如何用Cpp实现一个内存池

当需要频繁的进行new和delete操作时,可能会导致产生很多内存碎片。
所以用一个内存池来对这些空间进行管理,可以有效地提高内存利用率。
另外也可以用内存池和placement new来一块使用。
在STL中也有一个内存池的实现,还是非常巧妙的。在此学习并模仿着写一个。

简单设计

  • 用户申请的内存可能很小,可能很大,SGI STL中的做法是以128byte为分界线,分两种情况来处理,大于128byte的直接调用系统的malloc和free,小于128byte的统一用内存池来管理。
  • 因为内存碎片主要是由于小块内存分割了大块内存导致的,所以把小块内存统一管理就够了。
  • 我们把处理大于128的叫做一级空间配置器,小于128的叫做二级配置器。
  • 先看一级配置器,将其看成一个黑盒子的话,它需要给调用者提供这样几个接口:

    1
    2
    3
    4
    allocate 分配内存
    deallocate 回收内存
    reallocate 重新分配内存
    set_new_handler 用来处理内存不足的情况(二级配置器中不用再定义此函数,转来调用这个就好)
  • 一级配置器内部还得实现这样几个函数

    1
    2
    3
    oom_malloc malloc内存失败时的处理函数
    oom_realloc realloc内存失败时的处理函数
    __malloc_alloc_oom_handler 用户给制定的处理函数。
  • 二级配置器也得有下面几个public函数

    1
    2
    3
    allocate 分配内存
    deallocate 回收内存
    reallocate 重新分配内存
  • 二级配置器内部的内存也分为两种,一种是用链表管理起来的,一种是空闲着备用的。所以也需要下面两个函数

    1
    2
    refill 用来把“从空闲内存区申请到的内存”加到链表上
    chunk_alloc 负责从空闲内存区取内存的工作,负责内存池最核心的工作
  • 可以多加一个构造函数MemoryPool(size_t n),用来预先分配一些内存。

  • 二级配置器把内存按照8 16 24…总共16种情况来管理,每种情况都有一个链表结构把相应大小的内存给串起来。
  • 链表采用了下面这种结构,使用union联合体,可以尽可能的节省内存。
    1
    2
    3
    4
    5
    6
    7

    union obj{
    union obj *free_list_link;
    char client_data[1];
    }
    //这种结构的好处是,在内存空闲不用时,就把它当做obj*free_list_link来用,可以让它指向下一块内存,这样就能把空闲内存都串起来
    //当内存被申请后,当client_data来对待,可以全部用来储存数据,省去了传统链表所占用的空间,有效地利用了内存。

