当前位置:威尼斯 > 威尼斯人登录网站 > 通过对申请空间小而申请频繁的对象进行有效管

通过对申请空间小而申请频繁的对象进行有效管

文章作者:威尼斯人登录网站 上传时间:2019-09-27

有了tcmalloc和jemalloc,在大多数情况下我们都没有必要再自己写通用的内存分配器(应该说对于极大多数的程序员,都不可能写出比这

介绍:

stl中的空间配置器,stl空间配置器

 一般我们习惯的c++内存配置如下

class Foo { ... };
Foo* pf = new Foo; 
delete pf; 

 这里的new实际上分为两部分执行。首先是先用::operator new配置内存,然后执行Foo::Foo()构造对象内容。delete也一样,先运行Foo::~Foo()析构对象,再用::operator delete释放内存。在SGI STL中,这两部分分别在<stl_alloc.h>和<stl_construct.h>中。本文讲的便是<stl_alloc.h>中的故事。
  SGI STL中将配置器分为两级。第一级直接用malloc和free管理内存,第二级则使用内存池以避免内存碎片。这两级都由simple_alloc包装起来以符合stl标准。如图

威尼斯 1

第一级由于没有用operator new,所以要自己实现new-handler机制。我仿写的代码如下

 1 #ifndef _MALLOC_ALLOC_H_ 
 2 #define _MALLOC_ALLOC_H_ 
 3 
 4 //定义内存不足又没有定义相关处理函数时抛出的异常
 5 #ifndef THROW_OOM
 6 #    include <stdio.h>
 7 #    include <stdlib.h>
 8 #    define THROW_OOM fprintf(stderr, "out of memoryn"); exit(1)
 9 #endif
10 
11 #include<stdlib.h>
12 
13 namespace Chenstl{
14 
15 //第一级空间配置器,直接用mallloc分配内存
16 //当需要分配的空间大于MAX_BYTES时使用
17     class malloc_alloc{
18     private:
19         static void *oom_malloc(size_t);    //声明时可以只写类型啊。。现在才知道
20         static void *oom_realloc(void *,size_t);
21         static void (* malloc_oom_handler)();    //处理malloc时内存不足时的函数指针
22     public:
23         static void *allocate(size_t n);
24         static void decllocate(void *p);
25 
26         static void *realloc(void *p, size_t new_sz);
27         //当内存不足时,需要客户端设置handler
28         static void set_malloc_oom_handler(void(*f)());
29     };    
30 }
31 
32 #endif

 

威尼斯 2 1 #include "malloc_alloc.h" 2 3 using namespace Chenstl; 4 void *malloc_alloc::allocate(size_t n) 5 { 6 void *result = malloc(n); 7 if (0 == result) result = oom_malloc(n); 8 return result; 9 } 10 11 void malloc_alloc::decllocate(void *p) 12 { 13 free(p); 14 } 15 16 void * malloc_alloc::realloc(void *p, size_t new_sz) 17 { 18 void *result = realloc(p, new_sz); 19 if (0 == result) result = oom_realloc(p, new_sz); 20 return result; 21 } 22 23 //当内存不足时,需要客户端设置handler 24 void malloc_alloc::set_malloc_oom_handler(void(*f)()) 25 { 26 malloc_oom_handler = f; 27 } 28 29 void(*malloc_alloc::malloc_oom_handler)() = 0; 30 31 void *malloc_alloc::oom_malloc(size_t n) 32 {//不断试图获得内存 33 void *result; 34 for (;;) //据说这样比while(1)效果更优 35 { 36 if (0 == malloc_oom_handler) THROW_OOM; 37 (*malloc_oom_handler)(); 38 result = malloc(n); 39 if (result) return result; 40 } 41 } 42 43 void *malloc_alloc::oom_realloc(void *p, size_t n) 44 { 45 void *result; 46 for (;;) 47 { 48 if (0 == malloc_oom_handler) THROW_OOM; 49 (*malloc_oom_handler)(); 50 result = realloc(p, n); 51 if (result) return result; 52 } 53 } malloc_alloc.cpp

  如果需要的区块超过128bytes则用第一级,否则用第二级的内存池管理。为了便于管理,配置器会自动将内存需求量上调到8的倍数(要求20bytes时,自动调整为24bytes)。用16个freelist管理内存池,为节省空间,使用union

union obj {   //free-lists的节点构造 
   union obj *next;
   char client[1];  //使用者可见
  };

 获取内存时的代码及步骤如下

威尼斯 3void *default_alloc::allocate(size_t n) { obj *result = 0; obj **my_free_list = 0; if (n > MAX_BYTES) return malloc_alloc::allocate(n); //寻找free lists中合适的一个 my_free_list = free_list + FREELIST_INDEX(n); result = *my_free_list; if(0 == result) {//没有找到可用的freelist,从内存池里取出空间 return refill(ROUND_UP(n)); } //调整freelist *my_free_list = result->next; return result; } View Code

 威尼斯 4

  当free list中没有可用区块时,调用refill()为free list填充空间,新的空间取自内存池(由chunk_alloc()完成)。如果内存池不够,则malloc之,如果系统heap空间也不够,chunk_alloc()就寻找还有空闲区块的free list并将其内存充公,如果还是不够就调用第一级配置器。第一级配置器有实现new-handler机制,内存不够会抛出异常。

 

威尼斯 5#ifndef _DEFAULT_ALLOC_H #define _DEFAULT_ALLOC_H namespace Chenstl{ //使用内存池以减少碎片 class default_alloc { private: enum { ALIGN = 8}; enum { MAX_BYTES = 128 }; enum { NFREELISTS = 16 }; //static const int ALIGN = 8; //static const int MAX_BYTES = 128; //static const int NFREELISTS = 16; //MAX_BYTES/ALIGN union obj { //free-lists的节点构造 union obj *next; char client[1]; }; //freelist static obj *free_list[NFREELISTS]; static char *start_free; //内存池的起始位置 static char *end_free; //内存池的终止位置 static size_t heap_size; private: //将bytes上调至8的倍数 static size_t ROUND_UP(size_t bytes) { return ((bytes +ALIGN - 1) & ~(ALIGN - 1)); } //获取合适的区块在freelist中的位置 static size_t FREELIST_INDEX(size_t __bytes) { return (((__bytes)+(size_t)ALIGN

  • 1) / (size_通过对申请空间小而申请频繁的对象进行有效管理,delete释放内存威尼斯。t)ALIGN - 1); } //返回一个大小为n的对象,并可能加入大小为n的其他区块到free-list static void *refill(size_t n); //配置一大块空间,可容纳nobjs个大小为size的区块 //如果配置nobjs个区块有所不便,nobjs可能会降低 static char *chunk_alloc(size_t size, int &nobjs); public: static void *allocate(size_t n); static void deallocate(void *p, size_t n); static void *realloc(void *p, size_t old_sz, size_t new_sz); }; } #endif default_alloc.h

 

