精华内容
下载资源
问答
  • Java堆内存设计原理  通常来说,堆中存储通过new字符创建的对象或者数组;  JVM中堆内存分为2大块,Permanent space和 Heap space  Permanent即持久代(Permanent Generation),主要存储了Java类的定义...

    Java堆内存设计原理

       通常来说,堆中存储通过new字符创建的对象或者数组;

      JVM中堆内存分为2大块,Permanent space和 Heap space

    •   Permanent即持久代(Permanent Generation),主要存储了Java类的定义信息,与垃圾收集器要收集的Java对象关系不大
    •   Heap={Old+new={Eden,from,to}},Old代表年老代,New代表年轻代,年老代和年轻代的划分对垃圾回收器的影响比较大

           

    Permanent Generation 持久代

       用来存放静态数据类型

     

    年轻代、年老代

        所有新生的对象首先放在年轻代,年轻代的目标就是尽可能的在此将生命周期短的对象通过垃圾回收器进行回收。年轻代分为3个去,Eden,Survivor(From,To其中,From和To区地位是平等的);

        大部分对象是在Eden去生成档Eden区满时,还存活的对象被复制到Survivor区中的From区或者To区,当其中一个Survivor区满时,还存活的对象就被复制到另一个Survivor区,当另一个Survivor区也满的时候,这时候从另一个Survivor区复制过来的仍然存活的对象就有可能被复制到Old区;

     

    针对年轻代的回收    Young GC
    针对年老代的回收     Full     GC

     

    内存申请过程:

    1.JVM会试图为相关的Java对象在Eden区申请内存空间;

    2.如果在Eden区内存中空间足够,则申请结束;否则,进行下一步;

    3.JVM试图释放Eden区所有不活跃的对象(Young GC),释放后空间仍然不足的话,则JVM会试图将活跃的对象存放至Survivor区中

    4.Survivor区是Eden区与年老代的中间件。当年老代空间足够时,在Survivor区中存活了一定次数的对象会被移到年老代;

    5.当年老代空间不足时,JVM会在年老代执行完全的垃圾回收(Full GC);

    6.当Full GC 后,若Survivor区和年老代仍然无法存放从Eden区复制过来的对象,这时会出现JVM无法在Eden区为新的对象申请内存空间,即“Out of Memory”

     

    出现错误情况

    1.年老代溢出 ,表现为 java.lang.OutOfMemoryError:JavaHeapSpace

      原因:设置的内存参数Xmx过小或内存泄漏及使用不当问题

     

    2.持久代溢出,表现为java.lang OutofMemoryError:PermGenSpace

      原因:持久代设置过小,动态加载大量Java对象导致溢出

      解决方法:将 -xx MaxPermSize调大

     

    参数说明(来自网络):

    -Xms :初始堆大小。只要启动,就占用的堆大小
    -Xmx :最大堆大小。java.lang.OutOfMemoryError: Java heap这个错误可以通过配置-Xms和-Xmx参数来设置
    -Xss:栈大小分配。栈是每个线程私有的区域,通常只有几百K大小,决定了函数调用的深度,而局部变量、参数都分配到栈上。当出现大量局部变量,递归时,会发生栈空间OOM(java.lang.StackOverflowError)之类的错误。
    -XX:NewSize=n :设置新生代大小的绝对值
    -XX:NewRatio=n: 设置年轻代和年老代的比值。比如设置为3,则新生代:老年代=1:3,新生代占1/4的总heap大小。
    -XX:SurvivorRatio=n :年轻代中Eden区与两个Survivor区的比值。注意Survivor区有from和to两个。比如设置为8时,那么eden:from:to=8:1:1
    -XX:MaxPermSize=n :设置持久代大小 ;java.lang.OutOfMemoryError: PermGen space这个OOM错误需要合理调大PermSize和MaxPermSize大小。
    -XX:HeapDumpOnOutOfMemoryError :发生OOM时转储堆到文件,这是一个非常好的诊断方法。
    -XX:HeapDumpPath :导出堆的转储文件路径
    -XX:OnOutOfMemoryError:OOM时,执行一个脚本,比如发送邮件报警,重启程序。后面跟着一个脚本的路径。

    展开全文
  • Numpy多维数组的内存设计与实现原理

    千次阅读 2018-11-26 22:42:04
    ndarray的内存实现原理、切片索引的视图原理

    1、内存设计与实现原理

    ndarray的内存结构

    ndarray的实例本质上由一个连续的一维内存段一个索引方案组合而成。这种将所有数据存放在一个连续的一维内存段的存储方式,实际与C语言中的多维数组存储方式一致。但Numpy索引的灵活设计,使得ndarray对象可适应于任何跨步索引方案,以下对ndarray对象以行作为主要存储顺序的内存设计进行说明。

    Numpy在创建数组或建立数组视图时,将数组的信息记录在不同属性,如shape属性指定各维度的元素的数量,dtype属性指定元素类型及其解释方式,strides属性指定各维度的跨度,itemsize属性指定单个元素占用字节数。

    图1 ndarray对象在内存中的存储与索引

    索引的解析

    对于NN维的数组array\sf array,将各维度的跨度存放在strides\sf{strides}列表中,则第k+1k+1维的跨度
    strides[k]={itemsize,k=N1itemsize×j=k+1N1shape[j],k=0, ,N2{\sf strides}[k] = \begin{cases} {\sf{itemsize}}, &k=N-1\\ {\sf{itemsize}} \times \prod_{j=k+1}^{N-1}{\sf{shape}}[j], &k=0,\cdots,N-2\\ \end{cases}

    令数组array\sf array的首元素地址为&array\&{\sf{array}},则数组中坐标为(i0,i1, ,iN1)(i_0,i_1,\cdots,i_{N-1})的元素的地址
    &array[i0][i1][iN1]=&array+k=0N1ik×strides[k]\&{\sf{array}}[i_0][i_1]\cdots[i_{N-1}]= \&{\sf{array}} + \sum_{k=0}^{N-1}i_{k}\times {\sf{strides}}[k]

    利用以上公式计算出给定坐标对应的地址,即&array[i0][i1][iN1]\&{\sf{array}}[i_0][i_1]\cdots[i_{N-1}],然后即可得到array[i0][i1][iN1]{\sf{array}}[i_0][i_1]\cdots[i_{N-1}]的值。

    实例

    对于数据类型为int32(占4字节)的二维整型数组
    b=(0123456789101112131415)\bm b = \left(\begin{matrix} 0 &1 &2 &3 \\ 4 &5 &6 &7 \\ 8 &{\bm\color {red}9}&10 &11 \\ 12 &13 &14 &15 \end{matrix}\right)

    其形状shape=(4,4){\sf shape}=(4,4)itemsize=4{\sf itemsize}=4,因此不难计算出跨度列表strides=[16,4]{\sf strides}=[16, 4]

    若以b[2][1]b[2][1]的索引方式访问元素99,实际底层是将引用地址解析为
    &b[2][1]=&b+2×strides[0]+1×strides[1]=&b+36\&b[2][1] = \&b + 2 \times {\sf strides}[0] + 1\times {\sf strides}[1] = \&b+36

    显然,地址&b+36\&b+36存储的值为目标元素99,即完成了索引的解析。

    2、切片索引的视图原理

    切片索引的解析

    对于二维数组bb,使用以下起始值及步长对其进行切片
    a=b[begin0:end0:step0,begin1:end1:step1]a = b[{\sf begin_0:end_0:step_0}, {\sf begin_1:end_1:step_1}]

    易知,结果数组aa的首地址
    &a=&b[begin0,begin1]=&b+begin0×strides[0]+begin1×strides[1]\&a=\&b[{\sf begin_0}, {\sf begin_1}]=\&b+{\sf begin_0}\times {\sf strides}[0] + {\sf begin_1}\times {\sf strides}[1]

    基于各维度的切片步长,更新切片索引结果数组aa的跨度列表
    strides=step×strides=[step0,step1]×strides{\sf strides'} = {\sf step} \times {\sf strides} = [{\sf step_0}, {\sf step_1}] \times {\sf strides}

    此时,利用结果数组aa的起始地址&a\&a以及新的跨度列表strides{\sf strides'},使用索引a[i][j]a[i][j]的形式依然可以访问到目标元素。

    切片索引要求每一维度具有固定的切片步长,因此我们仅需要创建一个原始数组的视图,并根据起始位置以及各维度的切片步长,修改视图的起始位置以及各维度的跨度,即可访问到结果数组中的目标元素。因此,切片索引不需要复制原始数据。由于整数数组索引步数的随机性,不能通过更改索引方案的方案访问原数组。因此,整数数组索引返回的是原始数组的副本。

    实例

    对于数组bb,执行切片a=b[::3,1::2]a = b[::3, 1::2],得到红色标记位置元素
    b=(0123456789101112131415),a=(131315)\bm b = \left(\begin{matrix} 0 &{\bm\color {red}1} &2 &{\bm\color {red}3} \\ 4 &5 &6 &7 \\ 8 &9 &10 &11 \\ 12 &{\bm\color {red}13} &14 &{\bm\color {red}15} \end{matrix}\right), \quad\bm a=\left(\begin{matrix} 1 &3\\ 13 &15 \end{matrix}\right)

    原数组bb的跨度列表strides=[16,4]{\sf strides}=[16, 4],结果数组aa的首地址&a=&b+4\&a=\&b+4,结果数组aa的跨度列表strides=[48,8]{\sf strides'}=[48, 8]

    通过索引a[1,1]a[1,1]的方式访问元素15,实际底层将引用地址解析为
    &a[1][1]=&a+1×strides[0]+1×strides[1]=&a+56=&b+60\&a[1][1] = \&a + 1 \times {\sf strides'}[0] + 1\times {\sf strides'}[1] = \&a+56 = \&b+60

    此外
    &b[3][3]=&b+3×strides[0]+3×strides[1]=&b+60\&b[3][3] = \&b + 3 \times {\sf strides}[0] + 3\times {\sf strides}[1] = \&b+60

    显然,使用切片索引仅通过更改索引方案,即可访问到原始数据。

    展开全文
  • 内存设计原理

    2017-11-10 11:05:09
    1. 内存设计 1.1 目的 在给定的内存buffer上建立内存管理机制,根据用户需求从该buffer上分配内存或者将已经分配的内存释放回buffer中。 1.2 要求 尽量减少内存碎片,平均效率高于C语言的...

    1. 内存池设计

    1.1 目的

    在给定的内存buffer上建立内存管理机制,根据用户需求从该buffer上分配内存或者将已经分配的内存释放回buffer中。

    1.2 要求

    尽量减少内存碎片,平均效率高于C语言的malloc和free。

    1.3 设计思路

    将buffer分为四部分,第1部分是mem_pool结构体;第2部分是内存映射表;第3部分是内存chunk结构体缓冲区;第4部分是实际可分配的内存区。整个buffer结构图如图1所示:

    图1 内存buffer结构图

    图1 内存buffer结构图

    第1部分的作用是可以通过该mem_pool结构体控制整个内存池。

    第2部分的作用是记录第4部分,即实际可分配的内存区的使用情况。表中的每一个单元表示一个固定大小的内存块(block),多个连续的block组成一个chunk,每个block的详细结构如图2所示:

    图2 memory block结构图

    图2 memory block结构图

    其中count表示该block后面的与该block同属于一个chunk的blokc的个数,start表示该block所在的chunk的起始block索引。其实start这个域只有在每个chunk的最后一个block中才会用到(用于从当前chunk寻找前一个chunk的起始位置),而pmem_chunk则是一个指针,指向一个mem_chunk结构体。任意一块大小的内存都会被取向上整到block大小的整数倍。

    第3部分是一个mem_chunk pool,其作用是存储整个程序可用的mem_chunk结构体。mem_chunk pool中的mem_chunk被组织成双向链表结构(快速插入和删除)。每个mem_chunk结构图如图3所示:

    图3 memory chunk结构图

    图3 memory chunk结构图

    其中pmem_block指向该chunk在内存映射表中的位置,others表示其他一些域,不同的实现对应该域的内容略有不同。

    第4部分就是实际可以被分配给用户的内存。

    整个内存池管理程序除了这四部分外,还有一个重要的内容就是memory chunk set。虽然其中的每个元素都来自mem_chunk pool,但是它与mem_chunk pool的不同之处在于其中的每个memory chunk中记录了当前可用的一块内存的相关信息。而mem_chunk pool中的memory chunk的内容是无定以的。可以这样理解mem_chunk pool与memory chunk set:mem_chunk pool是为memory chunk set分配内存的“内存池”,只是该“内存池”每次分配的内存大小是固定的,为mem_chunk结构体的大小。内存池程序主要是通过搜索这个memory chunk set来获取可被分配的内存。在memory chunk set上建立不同的数据结构就构成了不同的内存池实现方法,同时也导致了不同的搜索效率,直接影响内存池的性能,本文稍后会介绍两种内存池的实现。

    1.4 内存池管理程序运行过程

    • 初始化:内存映射表中只有一块可用的内存信息,大小为内存池中所有可用的内存。从memory chunk pool中分配一个mem_chunk,使其指向内存映射表中的第一个block,并根据具体的内存池实现方式填充mem_chunk中的其他域,然后将该mem_chunk添加到memory chunk set中。
    • 申请内存:当用户申请一块内存时,首先在memory chunk set中查找合适的内存块。如果找到符合要求的内存块,就在内存映射表中找到相应的chunk,并修改chunk中相应block结构体的内容,然后根据修改后的chunk修改memory chunk set中chunk的内容,最后返回分配内存的起始地址;否则返回NULL。
    • 释放内存:当用户释放一块内存时,首先根据这块内存的起始地址找到其在内存映射表中对应的chunk,然后尝试将该chunk和与其相邻的chunk合并,修改chunk中相应block的内容并修改memory chunk set中相应chunk的内容或者向memory chunk set加入新的mem_chunk(这种情况在不能合并内存是发生)。

    1.5 减少内存碎片

    本文设计的方法只能在一定程度上减少内存碎片,并不能彻底消除内存碎片。具体方法如下:

    在用户释放内存时,尝试将该内存与其相邻的内存合并。如果其相邻内存为未分配内存则合并成功,合并后作为一整块内存使用;如火其相邻内存为已分配内存则不能合并,该释放的内存块作为一个独立的内存块被使用。

    2 内存池实现-链表结构

    2.1 性能分析

    链表结构的内存池实现是指将memory chunk set实现为双链表结构。这种方法的优缺点如下:

    优点:释放内存很快,O(1)复杂度。

    缺点:分配内存较慢,O(n)复杂度。

    2.2 内存池运行状态转移图

    绿色表示未使用的内存,红色表示已经使用的内存。其中每个block表示64B,这个值可以根据具体需要设定。

    • 初始化

    图4 内存池初始化状态

    图4 内存池初始化状态

    • 申请内存

    图5 第1次申请128B内存后

    图5 第1次申请128B内存后

    图6 第n次申请、释放内存后

    图6 第n次申请、释放内存后

    • 释放内存

    图7 释放64B内存前后

    图7 释放64B内存前后

    3 内存池实现-大顶堆结构

    3.1 性能分析

     

    大顶堆结构的内存池实现是指将memory chunk set实现为大顶堆结构。这种方法的优缺点如下:

    优点:降低了分配内存的时间复杂度,O(log(n))。

    缺点:增加了释放内存的时间复杂度,O(log(n))。

    3.2 内存池运行状态转移图

    绿色表示未使用的内存,红色表示已经使用的内存。其中每个block表示64B,这个值可以根据具体需要设定。

    • 初始化

    图8 内存池初始化状态

    图8 内存池初始化状态

    • 申请内存

    图9 第1次申请128B内存后

    图9 第1次申请128B内存后

    图10 第n次申请、释放内存后

    图10 第n次申请、释放内存后

    • 释放内存

    图11 释放64B内存前后

    图11 释放64B内存前后

    4 性能测试

    • 测试对象:C语言的malloc、free和本文的两种内存池(大小为500M,实际可分配内存为310M)。
    • 测试指标:执行n=2000次随机分配、释放随机大小内存(范围为64B~1024B)的时间比。
    • 测试方法1:

    (1) 生成n个随机数,大小在64~1024之间,用于表示n个要分配的内存大小;

    (2) 生成n个随机数,取值 为0或者1,表示每次分配内存后紧接着是否释放内存;

    (3) 测量C语言的malloc、free和本文两种内存池执行n次随机分配、释放随机大小内存的时间比ratio;

    (4) 重复(3)m=200次,记录每次活动的ratio,并绘制相应的曲线。

    • 测试方法2:

    (1) 生成n个随机数,大小在a~b之间(初始值a=64,b=1024),用于表示n个要分配的内存大小;

    (2) 测量C语言的malloc、free和本文两种内存池执行n次分配、释放随机大小内存的时间比ratio;

    (3) 重复(2)m=512次,每次分配的内存容量的范围比前一次大1024B,记录每次获得的ratio,并绘制相应曲线。

    4.1 性能测试结果-链表结果内存池

    图12 链表结构内存池性能测试结果1

    图12 链表结构内存池性能测试结果1

    链表结构内存池性能测试结果2

    图13 链表结构内存池性能测试结果2

    4.2 性能测试结果-大顶堆结构内存池

    图14 大顶堆内存池性能测试结果1

    图14 大顶堆内存池性能测试结果1

    图15 大顶堆内存池性能测试结果2

    图15 大顶堆内存池性能测试结果2

    4.3 性能比较

    图16 两种内存池性能测试结果比较1

    图16 两种内存池性能测试结果比较1

    图17 两种内存池性能测试结果比较2

    图17 两种内存池性能测试结果比较2

    5 结论

    从上面的内存池性能测试结果中可以看出,相比C语言的malloc和free,内存池使得用户分配内存和释放内存的效率有了较大的提高,这一优势尤其分配较大快的内存时体现的尤为突出。

    同时也可以看出大顶堆结够的内存池的性能并不比链表结构的内存池性能高,反而低于链表结构内存池的性能。这再一次表明O(log(n))优于O(n)是有条件的。当然,本文的测试具有一定的局限性,也许在其他的测试案例中大顶堆结构的内存池性能会超越链表结构的内存池。

     

    附:源代码

    链表结构内存池:

    MemoryPool.h

    [cpp] view plain copy
    1. #ifndef _MEMORYPOOL_H  
    2. #define _MEMORYPOOL_H  
    3. #include <stdlib.h>  
    4. #define MINUNITSIZE 64  
    5. #define ADDR_ALIGN 8  
    6. #define SIZE_ALIGN MINUNITSIZE  
    7. struct memory_chunk;  
    8. typedef struct memory_block  
    9. {  
    10.     size_t count;  
    11.     size_t start;  
    12.     memory_chunk* pmem_chunk;  
    13. }memory_block;  
    14. // 可用的内存块结构体  
    15. typedef struct memory_chunk  
    16. {  
    17.     memory_block* pfree_mem_addr;  
    18.     memory_chunk* pre;  
    19.     memory_chunk* next;  
    20. }memory_chunk;  
    21. // 内存池结构体  
    22. typedef struct MEMORYPOOL  
    23. {  
    24.     void *memory;  
    25.     size_t size;  
    26.     memory_block* pmem_map;   
    27.     memory_chunk* pfree_mem_chunk;  
    28.     memory_chunk* pfree_mem_chunk_pool;  
    29.     size_t mem_used_size; // 记录内存池中已经分配给用户的内存的大小  
    30.     size_t mem_map_pool_count; // 记录链表单元缓冲池中剩余的单元的个数,个数为0时不能分配单元给pfree_mem_chunk  
    31.     size_t free_mem_chunk_count; // 记录 pfree_mem_chunk链表中的单元个数  
    32.     size_t mem_map_unit_count; //   
    33.     size_t mem_block_count; // 一个 mem_unit 大小为 MINUNITSIZE  
    34. }MEMORYPOOL, *PMEMORYPOOL;  
    35. /************************************************************************/  
    36. /* 生成内存池 
    37.  * pBuf: 给定的内存buffer起始地址 
    38.  * sBufSize: 给定的内存buffer大小 
    39.  * 返回生成的内存池指针 
    40. /************************************************************************/  
    41. PMEMORYPOOL CreateMemoryPool(void* pBuf, size_t sBufSize);  
    42. /************************************************************************/  
    43. /* 暂时没用 
    44. /************************************************************************/  
    45. void ReleaseMemoryPool(PMEMORYPOOL* ppMem) ;   
    46. /************************************************************************/  
    47. /* 从内存池中分配指定大小的内存  
    48.  * pMem: 内存池 指针 
    49.  * sMemorySize: 要分配的内存大小 
    50.  * 成功时返回分配的内存起始地址,失败返回NULL 
    51. /************************************************************************/  
    52. void* GetMemory(size_t sMemorySize, PMEMORYPOOL pMem) ;  
    53.   
    54. /************************************************************************/  
    55. /* 从内存池中释放申请到的内存 
    56.  * pMem:内存池指针 
    57.  * ptrMemoryBlock:申请到的内存起始地址 
    58. /************************************************************************/  
    59. void FreeMemory(void *ptrMemoryBlock, PMEMORYPOOL pMem) ;  
    60.   
    61. #endif //_MEMORYPOOL_H  
     

    MemoryPool.cpp

    [cpp] view plain copy
    1. #include "stdafx.h"  
    2. #include <memory.h>  
    3. #include "MemoryPool.h"  
    4. /************************************************************************/  
    5. /* 内存池起始地址对齐到ADDR_ALIGN字节 
    6. /************************************************************************/  
    7. size_t check_align_addr(void*& pBuf)  
    8. {  
    9.     size_t align = 0;  
    10.     size_t addr = (int)pBuf;  
    11.     align = (ADDR_ALIGN - addr % ADDR_ALIGN) % ADDR_ALIGN;  
    12.     pBuf = (char*)pBuf + align;  
    13.     return align;  
    14. }  
    15. /************************************************************************/  
    16. /* 内存block大小对齐到MINUNITSIZE字节 
    17. /************************************************************************/  
    18. size_t check_align_block(size_t size)  
    19. {  
    20.     size_t align = size % MINUNITSIZE;  
    21.       
    22.     return size - align;   
    23. }  
    24. /************************************************************************/  
    25. /* 分配内存大小对齐到SIZE_ALIGN字节 
    26. /************************************************************************/  
    27. size_t check_align_size(size_t size)  
    28. {  
    29.     size = (size + SIZE_ALIGN - 1) / SIZE_ALIGN * SIZE_ALIGN;  
    30.     return size;  
    31. }  
    32. /************************************************************************/  
    33. /* 以下是链表相关操作 
    34. /************************************************************************/  
    35. memory_chunk* create_list(memory_chunk* pool, size_t count)  
    36. {  
    37.     if (!pool)  
    38.     {  
    39.         return NULL;  
    40.     }  
    41.     memory_chunk* head = NULL;  
    42.     for (size_t i = 0; i < count; i++)  
    43.     {  
    44.         pool->pre = NULL;  
    45.         pool->next = head;  
    46.         if (head != NULL)  
    47.         {  
    48.             head->pre = pool;              
    49.         }  
    50.         head = pool;  
    51.         pool++;  
    52.     }  
    53.     return head;  
    54. }  
    55. memory_chunk* front_pop(memory_chunk*& pool)  
    56. {  
    57.     if (!pool)  
    58.     {  
    59.         return NULL;  
    60.     }  
    61.     memory_chunk* tmp = pool;  
    62.     pool = tmp->next;  
    63.     pool->pre = NULL;  
    64.     return  tmp;  
    65. }  
    66. void push_back(memory_chunk*& head, memory_chunk* element)  
    67. {  
    68.     if (head == NULL)  
    69.     {  
    70.         head = element;  
    71.         head->pre = element;  
    72.         head->next = element;  
    73.         return;  
    74.     }  
    75.     head->pre->next = element;  
    76.     element->pre = head->pre;  
    77.     head->pre = element;  
    78.     element->next = head;  
    79. }  
    80. void push_front(memory_chunk*& head, memory_chunk* element)  
    81. {  
    82.     element->pre = NULL;  
    83.     element->next = head;  
    84.     if (head != NULL)  
    85.     {  
    86.         head->pre = element;           
    87.     }  
    88.     head = element;  
    89. }  
    90. void delete_chunk(memory_chunk*& head, memory_chunk* element)  
    91. {  
    92.     // 在双循环链表中删除元素  
    93.     if (element == NULL)  
    94.     {  
    95.         return;  
    96.     }  
    97.     // element为链表头  
    98.     else if (element == head)  
    99.     {  
    100.         // 链表只有一个元素  
    101.         if (head->pre == head)  
    102.         {  
    103.             head = NULL;  
    104.         }  
    105.         else  
    106.         {  
    107.             head = element->next;  
    108.             head->pre = element->pre;  
    109.             head->pre->next = head;  
    110.         }  
    111.     }  
    112.     // element为链表尾  
    113.     else if (element->next == head)  
    114.     {  
    115.         head->pre = element->pre;  
    116.         element->pre->next = head;  
    117.     }  
    118.     else  
    119.     {  
    120.         element->pre->next = element->next;  
    121.         element->next->pre = element->pre;  
    122.     }  
    123.     element->pre = NULL;  
    124.     element->next = NULL;  
    125. }  
    126. /************************************************************************/  
    127. /* 内存映射表中的索引转化为内存起始地址                                                                     
    128. /************************************************************************/  
    129. void* index2addr(PMEMORYPOOL mem_pool, size_t index)  
    130. {  
    131.     char* p = (char*)(mem_pool->memory);  
    132.     void* ret = (void*)(p + index *MINUNITSIZE);  
    133.       
    134.     return ret;  
    135. }  
    136. /************************************************************************/  
    137. /* 内存起始地址转化为内存映射表中的索引                                                                     
    138. /************************************************************************/  
    139. size_t addr2index(PMEMORYPOOL mem_pool, void* addr)  
    140. {  
    141.     char* start = (char*)(mem_pool->memory);  
    142.     char* p = (char*)addr;  
    143.     size_t index = (p - start) / MINUNITSIZE;  
    144.     return index;  
    145. }  
    146. /************************************************************************/  
    147. /* 生成内存池 
    148. * pBuf: 给定的内存buffer起始地址 
    149. * sBufSize: 给定的内存buffer大小 
    150. * 返回生成的内存池指针 
    151. /************************************************************************/  
    152. PMEMORYPOOL CreateMemoryPool(void* pBuf, size_t sBufSize)  
    153. {  
    154.     memset(pBuf, 0, sBufSize);  
    155.     PMEMORYPOOL mem_pool = (PMEMORYPOOL)pBuf;  
    156.     // 计算需要多少memory map单元格  
    157.     size_t mem_pool_struct_size = sizeof(MEMORYPOOL);  
    158.     mem_pool->mem_map_pool_count = (sBufSize - mem_pool_struct_size + MINUNITSIZE - 1) / MINUNITSIZE;  
    159.     mem_pool->mem_map_unit_count = (sBufSize - mem_pool_struct_size + MINUNITSIZE - 1) / MINUNITSIZE;  
    160.     mem_pool->pmem_map = (memory_block*)((char*)pBuf + mem_pool_struct_size);  
    161.     mem_pool->pfree_mem_chunk_pool = (memory_chunk*)((char*)pBuf + mem_pool_struct_size + sizeof(memory_block) * mem_pool->mem_map_unit_count);  
    162.       
    163.     mem_pool->memory = (char*)pBuf + mem_pool_struct_size+ sizeof(memory_block) * mem_pool->mem_map_unit_count + sizeof(memory_chunk) * mem_pool->mem_map_pool_count;  
    164.     mem_pool->size = sBufSize - mem_pool_struct_size - sizeof(memory_block) * mem_pool->mem_map_unit_count - sizeof(memory_chunk) * mem_pool->mem_map_pool_count;  
    165.     size_t align = check_align_addr(mem_pool->memory);  
    166.     mem_pool->size -= align;  
    167.     mem_pool->size = check_align_block(mem_pool->size);  
    168.     mem_pool->mem_block_count = mem_pool->size / MINUNITSIZE;  
    169.     // 链表化  
    170.     mem_pool->pfree_mem_chunk_pool = create_list(mem_pool->pfree_mem_chunk_pool, mem_pool->mem_map_pool_count);  
    171.     // 初始化 pfree_mem_chunk,双向循环链表  
    172.     memory_chunk* tmp = front_pop(mem_pool->pfree_mem_chunk_pool);  
    173.     tmp->pre = tmp;  
    174.     tmp->next = tmp;  
    175.     tmp->pfree_mem_addr = NULL;  
    176.     mem_pool->mem_map_pool_count--;  
    177.       
    178.     // 初始化 pmem_map  
    179.     mem_pool->pmem_map[0].count = mem_pool->mem_block_count;  
    180.     mem_pool->pmem_map[0].pmem_chunk = tmp;  
    181.     mem_pool->pmem_map[mem_pool->mem_block_count-1].start = 0;  
    182.       
    183.     tmp->pfree_mem_addr = mem_pool->pmem_map;  
    184.     push_back(mem_pool->pfree_mem_chunk, tmp);  
    185.     mem_pool->free_mem_chunk_count = 1;  
    186.     mem_pool->mem_used_size = 0;  
    187.     return mem_pool;  
    188. }  
    189. /************************************************************************/  
    190. /* 暂时没用 
    191. /************************************************************************/  
    192. void ReleaseMemoryPool(PMEMORYPOOL* ppMem)   
    193. {  
    194. }  
    195. /************************************************************************/  
    196. /* 从内存池中分配指定大小的内存  
    197. * pMem: 内存池 指针 
    198. * sMemorySize: 要分配的内存大小 
    199. * 成功时返回分配的内存起始地址,失败返回NULL 
    200. /************************************************************************/  
    201. void* GetMemory(size_t sMemorySize, PMEMORYPOOL pMem)  
    202. {  
    203.     sMemorySize = check_align_size(sMemorySize);  
    204.     size_t index = 0;  
    205.     memory_chunk* tmp = pMem->pfree_mem_chunk;  
    206.     for (index = 0; index < pMem->free_mem_chunk_count; index++)  
    207.     {  
    208.         if (tmp->pfree_mem_addr->count * MINUNITSIZE >= sMemorySize)  
    209.         {             
    210.             break;  
    211.         }  
    212.           
    213.         tmp = tmp->next;  
    214.     }  
    215.       
    216.     if (index == pMem->free_mem_chunk_count)  
    217.     {  
    218.         return NULL;  
    219.     }  
    220.     pMem->mem_used_size += sMemorySize;  
    221.     if (tmp->pfree_mem_addr->count * MINUNITSIZE == sMemorySize)  
    222.     {  
    223.         // 当要分配的内存大小与当前chunk中的内存大小相同时,从pfree_mem_chunk链表中删除此chunk  
    224.         size_t current_index = (tmp->pfree_mem_addr - pMem->pmem_map);  
    225.         delete_chunk(pMem->pfree_mem_chunk, tmp);  
    226.         tmp->pfree_mem_addr->pmem_chunk = NULL;  
    227.           
    228.         push_front(pMem->pfree_mem_chunk_pool, tmp);  
    229.         pMem->free_mem_chunk_count--;  
    230.         pMem->mem_map_pool_count++;  
    231.           
    232.         return index2addr(pMem, current_index);  
    233.     }  
    234.     else  
    235.     {  
    236.         // 当要分配的内存小于当前chunk中的内存时,更改pfree_mem_chunk中相应chunk的pfree_mem_addr  
    237.           
    238.         // 复制当前mem_map_unit  
    239.         memory_block copy;  
    240.         copy.count = tmp->pfree_mem_addr->count;  
    241.         copy.pmem_chunk = tmp;  
    242.         // 记录该block的起始和结束索引  
    243.         memory_block* current_block = tmp->pfree_mem_addr;  
    244.         current_block->count = sMemorySize / MINUNITSIZE;  
    245.         size_t current_index = (current_block - pMem->pmem_map);  
    246.         pMem->pmem_map[current_index+current_block->count-1].start = current_index;  
    247.         current_block->pmem_chunk = NULL; // NULL表示当前内存块已被分配  
    248.         // 当前block被一分为二,更新第二个block中的内容  
    249.         pMem->pmem_map[current_index+current_block->count].count = copy.count - current_block->count;  
    250.         pMem->pmem_map[current_index+current_block->count].pmem_chunk = copy.pmem_chunk;  
    251.         // 更新原来的pfree_mem_addr  
    252.         tmp->pfree_mem_addr = &(pMem->pmem_map[current_index+current_block->count]);  
    253.       
    254.         size_t end_index = current_index + copy.count - 1;  
    255.         pMem->pmem_map[end_index].start = current_index + current_block->count;  
    256.         return index2addr(pMem, current_index);  
    257.     }     
    258. }  
    259. /************************************************************************/  
    260. /* 从内存池中释放申请到的内存 
    261. * pMem:内存池指针 
    262. * ptrMemoryBlock:申请到的内存起始地址 
    263. /************************************************************************/  
    264. void FreeMemory(void *ptrMemoryBlock, PMEMORYPOOL pMem)   
    265. {  
    266.     size_t current_index = addr2index(pMem, ptrMemoryBlock);  
    267.     size_t size = pMem->pmem_map[current_index].count * MINUNITSIZE;  
    268.     // 判断与当前释放的内存块相邻的内存块是否可以与当前释放的内存块合并  
    269.     memory_block* pre_block = NULL;  
    270.     memory_block* next_block = NULL;  
    271.     memory_block* current_block = &(pMem->pmem_map[current_index]);  
    272.     // 第一个  
    273.     if (current_index == 0)  
    274.     {  
    275.         if (current_block->count < pMem->mem_block_count)  
    276.         {  
    277.             next_block = &(pMem->pmem_map[current_index+current_block->count]);  
    278.             // 如果后一个内存块是空闲的,合并  
    279.             if (next_block->pmem_chunk != NULL)  
    280.             {  
    281.                 next_block->pmem_chunk->pfree_mem_addr = current_block;  
    282.                 pMem->pmem_map[current_index+current_block->count+next_block->count-1].start = current_index;  
    283.                 current_block->count += next_block->count;  
    284.                 current_block->pmem_chunk = next_block->pmem_chunk;  
    285.                 next_block->pmem_chunk = NULL;  
    286.             }  
    287.             // 如果后一块内存不是空闲的,在pfree_mem_chunk中增加一个chunk  
    288.             else  
    289.             {  
    290.                 memory_chunk* new_chunk = front_pop(pMem->pfree_mem_chunk_pool);  
    291.                 new_chunk->pfree_mem_addr = current_block;  
    292.                 current_block->pmem_chunk = new_chunk;  
    293.                 push_back(pMem->pfree_mem_chunk, new_chunk);  
    294.                 pMem->mem_map_pool_count--;  
    295.                 pMem->free_mem_chunk_count++;  
    296.             }  
    297.         }  
    298.         else  
    299.         {  
    300.             memory_chunk* new_chunk = front_pop(pMem->pfree_mem_chunk_pool);  
    301.             new_chunk->pfree_mem_addr = current_block;  
    302.             current_block->pmem_chunk = new_chunk;  
    303.             push_back(pMem->pfree_mem_chunk, new_chunk);  
    304.             pMem->mem_map_pool_count--;  
    305.             pMem->free_mem_chunk_count++;  
    306.         }         
    307.     }  
    308.       
    309.     // 最后一个  
    310.     else if (current_index == pMem->mem_block_count-1)  
    311.     {  
    312.         if (current_block->count < pMem->mem_block_count)  
    313.         {  
    314.             pre_block = &(pMem->pmem_map[current_index-1]);  
    315.             size_t index = pre_block->count;  
    316.             pre_block = &(pMem->pmem_map[index]);  
    317.               
    318.             // 如果前一个内存块是空闲的,合并  
    319.             if (pre_block->pmem_chunk != NULL)  
    320.             {  
    321.                 pMem->pmem_map[current_index+current_block->count-1].start = current_index - pre_block->count;  
    322.                 pre_block->count += current_block->count;  
    323.                 current_block->pmem_chunk = NULL;  
    324.             }  
    325.             // 如果前一块内存不是空闲的,在pfree_mem_chunk中增加一个chunk  
    326.             else  
    327.             {  
    328.                 memory_chunk* new_chunk = front_pop(pMem->pfree_mem_chunk_pool);  
    329.                 new_chunk->pfree_mem_addr = current_block;  
    330.                 current_block->pmem_chunk = new_chunk;  
    331.                 push_back(pMem->pfree_mem_chunk, new_chunk);  
    332.                 pMem->mem_map_pool_count--;  
    333.                 pMem->free_mem_chunk_count++;  
    334.             }  
    335.         }  
    336.         else  
    337.         {  
    338.             memory_chunk* new_chunk = front_pop(pMem->pfree_mem_chunk_pool);  
    339.             new_chunk->pfree_mem_addr = current_block;  
    340.             current_block->pmem_chunk = new_chunk;  
    341.             push_back(pMem->pfree_mem_chunk, new_chunk);  
    342.             pMem->mem_map_pool_count--;  
    343.             pMem->free_mem_chunk_count++;  
    344.         }  
    345.     }  
    346.     else  
    347.     {         
    348.         next_block = &(pMem->pmem_map[current_index+current_block->count]);  
    349.         pre_block = &(pMem->pmem_map[current_index-1]);  
    350.         size_t index = pre_block->start;  
    351.         pre_block = &(pMem->pmem_map[index]);  
    352.         bool is_back_merge = false;  
    353.         if (next_block->pmem_chunk == NULL && pre_block->pmem_chunk == NULL)  
    354.         {  
    355.             memory_chunk* new_chunk = front_pop(pMem->pfree_mem_chunk_pool);  
    356.             new_chunk->pfree_mem_addr = current_block;  
    357.             current_block->pmem_chunk = new_chunk;  
    358.             push_back(pMem->pfree_mem_chunk, new_chunk);  
    359.             pMem->mem_map_pool_count--;  
    360.             pMem->free_mem_chunk_count++;  
    361.         }  
    362.         // 后一个内存块  
    363.         if (next_block->pmem_chunk != NULL)  
    364.         {  
    365.             next_block->pmem_chunk->pfree_mem_addr = current_block;  
    366.             pMem->pmem_map[current_index+current_block->count+next_block->count-1].start = current_index;  
    367.             current_block->count += next_block->count;  
    368.             current_block->pmem_chunk = next_block->pmem_chunk;  
    369.             next_block->pmem_chunk = NULL;  
    370.             is_back_merge = true;  
    371.         }  
    372.         // 前一个内存块  
    373.         if (pre_block->pmem_chunk != NULL)  
    374.         {  
    375.             pMem->pmem_map[current_index+current_block->count-1].start = current_index - pre_block->count;  
    376.             pre_block->count += current_block->count;  
    377.             if (is_back_merge)  
    378.             {  
    379.                 delete_chunk(pMem->pfree_mem_chunk, current_block->pmem_chunk);  
    380.                 push_front(pMem->pfree_mem_chunk_pool, current_block->pmem_chunk);  
    381.                 pMem->free_mem_chunk_count--;  
    382.                 pMem->mem_map_pool_count++;  
    383.             }  
    384.             current_block->pmem_chunk = NULL;              
    385.         }         
    386.     }  
    387.     pMem->mem_used_size -= size;  
    388. }  
     

    MemoryPoolTest.cpp

    [cpp] view plain copy
    1. // memory pool test.cpp : Defines the entry point for the console application.  
    2. #include <tchar.h>  
    3. #include "MemoryPool.h"  
    4. #include <iostream>  
    5. #include <windows.h>  
    6. #include <vector>  
    7. #include <time.h>  
    8. #include <math.h>  
    9. #include <fstream>  
    10. using namespace std;  
    11. int break_time = 0;  
    12. // 检测内存池相关参数  
    13. void check_mem_pool(int& max_chunk_size, int& free_chunk_count, int& min_chunk_size, int& total_free_mem, MEMORYPOOL* mem_pool)  
    14. {  
    15.     memory_chunk* head = mem_pool->pfree_mem_chunk;  
    16.     memory_chunk* tmp = head;  
    17.     free_chunk_count = 0;  
    18.     total_free_mem = 0;  
    19.     max_chunk_size = 0;  
    20.     min_chunk_size = 500*1024*1024;  
    21.     if (head == NULL)  
    22.     {  
    23.         min_chunk_size = 0;  
    24.         return;  
    25.     }  
    26.     while (tmp->next != head)  
    27.     {  
    28.         free_chunk_count++;  
    29.         total_free_mem += tmp->pfree_mem_addr->count * MINUNITSIZE;  
    30.         if (tmp->pfree_mem_addr->count * MINUNITSIZE > max_chunk_size )  
    31.         {  
    32.             max_chunk_size = tmp->pfree_mem_addr->count * MINUNITSIZE;  
    33.         }  
    34.         if (tmp->pfree_mem_addr->count * MINUNITSIZE < min_chunk_size)  
    35.         {  
    36.             min_chunk_size = tmp->pfree_mem_addr->count * MINUNITSIZE;  
    37.         }  
    38.         tmp = tmp->next;  
    39.     }  
    40.     free_chunk_count++;  
    41.     total_free_mem += tmp->pfree_mem_addr->count * MINUNITSIZE;  
    42.     if (tmp->pfree_mem_addr->count * MINUNITSIZE > max_chunk_size )  
    43.     {  
    44.         max_chunk_size = tmp->pfree_mem_addr->count * MINUNITSIZE;  
    45.     }  
    46.     if (tmp->pfree_mem_addr->count * MINUNITSIZE < min_chunk_size)  
    47.     {  
    48.         min_chunk_size = tmp->pfree_mem_addr->count * MINUNITSIZE;  
    49.     }  
    50. }  
    51. // 申请后紧接着释放  
    52. double test_mem_pool_perf_1(PMEMORYPOOL mem_pool, int iter, int* sizes)  
    53. {  
    54.     cout << "*********************test_mem_pool_perf_1*********************" << endl;  
    55.     LARGE_INTEGER litmp;   
    56.     LONGLONG QPart1, QPart2;  
    57.     double t;  
    58.     double dfMinus, dfFreq;   
    59.     QueryPerformanceFrequency(&litmp);  
    60.     dfFreq = (double)litmp.QuadPart;// 获得计数器的时钟频率  
    61.     QueryPerformanceCounter(&litmp);  
    62.     QPart1 = litmp.QuadPart;// 获得初始值  
    63.     for (int i = 0; i < iter; i++)  
    64.     {  
    65.         void *p = GetMemory(sizes[i], mem_pool);  
    66.         if (p == NULL)  
    67.         {  
    68.             cout << "break @ iterator = " << i << " / " << iter << ",    need memory " << sizes[i] << " Byte" << endl;  
    69.             cout << "total memory is: " << mem_pool->size << " Byte" << endl;  
    70.             cout << "memory used is: " << mem_pool->mem_used_size << " Byte" << endl;  
    71.             cout << "memory left is: " << mem_pool->size -  mem_pool->mem_used_size  << endl << endl;  
    72.             int max_chunk_size, free_chunk_count, min_chunk_size, total_free_mem;  
    73.             check_mem_pool(max_chunk_size, free_chunk_count, min_chunk_size, total_free_mem,  mem_pool);  
    74.             cout << "check memory pool result:" << endl;  
    75.             cout << "free_chunk_count:    " << free_chunk_count << endl  
    76.                 << "total_free_mem:   " << total_free_mem << endl  
    77.                 << "max_chunk_size:   " << max_chunk_size << endl  
    78.                 << "min_chunk_size:   " << min_chunk_size << endl;  
    79.             break;  
    80.         }  
    81.         FreeMemory(p,  mem_pool);  
    82.     }  
    83.     QueryPerformanceCounter(&litmp);  
    84.     QPart2 = litmp.QuadPart;//获得中止值  
    85.     dfMinus = (double)(QPart2-QPart1);  
    86.     t = dfMinus / dfFreq;// 获得对应的时间值,单位为秒     
    87.     cout << "test_mem_pool_perf_1: iter = " << iter << endl;  
    88.     cout << "time: " << t << endl;  
    89.     cout << "*********************test_mem_pool_perf_1*********************" <<  endl << endl << endl;  
    90.     return t;  
    91. }  
    92. double test_std_perf_1(int iter, int* sizes)  
    93. {  
    94.     cout << "*********************test_std_perf_1*********************" << endl;  
    95.     LARGE_INTEGER litmp;   
    96.     LONGLONG QPart1, QPart2;  
    97.     double t;  
    98.     double dfMinus, dfFreq;   
    99.     QueryPerformanceFrequency(&litmp);  
    100.     dfFreq = (double)litmp.QuadPart;// 获得计数器的时钟频率  
    101.     QueryPerformanceCounter(&litmp);  
    102.     QPart1 = litmp.QuadPart;// 获得初始值  
    103.     for (int i = 0; i < iter; i++)  
    104.     {  
    105.         void *p = malloc(sizes[i]);  
    106.         if (p == NULL)  
    107.         {  
    108.             cout << "break @ iterator = " << i << " / " << iter << ",    need memory " << sizes[i] << " Byte" << endl;  
    109.             break;  
    110.         }  
    111.         free(p);  
    112.     }  
    113.     QueryPerformanceCounter(&litmp);  
    114.     QPart2 = litmp.QuadPart;//获得中止值  
    115.     dfMinus = (double)(QPart2-QPart1);  
    116.     t = dfMinus / dfFreq;// 获得对应的时间值,单位为秒     
    117.     cout << "test_std_perf_1: iter = " << iter << endl;  
    118.     cout << "time: " << t << endl;  
    119.     cout << "*********************test_std_perf_1*********************" <<  endl << endl << endl;  
    120.     return t;  
    121. }  
    122. // 连续申请iter/2次,然后释放所有申请内存;再重复一次  
    123. double test_mem_pool_perf_2(PMEMORYPOOL mem_pool, int iter, int size)  
    124. {  
    125.     cout << "*********************test_mem_pool_perf_2*********************" << endl;  
    126.     LARGE_INTEGER litmp;   
    127.     LONGLONG QPart1, QPart2;  
    128.     double t;  
    129.     double dfMinus, dfFreq;   
    130.     QueryPerformanceFrequency(&litmp);  
    131.     dfFreq = (double)litmp.QuadPart;// 获得计数器的时钟频率  
    132.     QueryPerformanceCounter(&litmp);  
    133.     QPart1 = litmp.QuadPart;// 获得初始值  
    134.     void **p = new void*[iter];  
    135.     if (p == NULL)  
    136.     {  
    137.         cout << "new faild" << endl;  
    138.         return -1;  
    139.     }  
    140.     int count = 0;  
    141.     for (int i = 0; i < iter/2; i++)  
    142.     {  
    143.         p[i] = GetMemory(size, mem_pool);  
    144.         if (p[i] == NULL)  
    145.         {  
    146.             cout << "break @ iterator = " << i << " / " << iter << ",    need memory " << size << " Byte" << endl;  
    147.             cout << "total memory is: " << mem_pool->size << " Byte" << endl;  
    148.             cout << "memory used is: " << mem_pool->mem_used_size << " Byte" << endl;  
    149.             cout << "memory left is: " << mem_pool->size -  mem_pool->mem_used_size  << endl << endl;  
    150.             int max_chunk_size, free_chunk_count, min_chunk_size, total_free_mem;  
    151.             check_mem_pool(max_chunk_size, free_chunk_count, min_chunk_size, total_free_mem,  mem_pool);  
    152.             cout << "check memory pool result:" << endl;  
    153.             cout << "free_chunk_count:    " << free_chunk_count << endl  
    154.                 << "total_free_mem:   " << total_free_mem << endl  
    155.                 << "max_chunk_size:   " << max_chunk_size << endl  
    156.                 << "min_chunk_size:   " << min_chunk_size << endl;  
    157.             break;  
    158.         }  
    159.         count++;  
    160.     }  
    161.     for (int i = 0; i < count; i++)  
    162.     {  
    163.         FreeMemory(p[i],  mem_pool);  
    164.     }  
    165.     count = 0;  
    166.     for (int i = 0; i < iter/2; i++)  
    167.     {         
    168.         p[i] = GetMemory(size, mem_pool);  
    169.         if (p[i] == NULL)  
    170.         {  
    171.             cout << "break @ iterator = " << i << " / " << iter << ",    need memory " << size << " Byte" << endl;  
    172.             cout << "total memory is: " << mem_pool->size << " Byte" << endl;  
    173.             cout << "memory used is: " << mem_pool->mem_used_size << " Byte" << endl;  
    174.             cout << "memory left is: " << mem_pool->size -  mem_pool->mem_used_size  << endl << endl;  
    175.               
    176.             int max_chunk_size, free_chunk_count, min_chunk_size, total_free_mem;  
    177.             check_mem_pool(max_chunk_size, free_chunk_count, min_chunk_size, total_free_mem,  mem_pool);  
    178.             cout << "check memory pool result:" << endl;  
    179.             cout << "free_chunk_count:    " << free_chunk_count << endl  
    180.                 << "total_free_mem:   " << total_free_mem << endl  
    181.                 << "max_chunk_size:   " << max_chunk_size << endl  
    182.                 << "min_chunk_size:   " << min_chunk_size << endl;  
    183.             break;  
    184.         }  
    185.         count++;  
    186.     }  
    187.     for (int i = 0; i < count; i++)  
    188.     {  
    189.         if (p[i] == NULL)  
    190.         {  
    191.             cout << i << endl;  
    192.             break;  
    193.         }  
    194.         FreeMemory(p[i],  mem_pool);  
    195.     }  
    196.     QueryPerformanceCounter(&litmp);  
    197.     QPart2 = litmp.QuadPart;//获得中止值  
    198.     dfMinus = (double)(QPart2-QPart1);  
    199.     t = dfMinus / dfFreq;// 获得对应的时间值,单位为秒     
    200.     cout << "test_mem_pool_perf_2: iter = " << iter << endl;  
    201.     cout << "time: " << t << endl;  
    202.     delete []p;  
    203.     cout << "*********************test_mem_pool_perf_2*********************" <<  endl << endl << endl;  
    204.     return t;  
    205. }  
    206. // 连续申请inner_iter次,释放;重复iter/inner_iter次  
    207. double test_mem_pool_perf_3(PMEMORYPOOL mem_pool, int iter, int size)  
    208. {  
    209.     cout << "*********************test_mem_pool_perf_3*********************" << endl;  
    210.     int inner_iter = 10;  
    211.     void **p = new void*[inner_iter];  
    212.     if (p == NULL)  
    213.     {  
    214.         cout << "new faild" << endl;  
    215.         return -1;  
    216.     }  
    217.     LARGE_INTEGER litmp;   
    218.     LONGLONG QPart1, QPart2, start, finish;  
    219.     double t;  
    220.     double dfMinus, dfFreq;   
    221.     QueryPerformanceFrequency(&litmp);  
    222.     dfFreq = (double)litmp.QuadPart;// 获得计数器的时钟频率  
    223.     QueryPerformanceCounter(&litmp);  
    224.     QPart1 = litmp.QuadPart;// 获得初始值  
    225.     for (int k = 0; k < iter / inner_iter; k++)  
    226.     {  
    227.         int j = 0;  
    228.         for (j = 0; j < inner_iter; j++)  
    229.         {  
    230.             p[j] = GetMemory(size, mem_pool);  
    231.             if (p[j] == NULL)  
    232.             {  
    233.                 cout << "break @ iterator = " << j << " / " << iter << ",    need memory " << size << " Byte" << endl;  
    234.                 cout << "total memory is: " << mem_pool->size << " Byte" << endl;  
    235.                 cout << "memory used is: " << mem_pool->mem_used_size << " Byte" << endl;  
    236.                 cout << "memory left is: " << mem_pool->size -  mem_pool->mem_used_size  << endl << endl;  
    237.                 int max_chunk_size, free_chunk_count, min_chunk_size, total_free_mem;  
    238.                 check_mem_pool(max_chunk_size, free_chunk_count, min_chunk_size, total_free_mem,  mem_pool);  
    239.                 cout << "check memory pool result:" << endl;  
    240.                 cout << "free_chunk_count:    " << free_chunk_count << endl  
    241.                     << "total_free_mem:   " << total_free_mem << endl  
    242.                     << "max_chunk_size:   " << max_chunk_size << endl  
    243.                     << "min_chunk_size:   " << min_chunk_size << endl;  
    244.                 break;  
    245.             }  
    246.         }  
    247.         for (int i = 0; i < j; i++)  
    248.         {  
    249.                 FreeMemory(p[i],  mem_pool);          
    250.         }  
    251.     }  
    252.     QueryPerformanceCounter(&litmp);  
    253.     QPart2 = litmp.QuadPart;//获得中止值  
    254.     dfMinus = (double)(QPart2-QPart1);  
    255.     t = dfMinus / dfFreq;// 获得对应的时间值,单位为秒     
    256.     cout << "test_mem_pool_perf_3: iter = " << iter << endl;  
    257.     cout << "time: " << t << endl;  
    258.     cout << "*********************test_mem_pool_perf_3*********************" <<  endl << endl << endl;  
    259.     return t;  
    260. }  
    261. // 随机内存大小,随机释放操作  
    262. double test_mem_pool_perf_rand(PMEMORYPOOL mem_pool, int iter, int* sizes, int* instruction)  
    263. {  
    264.     cout << "-----------------------test_mem_pool_perf_rand----------------------- "<< endl;  
    265.     void** p = new void*[iter];  
    266.     if (p == NULL)  
    267.     {  
    268.         cout << "new failed" << endl;  
    269.         return -1;  
    270.     }  
    271.     LARGE_INTEGER litmp, gftime;   
    272.     LONGLONG QPart1, QPart2, start, finish;  
    273.     double t, GetMemory_time, FreeMemory_time;  
    274.     double dfMinus, dfFreq;   
    275.     QueryPerformanceFrequency(&litmp);  
    276.     dfFreq = (double)litmp.QuadPart;// 获得计数器的时钟频率  
    277.     QueryPerformanceCounter(&litmp);  
    278.     QPart1 = litmp.QuadPart;// 获得初始值  
    279.     int index = 0;  
    280.     int size;  
    281.     int free_tmp = 0;  
    282.     double seach_time;  
    283.     for (int i = 0; i < iter; i++)  
    284.     {  
    285.         size = sizes[i];  
    286.         p[index++] = GetMemory(size, mem_pool);  
    287.         if (p[index-1] == NULL)  
    288.         {             
    289.             break_time++;  
    290.             cout << "break @ iterator = " << i << " / " << iter << ",    need memory " << size << " Byte" << endl;  
    291.             cout << "total memory is: " << mem_pool->size << " Byte" << endl;  
    292.             cout << "memory used is: " << mem_pool->mem_used_size << " Byte" << endl;  
    293.             cout << "memory left is: " << mem_pool->size -  mem_pool->mem_used_size  << endl << endl;  
    294.             int max_chunk_size, free_chunk_count, min_chunk_size, total_free_mem;  
    295.             check_mem_pool(max_chunk_size, free_chunk_count, min_chunk_size, total_free_mem,  mem_pool);  
    296.             cout << "check memory pool result:" << endl;  
    297.             cout << "free_chunk_count:    " << free_chunk_count << endl  
    298.                 << "total_free_mem:   " << total_free_mem << endl  
    299.                 << "max_chunk_size:   " << max_chunk_size << endl  
    300.                 << "min_chunk_size:   " << min_chunk_size << endl;  
    301.             break;  
    302.         }  
    303.           
    304.         if (instruction[i] == 1)  
    305.         {             
    306.             FreeMemory(p[--index],  mem_pool);  
    307.         }     
    308.     }  
    309.     QueryPerformanceCounter(&litmp);  
    310.     QPart2 = litmp.QuadPart;//获得中止值  
    311.     dfMinus = (double)(QPart2-QPart1);  
    312.     t = dfMinus / dfFreq;// 获得对应的时间值,单位为秒     
    313.     cout << "test_mem_pool_perf_rand: iter = " << iter << endl;  
    314.     cout << "time: " << t << endl << endl;  
    315.     delete []p;  
    316.     return t;  
    317. }  
    318. double test_std_perf(int iter, int* sizes, int* instruction)  
    319. {  
    320.     cout << "test_std_perf" << endl;  
    321.     void** p =new void*[iter];  
    322.     if (p == NULL)  
    323.     {  
    324.         cout << "new failed" << endl;  
    325.         return -1;  
    326.     }  
    327.       
    328.     LARGE_INTEGER litmp;   
    329.     LONGLONG QPart1, QPart2;  
    330.     double t;  
    331.     double dfMinus, dfFreq;   
    332.     QueryPerformanceFrequency(&litmp);  
    333.     dfFreq = (double)litmp.QuadPart;// 获得计数器的时钟频率  
    334.     QueryPerformanceCounter(&litmp);  
    335.     QPart1 = litmp.QuadPart;// 获得初始值  
    336. //  cout << "test start" << endl;  
    337.     int index = 0;  
    338.     int size;  
    339.     for (int i = 0; i < iter; i++)  
    340.     {  
    341.         size = sizes[i];  
    342.         p[index++] = malloc(size);  
    343.         if (p[index-1] == NULL)  
    344.         {  
    345.             cout << i << endl;  
    346.             break;  
    347.         }  
    348.         if (instruction[i] == 1)  
    349.         {  
    350.             free(p[--index]);  
    351.         }         
    352.     }  
    353.     QueryPerformanceCounter(&litmp);  
    354.     QPart2 = litmp.QuadPart;//获得中止值  
    355.     dfMinus = (double)(QPart2-QPart1);  
    356.     t = dfMinus / dfFreq;// 获得对应的时间值,单位为秒     
    357.     cout << "test_std_perf: iter = " << iter << endl;  
    358.     cout << "time: " << t << endl << endl;  
    359.     for (int k = 0; k < index; k++)  
    360.     {  
    361.         free(p[k]);  
    362.     }  
    363.     return t;  
    364. }  
    365. double test_std_perf_fix_size(int iter, int size)  
    366. {  
    367.     cout << "******************* test_std_perf_fix_size *******************" << endl;  
    368.     LARGE_INTEGER litmp;   
    369.     LONGLONG QPart1, QPart2;  
    370.     double t;  
    371.     double dfMinus, dfFreq;   
    372.     QueryPerformanceFrequency(&litmp);  
    373.     dfFreq = (double)litmp.QuadPart;// 获得计数器的时钟频率  
    374.     QueryPerformanceCounter(&litmp);  
    375.     QPart1 = litmp.QuadPart;// 获得初始值  
    376.     int index = 0;  
    377.       
    378.     for (int i = 0; i < iter; i++)  
    379.     {  
    380.         void *p = malloc(size);  
    381.         if (p == NULL)  
    382.         {  
    383.             cout << i << endl;  
    384.             break;  
    385.         }  
    386.         free(p);  
    387.     }  
    388.     QueryPerformanceCounter(&litmp);  
    389.     QPart2 = litmp.QuadPart;//获得中止值  
    390.     dfMinus = (double)(QPart2-QPart1);  
    391.     t = dfMinus / dfFreq;// 获得对应的时间值,单位为秒     
    392.     cout << "test_std_perf: iter = " << iter << endl;  
    393.     cout << "time: " << t << endl;  
    394.     cout << "******************* test_std_perf_fix_size *******************" << endl << endl << endl;  
    395.     return t;  
    396. }  
    397. void test_correct_1(PMEMORYPOOL mem_pool, int iter, int size)  
    398. {  
    399.     vector<void*>vec;  
    400.     vector<void*>::iterator vec_iter;  
    401.     int i = 0;  
    402.     cout << "**************************** Get Memory Test Start ****************************"<< endl << endl;  
    403.     for (i = 0; i < iter; i++)  
    404.     {  
    405.         void *p = GetMemory(size, mem_pool);  
    406.         if (p == NULL)  
    407.         {  
    408.             cout << "break @ iterator = " << i << " / " << iter << ",    need memory " << size << " Byte" << endl;  
    409.             cout << "memory left is: " << mem_pool->size << " Byte" << endl;  
    410.             cout << "memory used is: " << mem_pool->mem_used_size << " Byte" << endl << endl;  
    411.             break;  
    412.         }  
    413.         vec.push_back(p);  
    414.     }  
    415.     cout << "break @ iterator = " << i << " / " << iter << ",    need memory " << size << " Byte" << endl;  
    416.     cout << "memory left is: " << mem_pool->size << " Byte" << endl;  
    417.     cout << "memory used is: " << mem_pool->mem_used_size << " Byte" << endl << endl;  
    418.     cout << "verify memory size" << endl;  
    419.     memory_chunk* tmp = mem_pool->pfree_mem_chunk;  
    420.     int free_size = 0;  
    421.     for (int k = 0; k < mem_pool->free_mem_chunk_count; k++)  
    422.     {  
    423.         free_size += tmp->pfree_mem_addr->count * MINUNITSIZE;  
    424.         tmp = tmp->next;  
    425.     }  
    426.     cout << "memory free size is " << free_size << " Byte" << endl;  
    427.     cout << "memory used size is " << mem_pool->mem_used_size << " Byte" << endl;  
    428.     cout << "*************************** Get Memory Test Finish ***************************"<< endl << endl;  
    429.     cout << "*************************** Free Memory Test Start ***************************"<< endl << endl;  
    430.     int index = 0;  
    431.     for (vec_iter = vec.begin(); vec_iter != vec.end(); vec_iter++)  
    432.     {  
    433.         index++;  
    434.         FreeMemory(*vec_iter, mem_pool);  
    435.     }  
    436.     cout << "memory left is: " << mem_pool->size << " Byte" << endl;  
    437.     cout << "memory used is: " << mem_pool->mem_used_size << " Byte" << endl << endl;  
    438.     cout << "*************************** Free Memory Test Finish ***************************"<< endl << endl;  
    439.     cout << "********************* Get Memory Test (after Free) Start *********************"<< endl << endl;  
    440.     for (i = 0; i < iter; i++)  
    441.     {  
    442.         void *p = GetMemory(size, mem_pool);  
    443.         if (p == NULL)  
    444.         {  
    445.             cout << "break @ iterator = " << i << " / " << iter << ",    need memory " << size << " Byte" << endl;  
    446.             cout << "memory left is: " << mem_pool->size << " Byte" << endl;  
    447.             cout << "memory used is: " << mem_pool->mem_used_size << " Byte" << endl << endl;  
    448.             int max_size = 0;  
    449.             memory_chunk* tmp = mem_pool->pfree_mem_chunk;  
    450.             for (int k = 0; k < mem_pool->free_mem_chunk_count; k++)  
    451.             {  
    452.                 if (tmp->pfree_mem_addr->count * MINUNITSIZE > max_size)  
    453.                 {  
    454.                     max_size = tmp->pfree_mem_addr->count * MINUNITSIZE > max_size;  
    455.                 }  
    456.             }  
    457.             cout << "max chunk size is: " << max_size << " Byte" << endl;  
    458.             break;  
    459.         }  
    460.         vec.push_back(p);  
    461.     }  
    462.     cout << "break @ iterator = " << i << " / " << iter << ",    need memory " << size << " Byte" << endl;  
    463.     cout << "memory left is: " << mem_pool->size << " Byte" << endl;  
    464.     cout << "memory used is: " << mem_pool->mem_used_size << " Byte" << endl << endl;  
    465.     cout << "verify memory size" << endl;  
    466.     tmp = mem_pool->pfree_mem_chunk;  
    467.     free_size = 0;  
    468.     for (int k = 0; k < mem_pool->free_mem_chunk_count; k++)  
    469.     {  
    470.         free_size += tmp->pfree_mem_addr->count * MINUNITSIZE;  
    471.         tmp = tmp->next;  
    472.     }  
    473.     cout << "memory free size is " << free_size << " Byte" << endl;  
    474.     cout << "memory used size is " << mem_pool->mem_used_size << " Byte" << endl;  
    475.     cout << "********************* Get Memory Test (after Free) Finish *********************"<< endl << endl;  
    476. }  
    477. /************************************************************************/  
    478. /* 内存池性能测试代码 
    479.  * 固定大小 
    480.  /************************************************************************/  
    481. /* 
    482. void test_mem_pool_fix_size(PMEMORYPOOL mem_pool) 
    483. { 
    484.     int iter = 200000; 
    485.     int size = 512; 
    486.     double t1 = test_std_perf_fix_size(iter, size); 
    487.     double t2 = test_mem_pool_perf_1(mem_pool, iter, size); 
    488.     double t3 = test_mem_pool_perf_2(mem_pool, iter, size); 
    489.     double t4 = test_mem_pool_perf_3(mem_pool, iter, size); 
    490.     cout  << endl << endl  
    491.         << "test count: " << iter << ", test size: " << size << endl 
    492.         << "test result (system time / mem_pool time) : " << endl; 
    493.     cout << "test_mem_pool_perf_1:    " << t1 / t2 << endl 
    494.         << "test_mem_pool_perf_2: " << t1 / t3 << endl 
    495.         << "test_mem_pool_perf_3: " << t1 / t4 << endl; 
    496. } 
    497. */  
    498. /************************************************************************/  
    499. /* 内存池性能测试代码 
    500.   
    501.  * 随机大小,随机释放操作 
    502. /************************************************************************/  
    503. void rand_test()  
    504. {  
    505.     size_t sBufSize = 500* 1024*1024;  
    506.     void*pBuf = malloc(sBufSize);  
    507.     if (pBuf == NULL)  
    508.     {  
    509.         cout << "malloc failed" << endl;  
    510.         return;  
    511.     }  
    512.     PMEMORYPOOL mem_pool = CreateMemoryPool(pBuf, sBufSize);  
    513.     ofstream out("rand_test.txt");  
    514.     int iter = 2000;  
    515.     int* instruction = new int[iter];  
    516.     int* sizes = new int[iter];   
    517.     if (instruction == NULL || sizes == NULL)  
    518.     {  
    519.         cout << "new memory failed" << endl;  
    520.         return;  
    521.     }  
    522.     srand(time(NULL));   
    523.     cout << "generate rand number" << endl;  
    524.     // instruction 中元素为1时表示在GetMemory后执行FreeMemory,0表示不执行FreeMemory  
    525.     // sizes中是每次分配内存的大小,范围从64B~1024B  
    526.     for (int i = 0; i < iter; i++)  
    527.     {  
    528.         instruction[i] = rand() % 2;  
    529.         sizes[i] = (rand() % 16 + 1) * 64;  
    530.     }  
    531.     int test_count = 200;  
    532.     double t1, t2;  
    533.     double* ratio = new double[test_count];  
    534.     int count = 0;  
    535.     for (int k = 0; k < test_count; k++)  
    536.     {  
    537.         if (break_time != 0)  
    538.         {  
    539.             cout << "break @ " << k << " / " << test_count << endl;  
    540.             break;  
    541.         }  
    542.         count++;  
    543.         cout << "******************************************test " << k+1 << " *************************************************" << endl;  
    544.         t1 = test_std_perf(iter, sizes, instruction);  
    545.         t2 = test_mem_pool_perf_rand(mem_pool, iter,  sizes, instruction);  
    546.         cout << "total memory: " << mem_pool->size << ", memory used: " << mem_pool->mem_used_size   
    547.             << ", memory left: " << mem_pool->size - mem_pool->mem_used_size  << endl;  
    548.         ratio[k] = t1 / t2;  
    549.           
    550.     }  
    551.     if(break_time == 0)  
    552.         break_time = test_count;  
    553.     break_time = count - 1;  
    554.     cout << "*************************** ratio (system time / mem_pool time) ***************************" << endl;  
    555.     for (int k = 0; k < break_time; k++)  
    556.     {  
    557.         out << ratio[k] << ",";  
    558.         if (k % 10 == 0 && k != 0)  
    559.         {  
    560.             cout << endl;  
    561.         }  
    562.         cout << ratio[k] << " ";  
    563.     }  
    564.     cout << endl;  
    565.     delete []ratio;  
    566.     delete []instruction;  
    567.     delete []sizes;  
    568.     free(pBuf);  
    569. }  
    570. // 申请紧接着释放  
    571. void rand_test_2()  
    572. {  
    573.     size_t sBufSize = 500* 1024*1024;  
    574.     void*pBuf = malloc(sBufSize);  
    575.     if (pBuf == NULL)  
    576.     {  
    577.         cout << "malloc failed" << endl;  
    578.         return;  
    579.     }  
    580.     PMEMORYPOOL mem_pool = CreateMemoryPool(pBuf, sBufSize);  
    581.     int iter = 2000;  
    582.     int test_count = 511;  
    583.     int* sizes = new int[iter];   
    584.     double* ratio = new double[test_count];  
    585.     if (sizes == NULL || ratio == NULL)  
    586.     {  
    587.         cout << "new memory failed" << endl;  
    588.         return;  
    589.     }  
    590.     srand(time(NULL));   
    591.     cout << "generate rand number" << endl;  
    592.     ofstream out("rand_test_2.txt");  
    593.     for (int k = 0; k < test_count; k++)  
    594.     {  
    595.         for (int i = 0; i < iter; i++)  
    596.         {  
    597.             sizes[i] = (rand() % 16 + 1) * 64 + 1024 * k;  
    598.         }  
    599.         double mem_pool_t = test_mem_pool_perf_1(mem_pool, iter, sizes);  
    600.         double std_t = test_std_perf_1(iter, sizes);  
    601.           
    602.         ratio[k] = std_t / mem_pool_t;  
    603.     }  
    604.     cout << "*************************** ratio (system time / mem_pool time) ***************************" << endl;  
    605.     for (int k = 0; k < test_count; k++)  
    606.     {  
    607.         out << ratio[k] << ",";  
    608.         if (k % 10 == 0 && k != 0)  
    609.         {  
    610.             cout << endl;  
    611.         }  
    612.         cout << ratio[k] << " ";  
    613.     }  
    614.     cout << endl;  
    615.       
    616.     delete []sizes;  
    617.     delete ratio;  
    618.     free(pBuf);  
    619. }  
    620. int _tmain(int argc, _TCHAR* argv[])  
    621. {  
    622.     rand_test();  
    623. //  rand_test_2();  
    624.       
    625.     return 0;  
    626. }  
     

    大顶堆结构内存池:

    MemoryPool.h

    [cpp] view plain copy
    1. #ifndef _MEMORYPOOL_H  
    2. #define _MEMORYPOOL_H  
    3. #include <stdlib.h>  
    4. #define MINUNITSIZE 64  
    5. #define ADDR_ALIGN 8  
    6. #define SIZE_ALIGN MINUNITSIZE  
    7. #define MAXCHUNKSIZE 1024*1024*64  
    8. struct memory_chunk;  
    9. typedef struct memory_block  
    10. {  
    11.     size_t count;  
    12.     size_t start;  
    13.     memory_chunk* pmem_chunk;  
    14. }memory_block;  
    15. typedef struct memory_chunk  
    16. {  
    17.     size_t chunk_size;  
    18.     memory_block* pfree_mem_addr;  
    19. }memory_chunk;  
    20. typedef struct max_heap  
    21. {  
    22.     memory_chunk *heap;    
    23.     size_t maxSize;     
    24.     size_t currentSize;    
    25. }max_heap;  
    26. typedef struct MEMORYPOOL  
    27. {  
    28.     void *memory;  
    29.     size_t size;  
    30.     memory_block* pmem_map;   
    31.     max_heap heap;  
    32.     size_t mem_used_size; // 记录内存池中已经分配给用户的内存的大小  
    33.     size_t free_mem_chunk_count; // 记录 pfree_mem_chunk链表中的单元个数  
    34.     size_t mem_map_unit_count; //   
    35.     size_t mem_block_count; // 一个 mem_unit 大小为 MINUNITSIZE  
    36. }MEMORYPOOL, *PMEMORYPOOL;  
    37. /************************************************************************/  
    38. /* 生成内存池 
    39. * pBuf: 给定的内存buffer起始地址 
    40. * sBufSize: 给定的内存buffer大小 
    41. * 返回生成的内存池指针 
    42. /************************************************************************/  
    43. PMEMORYPOOL CreateMemoryPool(void* pBuf, size_t sBufSize);  
    44. /************************************************************************/  
    45. /* 暂时没用 
    46. /************************************************************************/  
    47. void ReleaseMemoryPool(PMEMORYPOOL* ppMem) ;   
    48. /************************************************************************/  
    49. /* 从内存池中分配指定大小的内存  
    50. * pMem: 内存池 指针 
    51. * sMemorySize: 要分配的内存大小 
    52. * 成功时返回分配的内存起始地址,失败返回NULL 
    53. /************************************************************************/  
    54. void* GetMemory(size_t sMemorySize, PMEMORYPOOL pMem) ;  
    55. /************************************************************************/  
    56. /* 从内存池中释放申请到的内存 
    57. * pMem:内存池指针 
    58. * ptrMemoryBlock:申请到的内存起始地址 
    59. /************************************************************************/  
    60. void FreeMemory(void *ptrMemoryBlock, PMEMORYPOOL pMem) ;  
    61. #endif //_MEMORYPOOL_H  
     

    MemoryPool.cpp

    [cpp] view plain copy
    1. #include <memory.h>  
    2. #include "MemoryPool.h"  
    3. /************************************************************************/  
    4. /* 以下为大顶堆操作*/                                                                          
    5. void init_max_heap(size_t max_heap_size, memory_chunk* heap_arr, max_heap* heap)  
    6. {  
    7.     heap->maxSize = max_heap_size;  
    8.     heap->currentSize = 0;  
    9.     heap->heap = heap_arr;  
    10. }  
    11. bool is_heap_empty(max_heap* heap)  
    12. {  
    13.     return heap->currentSize == 0;    
    14. }  
    15. bool is_heap_full(max_heap* heap)  
    16. {  
    17.     return heap->currentSize == heap->maxSize;    
    18. }  
    19. memory_chunk* filter_up(max_heap* heap, size_t start)  
    20. {  
    21.     size_t i = start;  
    22.     size_t j = ( i - 1 ) / 2;    
    23.     memory_chunk temp = heap->heap[i];    
    24.     while(i > 0)  
    25.     {    
    26.         if(temp.chunk_size <= heap->heap[j].chunk_size)  
    27.             break;    
    28.         else  
    29.         {             
    30.             heap->heap[i] = heap->heap[j];    
    31.             heap->heap[j].pfree_mem_addr->pmem_chunk = &(heap->heap[i]);  
    32.             i = j;    
    33.             j = (i - 1) / 2;    
    34.         }    
    35.     }    
    36.     heap->heap[i] = temp;    
    37.     return &(heap->heap[i]);  
    38. }  
    39. memory_chunk* filter_down(max_heap* heap, size_t start, size_t endOfHeap)  
    40. {  
    41.     size_t i = start;  
    42.     size_t j = i * 2 + 1;    
    43.     memory_chunk temp = heap->heap[i];    
    44.     while(j <= endOfHeap)  
    45.     {    
    46.         if(j < endOfHeap && heap->heap[j].chunk_size < heap->heap[j+1].chunk_size)  
    47.             j++;    
    48.         if(temp.chunk_size > heap->heap[j].chunk_size)  
    49.             break;    
    50.         else  
    51.         {    
    52.             heap->heap[i] = heap->heap[j];    
    53.             heap->heap[j].pfree_mem_addr->pmem_chunk = &(heap->heap[i]);  
    54.             i = j;    
    55.             j = 2 * i + 1;    
    56.         }    
    57.     }    
    58.     heap->heap[i] = temp;    
    59.     return &(heap->heap[i]);  
    60. }  
    61. memory_chunk* insert_heap(memory_chunk& chunk, max_heap* heap)  
    62. {  
    63.     if (is_heap_full(heap))  
    64.     {  
    65.         return NULL;  
    66.     }  
    67.     heap->heap[heap->currentSize] = chunk;  
    68.     memory_chunk* ret = filter_up(heap, heap->currentSize);  
    69.     heap->currentSize++;    
    70.     return ret;    
    71. }  
    72. bool get_max(memory_chunk*& chunk, max_heap* heap)  
    73. {  
    74.     if(is_heap_empty(heap))  
    75.     {    
    76.         return false;    
    77.     }    
    78.     chunk = heap->heap;    
    79.     return true;  
    80. }  
    81. bool remove_max(max_heap* heap)  
    82. {  
    83.     if(is_heap_empty(heap))  
    84.     {    
    85.         return false;    
    86.     }    
    87.     heap->heap[0] = heap->heap[heap->currentSize - 1];    
    88.     heap->currentSize--;    
    89.     if (heap->currentSize > 0)  
    90.     {  
    91.         filter_down(heap, 0, heap->currentSize-1);    
    92.     }  
    93.     return true;    
    94. }  
    95. void remove_element(memory_chunk* chunk, max_heap* heap)  
    96. {  
    97.     // 删除某个非max元素有两步组成:  
    98.     // 1. 将该元素size增至最大(大于max element),然后将其上移至堆顶;  
    99.     // 2. 删除堆顶元素  
    100.     size_t index = chunk - heap->heap;  
    101.     chunk->chunk_size = MAXCHUNKSIZE;  
    102.     filter_up(heap, index);  
    103.     remove_max(heap);  
    104. }  
    105. memory_chunk* increase_element_value(memory_chunk* chunk, max_heap* heap, size_t increase_value)  
    106. {  
    107.     size_t index = chunk - heap->heap;  
    108.     chunk->chunk_size += increase_value;  
    109.     return filter_up(heap, index);  
    110. }  
    111. memory_chunk* decrease_element_value(memory_chunk* chunk, max_heap* heap, size_t decrease_value)  
    112. {  
    113.     size_t index = chunk - heap->heap;  
    114.     chunk->chunk_size -= decrease_value;  
    115.     return filter_down(heap, index, heap->currentSize-1);  
    116. }  
    117. /************************************************************************/  
    118. /* 内存池起始地址对齐到ADDR_ALIGN字节 
    119. /************************************************************************/  
    120. size_t check_align_addr(void*& pBuf)  
    121. {  
    122.     size_t align = 0;  
    123.     size_t addr = (int)pBuf;  
    124.     align = (ADDR_ALIGN - addr % ADDR_ALIGN) % ADDR_ALIGN;  
    125.     pBuf = (char*)pBuf + align;  
    126.     return align;  
    127. }  
    128. /************************************************************************/  
    129. /* 内存block大小对齐到MINUNITSIZE字节 
    130. /************************************************************************/  
    131. size_t check_align_block(size_t size)  
    132. {  
    133.     size_t align = size % MINUNITSIZE;  
    134.       
    135.     return size - align;   
    136. }  
    137. /************************************************************************/  
    138. /* 分配内存大小对齐到SIZE_ALIGN字节 
    139. /************************************************************************/  
    140. size_t check_align_size(size_t size)  
    141. {  
    142.     size = (size + SIZE_ALIGN - 1) / SIZE_ALIGN * SIZE_ALIGN;  
    143.     return size;  
    144. }  
    145. /************************************************************************/  
    146. /* 内存映射表中的索引转化为内存起始地址                                                                     
    147. /************************************************************************/  
    148. void* index2addr(PMEMORYPOOL mem_pool, size_t index)  
    149. {  
    150.     char* p = (char*)(mem_pool->memory);  
    151.     void* ret = (void*)(p + index *MINUNITSIZE);  
    152.       
    153.     return ret;  
    154. }  
    155. /************************************************************************/  
    156. /* 内存起始地址转化为内存映射表中的索引                                                                     
    157. /************************************************************************/  
    158. size_t addr2index(PMEMORYPOOL me