注释版代码

  • defaultmalloc.h

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    #ifndef DEFAULT_MALLOC
    #define DEFAULT_MALLOC

    #include <iostream>
    #include <cstdlib>
    #include <cstdio>
    using namespace std;

    //一级配置器,大于128的直接调用malloc和free
    class DefaultMalloc{
    public:
    static void * allocate(size_t n);
    static void * deallocate(void *p,size_t n);
    static void * reallocate(void *p,size_t old_sz,size_t new_sz);
    static void (*set_malloc_handler(void (*f)()))();
    private:
    static void *oom_malloc(size_t n);
    static void *oom_realloc(void *p,size_t n);
    static void (* __malloc_alloc_oom_handler)();
    };

    //初始化函数指针(static成员变量要在类外初始化)
    void (*DefaultMalloc::__malloc_alloc_oom_handler)()=0;

    //分配内存,直接调用malloc
    void * DefaultMalloc::allocate(size_t n){
    void *result=malloc(n);
    if(result==0) result=oom_malloc(n);
    return result;
    }

    //释放内存
    void * DefaultMalloc::deallocate(void *p,size_t n){
    free(p);
    }

    //重新分配内存
    void * DefaultMalloc::reallocate(void *p,size_t old_sz,size_t new_sz){
    void * result=realloc(p,new_sz);
    if(result==0) result=oom_realloc(p,new_sz);
    return result;
    }

    //设置内存不在时的处理函数
    void (*DefaultMalloc::set_malloc_handler(void (*f)()))(){
    void (*old)()=__malloc_alloc_oom_handler;
    __malloc_alloc_oom_handler=f;
    return old;
    }

    //malloc失败时调用此函数
    void * DefaultMalloc::oom_malloc(size_t n){
    void (*my_malloc_handler)();
    void *result;
    for(;;){
    my_malloc_handler=__malloc_alloc_oom_handler;
    if(my_malloc_handler==0) exit(-1);
    (*my_malloc_handler)();
    result=malloc(n);
    if(result) return result;
    }
    }

    //realloc失败时调用此函数
    void * DefaultMalloc::oom_realloc(void *p,size_t n){
    void (*my_malloc_handler)();
    void *result;
    for(;;){
    my_malloc_handler=__malloc_alloc_oom_handler;
    if(my_malloc_handler==0) exit(-1);
    (*my_malloc_handler)();
    result=realloc(p,n);
    if(result) return result;
    }
    return result;
    }

    \#endif
  • memorypool.h

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    #ifndef MEMORY_POOL
    #define MEMORY_POOL
    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include "defaultmalloc.h"
    using namespace std;

    enum{__ALIGN=8};
    enum{__MAX_BYTES=128};
    enum{__NUM_FREELISTS=16};

    //二级配置器,当函数小于128bytes时,使用此类来管理内存
    class MemoryPool{
    public:
    MemoryPool(){}; //无参构造
    MemoryPool(size_t n); //带参构造,可以先给内存池分配n个bytes
    static void * allocate(size_t n);
    static void deallocate(void *p,size_t n);
    static void * reallocate(void *p,size_t old_sz,size_t new_sz);

    private:
    //链表的union,用来串联每块内存
    union obj{
    union obj *free_list_link;
    char data[1];
    };
    //向上取到8的整数倍
    static size_t ROUND_UP(size_t bytes){
    return ( (bytes+__ALIGN-1) & ~(__ALIGN-1) );
    }
    //分了16个规格来管理内存,分别是8 16...128,此函数用来判断此次申请的bytes个字节要到哪个规格的链表去申请内存
    static size_t FREELIST_INDEX(size_t bytes){
    return ( (bytes+__ALIGN-1)/__ALIGN -1 );
    }

    //当链表上的空间不足时,refill会调用chunk_alloc向内存池申请空间,连到链表上
    static void *refill(size_t n);
    //用来向内存池申请空间,执行具体的操作
    static char *chunk_alloc(size_t size,int &objs);//此处要用引用

    //长度为16的链表,用来管理内存
    static obj * volatile free_list[__NUM_FREELISTS];
    //用来标示内存池的起止位置,这里面是未被链表连起来的内存,链表上的内存不够用时,会从这块内存池中申请内存
    static char *start_free,*end_free;
    //内存池申请到的总空间大小,包括被free_list串起来的。
    static size_t heap_size;
    };

    MemoryPool::obj * volatile MemoryPool::free_list[__NUM_FREELISTS]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
    char* MemoryPool::start_free=0;
    char* MemoryPool::end_free=0;
    size_t MemoryPool::heap_size=0;

    MemoryPool::MemoryPool(size_t n){
    start_free=(char*)DefaultMalloc::allocate(n);
    end_free=start_free+n;
    heap_size=n;
    }

    void * MemoryPool::allocate(size_t n){
    obj * volatile * my_free_list;
    obj * result;
    //当申请的内存大于128bytes或小于等于0,直接调用一级配置器,即malloc
    if(n > (size_t)__MAX_BYTES || n<=0){
    return (DefaultMalloc::allocate(n));
    }
    //找到长度为n的内存要从第几个链表上来申请
    my_free_list=free_list+FREELIST_INDEX(n);
    result=*my_free_list;
    //如果链表上没有相应大小的内存了,就调用refill从内存池申请
    if(result==0){
    void *r=refill(ROUND_UP(n));
    return r;
    }
    *my_free_list=result->free_list_link;
    return result;
    }

    void MemoryPool::deallocate(void *p,size_t n){
    obj * volatile * my_free_list;
    obj *q=(obj*)p;
    if(n > (size_t)__MAX_BYTES || n<=0){
    DefaultMalloc::deallocate(p,n);
    return ;
    }
    my_free_list=free_list+FREELIST_INDEX(n);
    //将p指向的内存归还到相应的链表上
    q->free_list_link=*my_free_list;
    *my_free_list=q;
    }

    void * MemoryPool::reallocate(void *p,size_t old_sz,size_t new_sz){
    void * result;
    size_t copy_size;
    if(old_sz > (size_t)__MAX_BYTES || new_sz<=0 || old_sz<=0){
    return (DefaultMalloc::reallocate(p,old_sz,new_sz));
    }
    if(ROUND_UP(old_sz) == ROUND_UP(new_sz)) return p;
    result=allocate(new_sz);
    copy_size=new_sz>old_sz ? old_sz : new_sz;
    //申请完新内存之后,把旧地址的数据复制到新地址
    memcpy(result,p,copy_size);
    deallocate(p,old_sz);
    return result;
    }

    void * MemoryPool::refill(size_t n){
    //默认每次返回20个长度为n的块,其中返回给用户一块,剩下的连到相应大小的链表上。
    int nobjs=20;
    //从内存池中申请20块大小为n的内存。
    char * chunk=chunk_alloc(n,nobjs);
    obj * volatile * my_free_list;
    obj *result,*current_obj,*next_obj;
    //上面chunk_alloc中的nobjs是引用传值,可能会改变nobjs的值。
    if(nobjs==1) return chunk;
    my_free_list=free_list+FREELIST_INDEX(n);
    result=(obj*)chunk;
    *my_free_list=next_obj=(obj*)(chunk+n);
    //把剩余的块都连到链表上
    for(int i=1;;i++){
    current_obj=next_obj;
    next_obj=(obj*)((char*)current_obj+n);
    if((i+1)==nobjs){
    current_obj->free_list_link=0;
    break;
    }else{
    current_obj->free_list_link=next_obj;
    }
    }
    return result;
    }
    char * MemoryPool::chunk_alloc(size_t size,int &objs){
    char *result;
    //计算要申请到内存总数
    size_t total_bytes=size*objs;
    //计算内存池中未管理的内存还有多少
    size_t bytes_left=end_free-start_free;
    //如果剩余内存足够申请20块内存
    if(bytes_left>=total_bytes){
    result=start_free;
    start_free+=total_bytes;
    return result;
    //如果不够20块,但是能提供一块或以上
    }else if(bytes_left>=size){
    objs=bytes_left/size;
    total_bytes=size*objs;
    result=start_free;
    start_free+=total_bytes;
    return result;
    //如果一块都提供不了,就需要另想办法了
    }else{
    //内存池不够了就从堆中申请,从堆中申请的数量这样计算:
    //要申请的大小的2倍+一个随申请次数增大的值
    //(heap_size一直记录申请内存总数,右移四位相当于除以16,应该是有十六个规格的原因?
    size_t bytes_to_get=total_bytes*2+ROUND_UP(heap_size>>4);
    //如果剩余内存无法提供一块size,但是还剩下一点,就先把这个块内存连到链表上
    if(bytes_left>0){
    obj * volatile * my_free_list=free_list+FREELIST_INDEX(bytes_left);
    ((obj*)start_free)->free_list_link=*my_free_list;
    *my_free_list=(obj*)start_free;
    }
    //向堆中再申请新的内存
    start_free=(char*)malloc(bytes_to_get);
    //如果堆中内存也没了
    if(0==start_free){
    obj *volatile * my_free_list,*p;
    //再遍历一下链表,看被管理起来的内存中有没有能够本次使用的
    for(int i=size;i<=__MAX_BYTES;i+=__ALIGN){
    my_free_list=free_list+FREELIST_INDEX(i);
    p=*my_free_list;
    if(p!=0){
    *my_free_list=p->free_list_link;
    start_free=(char*)p;
    end_free=start_free+i;
    //再递归调用自身,看刚回收的那点内存能使用不
    return chunk_alloc(size,objs);
    }
    }
    end_free=0;
    start_free=(char*)DefaultMalloc::allocate(bytes_to_get);
    }
    heap_size+=bytes_to_get;
    end_free=start_free+bytes_to_get;
    //如果从堆中申请到了内存,再递归调用自身
    return chunk_alloc(size,objs);
    }
    }
    \#endif
  • test.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <cstdlib>