威尼斯 6#include "default_alloc.h" #include "malloc_alloc.h" using namespace Chenstl; default_alloc::obj *default_alloc::free_list[NFREELISTS] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, }; char *default_alloc::start_free = 0; //内存池的起始位置 char *default_alloc::end_free = 0; //内存池的终止位置 size_t default_alloc::heap_size = 0; void *default_alloc::allocate(size_t n) { obj *result = 0; obj **my_free_list = 0; if (n > MAX_BYTES) return malloc_alloc::allocate(n); //寻找free lists中合适的一个 my_free_list = free_list + FREELIST_INDEX(n); result = *my_free_list; if(0 == result) {//没有找到可用的freelist,从内存池里取出空间 return refill(ROUND_UP(n)); } //调整freelist *my_free_list = result->next; return result; } void default_alloc::deallocate(void *p, size_t n) { } //返回一个大小为n的对象,并可能加入大小为n的其他区块到freelist //在ANSI c中,void *不允许进行加减操作,所以chunk用char * void *default_alloc::refill(size_t n) { int objs = 20; char *chunk = chunk_alloc(n, objs); obj *next, *current; obj *result; obj **my_free_list; if (1 == objs) //只取出一个区块 return chunk; my_free_list = free_list + FREELIST_INDEX(n); result = (obj *)chunk; //这一块返回给客户端 //将freellist指向分配的区域 *my_free_list = next = (obj *)chunk + n; for (int i = 1;; i++) { current = next; next = (obj *)((char *)next + n); //这里注意不能直接用next+n if (i == objs - 1) { current->next = 0; break; } else current->next = next; } return result; } char *default_alloc::chunk_alloc(size_t size, int &nobjs) { char *result = 0; size_t total_bytes = size*nobjs; size_t bytes_left = end_free

  • start_free; //内存池剩余空间 if (bytes_left >= total_bytes) {//内存池足够提供所需内存 result = start_free; start_通过对申请空间小而申请频繁的对象进行有效管理,delete释放内存威尼斯。free += total_bytes; return result; } else if (bytes_left >= size) {//内存池足够供应一个以上的区块 nobjs = bytes_left / size; total_bytes = nobjs * size; result = start_free; start_free += total_bytes; return result; } else {//内存池一块区块也供应不了 size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);; if (bytes_left>0) {//将内存池的零头分配给合适的freelist obj **my_free_list = free_list + FREELIST_INDEX(bytes_left); ((obj *)start_free)->next = *my_free_list; *my_free_list = (obj *)start_free; } start_free = (char *)malloc(bytes_to_get); if (!start_free) {//系统堆内存不足,寻找还未使用的freelist obj *p = 0; obj **my_free_list = 0; for (int i = size; i < MAX_BYTES; ++i) { my_free_list = free_list + FREELIST_INDEX(i); p = *my_free_list; if (0 != p) {//还有未使用的freelist start_free = (char *)p; *my_free_list = p->next; end_free = start_free + i; //递归调用,修正nobjs return chunk_alloc(size, nobjs); } } //没内存可用,寄希望于第一级的new-handler或抛出异常 end_free = 0; start_free = (char *)malloc_alloc::allocate(bytes_to_get); } heap_size += bytes_to_get; end_free = start_free + bytes_to_get; return chunk_alloc(size, nobjs);//递归调用,修正nobjs } } default_alloc.cpp

 

一般我们习惯的c++内存配置如下 class Foo { ... };Foo * pf = new Foo; delete pf; 这里的new实际上分为两部分执行。...

个两个更好的通用内存分配器)。但是,如果对性能有极致的要求,写一个比通用内存分配器效率更高的池式对象分配器是可能的。

       设计内存池的目标是为了保证服务器长时间高效的运行,通过对申请空间小而申请频繁的对象进行有效管理,减少内存碎片的产生,合理分配管理用户内存,从而减少系统中出现有效空间足够,而无法分配大块连续内存的情况。

一个最简单也高效的实现就是freelist,每次分配的时候从freelist中get一个,释放的时候put回去就好了。其实现在单线程下是相当简单的,

目标:

也就几十行代码。但是在多线程的环境下,问题稍微复杂一点,因为可能有多个线程需要操作freelist,那么就要用锁去保护这个freelist,每次

    此次设计内存池的基本目标,需要满足线程安全性(多线程),适量的内存泄露越界检查,运行效率不太低于malloc/free方式,实现对4-128字节范围内的内存空间申请的内存池管理(非单一固定大小对象管理的内存池)。

get和put的时候都要加锁显然会导致freelist的操作效率低下.

内存池技术设计与实现

我在 block_obj_allocator 中利使用了线程本地存储来减

    本内存池的设计方法主要参考SGI的alloc的设计方案,为了适合一般的应用,并在alloc的基础上做一些简单的修改。

少锁的使用,其核心思想是,每个线程都有一个本地的freelist,get和put操作的都是本地的freelist,当本地freelist为空时,向一个全局的freelist

    Mempool的内存池设计方案如下(也可参考候捷《深入剖析STL》)

,请求一大块的内存,这个时候需要锁操作。在执行put的时候,如果收集了一定数量的对象,就一次性将一定数量的对象返还给全局freelist,

    从系统申请大块heap内存,在此内存上划分不同大小的区块,并把具有相同大小的区块连接起来,组成一个链表。比如A大小的块,组成链表L,当申请A大小 时,直接从链表L头部(如果不为空)上取到一块交给申请者,当释放A大小的块时,直接挂接到L的头部。内存池的原理比较简单,但是在具体实现过程中大量的 细节需要注意。