#include <vector>
#include <ctime>
#include "memorypool.h"
using namespace std;
//#define USEPOOL

int main(){
MemoryPool pool(10);
clock_t start,end;
int sum=0;
vector<int> randnum(20005);
for(int i=0;i<20000;i++){
randnum[i]=rand()%128;
}

#ifdef USEPOOL
for(int i=0;i<80;i++){
start=clock();
for(int i=0;i<20000;i++){
char *p=(char*)pool.allocate(randnum[i]);

pool.deallocate(p,randnum[i]);
}
end=clock();
sum+=(end-start);
}
cout<<"MemoryPool:20000次申请释放内存(0-128bytes)用时:"<<sum/80<<"毫秒"<<endl;
#else
sum=0;
for(int i=0;i<80;i++){
start=clock();
for(int i=0;i<20000;i++){
char *p=(char*)malloc(randnum[i]);
free(p);
}
end=clock();
sum+=(end-start);
}
cout<<"原生api:20000次申请释放内存(0-128bytes)用时:"<<sum/80<<"毫秒"<<endl;

#endif

return 0;
}

存在问题

  • 基本按照STL中的空间配置器来实现的,但测试发现不如直接调用malloc和free速度快,是否内存池主要是解决内存碎片的问题,而速度上可能不会带来多大提升?
  • 在多线程环境下如何改进

参考

  • 《STL源码剖析》

欢迎与我分享你的看法。
转载请注明出处:http://taowusheng.cn/