这个时候也需要锁操作。下面提出另外一种实现方式,这个实现要更简单,其核心思想就是对象由谁分配就由谁负责释放。

    1:字节对齐。

    struct obj_block    {        struct dnode node;        struct llist freelist;        lockfree_stack_t que;        pthread_t       thdid;//·ÖÅäÏ̵߳Äid        char   buf[0];    };        struct obj_slot    {        struct lnode node;        struct obj_block *block;        char buf[0];    };

    为了方便内存池中对象的管理,需要对申请内存空间的进行调整,在Mempool中,字节对齐的大小为最接近8倍数的字节数。比如,用户申请5个字节,Mempool首先会把它调整为8字节。比如申请22字节,会调整为24,对比关系如下

obj_block是一个内存块管理器,当对象池中没有对象时,就分配一个obj_block,然后将buf中的内存分成一个个单独的obj_slot

序号

对齐字节

范围

0

8

1-8

1

16

9-16

2

24

17-24

3

32

25-32

4

40

33-40

5

48

41-48

6

56

49-56

7

64

57-64

8

72

65-72

9

80

73-80

10

88

81-88

11

96

89-96

12

104

97-104

13

112

105-112

14

120

113-120

15

128

121-128

添加到obj_block的freelist中.obj_block中记录了分配线程的线程id,保存在thdid变量中.

(图1)

    struct pth_allocator    {        lockfree_stack que;        uint32_t free_block_size;        struct dlist free_blocks;        struct dlist recy_blocks;    };            struct obj_allocator{        struct allocator base;        uint32_t alloc_size;        uint32_t objsize;        uint16_t tls_type;        pthread_key_t pkey;    };

对于超过128字节的申请,直接调用malloc函数申请内存空间。这里设计的内存池并不是对所有的对象进行内存管理,只是对申请内存空间小,而申 请频繁的对象进行管理,对于超过128字节的对象申请,不予考虑。这个需要与实际项目结合,并不是固定不变的。实现对齐操作的函数如下

pth_allocator是一个每线程的管理结构,free_block_size记录了当前管理结构可供分配的obj_block的数量,所有可供分配的obj_block

static size_t round_up(size_t size)
{
        return (((size)+7) &~ 7);// 按8字节对齐
}

被添加到free_blocks中,而recy_blocks中保存了已经没有可分配对象的obj_block.分配过程是从free_blocks的表头中获得一个obj_block,

2:构建索引表

然后从obj_block的freelist中弹出一个空闲的对象,分配出去.如果分配之后obj_block的freelist为空,则将obj_block从free_blocks中弹

内存池中管理的对象都是固定大小,现在要管理0-128字节的范围内的对象申请空间,除了采用上面提到的字节对齐外,还需要变通一下,这就是建立索引表,做法如下;
static _obj*  free_list[16];
创建一个包含16个_obj*指针的数组,关于_obj结构后面详细讲解。free_list[0]记录所有空闲空间为8字节的链表的首地 址;free_list[1]对应16字节的链表,free_list[2]对应24字节的列表。free_list中的下标和字节链表对应关系参考图1 中的“序号”和“对齐字节”之间的关系。这种关系,我们很容易用算法计算出来。如下

出,添加到recy_blocks中.

static size_t freelist_index(size_t size)
{
        return (((size)+7)/7-1);// 按8字节对齐
}

这个设计的关键在que,它是一个无锁算法实现的栈,这里之所以使用栈,首先,我们不需要关注释放的顺序,其次无锁栈的实现最简单,

    所以,这样当用户申请空间A时,我们只是通过上面简单的转换,就可以跳转到包含A字节大小的空闲链表上,如下;
_obj** p = free_list[freelist_index(A)];

开销最小.

3:构建空闲链表

如果释放线程与分配线程不是同一个线程,则将要释放的对象push到que中,由分配线程在以后的某个时间里从que中取出,然后

通过索引表,我们知道mempool中维持着16条空闲链表,这些空闲链表中管理的空闲对象大小分别为8,16,24,32,40…128。这些空闲链表链接起来的方式完全相同。一般情况下我们构建单链表时需要创建如下的一个结构体。

放回到free_list中,释放部分的代码如下:

struct Obj
{
    Obj *next;
    Char* p;
    Int iSize;
}

    void obj_dealloc(struct allocator *allo ,void *ptr)    {        obj_allocator_t _allo = (obj_allocator_t)allo;        struct obj_slot *obj = (struct obj_slot*)((char*)ptr - sizeof(struct obj_slot));            if(obj->block->thdid == pthread_self{            struct pth_allocator *pth = (struct pth_allocator*)pthread_getspecific(_allo->pkey);;            if(unlikely(!pth))                abort();            __dealloc(_allo,pth,obj);        }        else            lfstack_push(obj->block->que,(struct lnode*)obj);    }

next指针指向下一个这样的结构,p指向真正可用空间,iSize用于只是可用空间的大小,在其他的一些内存池实现中,还有更复杂的结构体,比如 还包括记录此结构体的上级结构体的指针,结构体中当前使用空间的变量等,当用户申请空间时,把此结构体添加的用户申请空间中去,比如用户申请12字节的空 间,可以这样做

再来看下分配的实现:

Obj *p = (Obj*)malloc(12+sizeof(Obj));
p->next = NULL;
p->p = (char*)p+sizeof(Obj);
p->iSize = 12;

    void* obj_alloc(struct allocator *allo,int32_t size)    {        obj_allocator_t _allo = (obj_allocator_t)allo;        struct pth_allocator *pth = (struct pth_allocator*)pthread_getspecific(_allo->pkey);        if(unlikely(!pth))        {            pth = new_pth;            pthread_setspecific(_allo->pkey,pth);        }        if(unlikely(dlist_empty(&pth->free_blocks)))        {            struct lnode *n;            while((n = lfstack_pop(&pth->que)) != NULL)                __dealloc(_allo,pth,(struct obj_slot*)n);                    }else            return __alloc(_allo,pth);        if(unlikely(dlist_empty(&pth->free_blocks)))            __expand(_allo,pth);        return __alloc(_allo,pth);    }

但是,我们并没有采用这种方式,这种方式的一个缺点就是,用户申请小空间时,内存池加料太多了。比如用户申请12字节时,而真实情况是内存池向内存 申请了12+ sizeof(Obj)=12+12=24字节的内存空间,这样浪费大量内存用在标记内存空间上去,并且也没有体现索引表的优势。Mempool采用的是 union方式

首先看下本地是否有可供分配的对象,如果有直接调用__alloc分配,如果本地没有则看下que里有没有其线程释放的对,如果有将这些对象回收到本地
的free_list中,接着再次查看本地是否有可供分配的对象,如果还是没有调用__expand分配一块内存,创建新的对象,然后再调用__alloc分配.

union Obj
{
    Obj *next;
    char client_data[1];
}

分配器的完整代码,使用方式参看asynserver

这里除了把上面的struct修改为union,并把int iSize去掉,同时把char*p,修改为char client_data[1],并没有做太多的修改。而优势也恰恰体现在这里。如果采用struct方式,我们需要维护两条链表,一条链表是,已分配内存 空间链表,另一条是未分配(空闲)空间链表。而我们使用索引表和union结构体,只需要维护一条链表,即未分配空间链表。具体如下

索引表的作用有两条1:如上所说,维护16条空闲链表2:变相记录每条链表上空间的大小,比如下标为3的索引表内维持着是大小为24字节的空闲链表。这样我们通过索引表减少在结构体内记录p所指向空间大小的iSize变量。从而减少4个字节。

Union的特性是,结构内的变量是互斥存在的。再运行状态下,只是存在一种变量类型。所以在这里sizeof(Obj)的大小为4,难道这里我们也需要把这4字节也加到用户申请空间中去嘛?其实不是,如果这样,我们又抹杀了union的特性。

当我们构建空闲分配链表时,我们通过next指向下一个union结构体,这样我们不使用p指针。当把这个结构体分配出去时,我们直接返回 client_data的地址,此时client_data正好指向申请空间的首字节。所以这样,我们就不用在用户申请空间上添加任何东西。

威尼斯 7威尼斯 8
图2

    Obj的连接方式如上所示,这样我们无需为用户申请空间添加任何内容。   

4:记录申请空间字节数

如果采用面向对象方式,或者我们在释放内存池的空间时能够明确知道释放空间的大小,无需采用这种方式。

威尼斯 9
图3

在C语言中的free没有传递释放空间大小,而可以正确释放,在这里也是模仿这种方式,采用这种记录申请空间大小的方式去释放内存。用户申请空 间+1操作将在字节对齐之前执行,找到合适空间后,把首字节改写为申请空间的大小,当然1个字节最多纪录256个数,如果项目需要,可以设置为short 类型或者int类型,不过这样就需要占用用户比较大的空间。当释放内存空间时,首先读取这个字节,获取空间大小,进行释放。为了便于对大于128字节对象 的大小进行合适的释放,同时也对大于128字节的内存申请,添加1字节记录大小。所以现在这里限制了用户内存申请空间不得大于255字节,不过现在已经满 足项目要求。当然也可以修改为用short类型记录申请空间的大小。

    // 申请
    *(( unsigned char *)result) = (size_t)n;
    unsigned char * pTemp = (unsigned char*)result;
    ++pTemp;
    result = (_obj*)pTemp;
    return result;

    // 释放
    unsigned char * pTemp = (unsigned char *)ptr;
    --pTemp;
    ptr = (void*)pTemp;
    n = (size_t)(*( unsigned char *)ptr);

5:内存池的分配原理

在内存池的设计中,有两个重要的操作过程1:chunk_alloc,申请大块内存,2:refill回填操作,内存池初始化化时并不是为索引表中 的每一项都创建空闲分配链表,这个过程会推迟到,只有用户提取请求时才会创建这样的分配链表。详细参考如下代码(在sgi中stl_alloc.h文件中 你也可以看到这两个函数),主要步骤在注释中已经说明。

/**
* @bri: 申请大块内存,并返回size*(*nobjs)大小的内存块
* @param: size,round_up对齐后的大小,nobjs
* @return: 返回指向第一个对象内存指针
*/
static char* chunk_alloc(size_t size, int *nobjs)
{
     /**< 返回指针 */
     char* __result;
     /**< 申请内存块大小 */
     size_t __total_bytes = size *(*nobjs);
     /**< 当前内存可用空间 */
     size_t __bytes_left = _end_free - _start_free;

     /**< 内存池中还有大片可用内存 */
     if (__bytes_left >= __total_bytes)
     {
         __result = _start_free;
         _start_free += __total_bytes;
         return (__result);
     }
     /**< 至少还有一个对象大小的内存空间 */
     else if (__bytes_left >= size)
     {
         *nobjs = (int)(__bytes_left/size);
         __total_bytes = size * (*nobjs);
         __result = _start_free;
         _start_free += __total_bytes;
         return (__result);
     }
     /**< 内存池中没有任何空间 */
     else
     {
         /**< 重新申请内存池的大小 */
         size_t __bytes_to_get = 2 * __total_bytes + round_up(_heap_size >> 4);
         /**< 把内存中剩余的空间添加到freelist中 */
         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);
         /*=======================================================================*/
         memset(_start_free,0,__bytes_to_get);
         /*=======================================================================*/
         // 系统内存已经无可用内存,那么从内存池中压缩内存
         if(0 == _start_free)
         {
              size_t __i;
              _obj *VOLATILE* __my_free_list;
              _obj *__p;
              /**< 从freelist中逐项检查可用空间(此时只收集比size对象大的内存空间) */
              for (__i = size; __i <= (size_t)__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,nobjs));
                   }
              }
              _end_free = 0;
              /**< 再次申请内存,可能触发一个异常 */
              _start_free = (char*)malloc(__bytes_to_get);
         }
         /**< 记录当前内存池的容量 */
         _heap_size += __bytes_to_get;
         _end_free = _start_free + __bytes_to_get;
         return (chunk_alloc(size,nobjs));
     }
}

/*=======================================================================*/
/**
 * @bri: 填充freelist的连接,默认填充20个
 * @param: __n,填充对象的大小,8字节对齐后的value
 * @return: 空闲
 */
static void* refill(size_t n)
{
     int __nobjs = 20;
     char* __chunk = (char*)chunk_alloc(n, &__nobjs);
     _obj *VOLATILE* __my_free_list;
     _obj *VOLATILE* __my_free_list1;
     _obj * __result;
     _obj * __current_obj;
     _obj * __next_obj;
     int __i;
     // 如果内存池中仅有一个对象
     if (1 == __nobjs) 
         return(__chunk);
     __my_free_list = _free_list + freelist_index(n);
     /* Build free list in chunk */
     __result = (_obj*)__chunk;
     *__my_free_list = __next_obj = (_obj*)(__chunk + n);
     __my_free_list1 = _free_list + freelist_index(n);
     for (__i = 1;; ++__i)
     {
         __current_obj = __next_obj;
         __next_obj = (_obj*)((char*)__next_obj+n);
         if(__nobjs - 1 == __i)
         {
              __current_obj->free_list_link = 0;
              break;
         }else{
              __current_obj->free_list_link = __next_obj;
         }
     }
     return(__result);
}

经过上面操作后,内存池可能会成为如下的一种状态。从图上我们可以看到,已经构建了8,24,88,128字节的空闲分配链表,而其他没有分配空闲 分配链表的他们的指针都指向NULL。我们通过判断索引表中的指针是否为NULL,知道是否已经构建空闲分配表或者空闲分配表是否用完,如果此处指针为 NULL,我们调用refill函数,重新申请20个这样大小的内存空间,并把他们连接起来。在refill函数内,我们要查看大内存中是否有可用内存, 如果有,并且大小合适,就返回给refill函数。

威尼斯 10
图4

 

    6:线程安全
    采用互斥体,保证线程安全。

内存池测试

    内存池的测试主要分两部分测试1:单线程下malloc与mempool的分配速度对比2:多线程下malloc和mempool的分配速度对比,我们分为4,10,16个线程进行测试了。
    测试环境:操作系统:windows2003+sp1,VC7.1+sp1,硬件环境:intel(R) Celeron(R) CPU 2.53GHz,512M物理内存。

    申请内存空间设定如下
#define ALLOCNUMBER0 4
#define ALLOCNUMBER1 7
#define ALLOCNUMBER2 23
#define ALLOCNUMBER3 56
#define ALLOCNUMBER4 10
#define ALLOCNUMBER5 60
#define ALLOCNUMBER6 5
#define ALLOCNUMBER7 80
#define ALLOCNUMBER8 9
#define ALLOCNUMBER9 100

    Malloc方式和mempool方式均使用如上数据进行内存空间的申请和释放。申请过程,每次循环申请释放上述数据20次
    我们对malloc和mempool,分别进行了如下申请次数的测试(单位为万)

2

10

20

30

40

50

80

100

150

200

malloc和mempool在单线程,多线程,release,debug版的各种测试数据,形成如下的统计图

威尼斯 11
图5

可以看到mempool无论在多线程还是在单线程情况下,mempool的速度都优于malloc方式的直接分配。

    Malloc方式debug模式下,在不同的线程下,运行时间如下,通过图片可知,malloc方式,在debug模式下,申请空间的速度和多线程的关系不大。多线程方式,要略快于单线程的运行实现。

威尼斯 12
图6

    Malloc方式release模式测试结果如下。

威尼斯 13
图7

多线程的优势,逐渐体现出来。当执行200w次申请和释放时,多线程要比单线程快1500ms左右,而4,10,16个线程之间的差别并不是特别大。不过整体感觉4个线程的运行时间要稍微高于10,16个线程的情况下,意味着进程中线程越多用在线程切换上的时间就越多。

下面是mempool在debug测试结果

威尼斯 14
图8

    下面是mempool在release模式下的测试结果

威尼斯 15
图9

    以上所有统计图中所用到的数据,是我们测试三次后平均值。

通过上面的测试,可以知道mempool的性能基本上超过直接malloc方式,在200w次申请和释放的情况下,单线程release版情况 下,mempool比直接malloc快110倍。而在4个线程情况下,mempool要比直接malloc快7倍左右。以上测试只是申请速度的测试,在 不同的压力情况下,测试结果可能会不同,测试结果也不能说明mempool方式比malloc方式稳定。

    小结:内存池基本上满足初期设计目标,但是她并不是完美的,有缺陷,比如,不能申请大于256字节的内存空间,无内存越界检查,无内存自动回缩功能等。只是这些对我们的影响还不是那么重要。

由于这是一个公司项目,代码涉及版权,所以不能发布出来。如果你想做自己的内存池,可以与我联系ugg_xchj#hotmail.com.

 

来源:

本文由威尼斯发布于威尼斯人登录网站,转载请注明出处:通过对申请空间小而申请频繁的对象进行有效管

关键词: