我执分别心

除了自己还有谁

怎么实现释放和分配时间复杂度都为常数(O(1))的内存池

以前在一个高性能的场合,需要十分频繁的使用临时缓存。由于所需的缓存大小我事先知道,所以我索性开了一块全局缓存,不要骂我土,它背后可以一个崇高的设计哲学:奥坎姆的剃刀。
不过,后边我越看越恶心,越看越想吐,于是就想实现一个分配和释放都为常数时间的MemPool. 虽然内存池是一个老得不老再老的话题,但是我并没有找到一个能达到我要求的设计。
虽然我对C++的任何细节都毫不知情,不过还是免为其难的写了一个有诸多缺陷的XMemPool。

先说下大致思路:
1 POOL将分配划分成两种情况,小缓存分配,大缓存分配。小于4K的我把它当成小缓存。小缓存块BlockSize按8字节步长增长,大块默认按4K步长增长。每种Size的块用两个链表进行管理(free & used)。
2 分配。要是size超过了最大能分配的大小或者池容量超过限制就直接调用系统分配。计算相应块的index(如果是调用系统分配的index会置为-1), 把free list第一个结点移到used list的第一个结点
3 释放。 如果块的index为-1直接delete。将要释放的块直接移动到free list的第一个结点。

这样的话缺点也是相当明显的:
1 用户必要从Block获取缓存
2 用户非常有必要对缓存大小事先按需求进行合理估计。

 1#ifndef _X_MEM_POOL_H_
 2#define _X_MEM_POOL_H_
 3
 4//! (1)alloc:O(1)
 5//! (2)free :O(1)
 6//! (3)not thread safe
 7
 8class XMemPool;
 9class XMemBlock
10{
11public:
12    XMemBlock( const int& index, const size_t& size ):
13      _index( index ),
14      _next( 0 ),
15      _pre( 0 ),
16      _size( size )
17    {
18        _data = new char[size];
19    }

20    ~XMemBlock()
21    {
22        delete []_data;
23    }

24
25public:
26    friend class XMemPool;
27    template<class T>
28    T* getMem() const return (T*)_data; }
29
30private:
31    const int    _index;
32    const size_t _size;
33    char        *_data;
34    XMemBlock  *_next;
35    XMemBlock  *_pre;
36}
;
37
38const size_t S_MEM_THRE        = 4096;//4K
39const size_t S_POOL_STEP       = 8;
40const size_t LARGE_POOL_STEP   = 4096;//4K
41const size_t SMAX_SUB_POOL_CAP = 128;
42const size_t LMAX_SUB_POOL_CAP = 64;
43
44class XMemPool
45{
46public:
47    /* 
48    maxBlockSize 此内存池能分配的最大的内存
49    maxSubPoolCapability 每个子内存池的最大容量
50    poolXep 相邻子内存池之间的BlockSize的差距,即每个子内存池大小为poolXep的整数倍
51
52    这里小块的容量,大小写死了的,只有大块的可以配置
53    */

54    XMemPool( const size_t& maxBlockSize, const size_t& lmaxSubPoolCapability = LMAX_SUB_POOL_CAP,\
55        const size_t& lpoolXep = LARGE_POOL_STEP );
56    ~XMemPool();
57public:
58    XMemBlock *alloc( size_t size );
59    void free( XMemBlock* block );
60    void destroy();
61    size_t getTotalMemSize() const return _totalMemSize; };
62
63private:
64    const size_t _maxBlockSize;  //最大能分配的内存块
65    const size_t _lmaxSubPoolCapability; //每种块的最大小数(大块)
66    static const size_t\
67                 _smaxSubPoolCapability = SMAX_SUB_POOL_CAP;//每种块的最大小数(小块)
68    const size_t _lpoolXep; //大块的增长步长
69    static const size_t\
70                 _spoolXep = S_POOL_STEP; //小块的步长
71    XMemBlock **_ssubPool[2];//0:free 1:used 小块的链表数组
72    XMemBlock **_lsubPool[2];//大块的链表数组
73    size_t       _ssubPoolNum;//小块的种类个数
74    size_t       _lsubPoolNum;//大块的种类个数
75    size_t      *_lsubPoolSize;//每种size大块的个数
76    size_t      *_ssubPoolSize;//每种size小块的个数
77    size_t       _totalMemSize;//内存池总容量
78}
;
79
80#endif

 

  1XMemPool::XMemPool( const size_t& maxBlockSize, const size_t& lmaxSubPoolCapability, const size_t& lpoolXep ):\
  2_maxBlockSize( maxBlockSize ),
  3_lmaxSubPoolCapability( lmaxSubPoolCapability ),
  4_lpoolXep( lpoolXep )
  5{
  6    _ssubPoolNum = ( S_MEM_THRE + _spoolXep - 1 ) / _spoolXep;
  7    _lsubPoolNum = ( _maxBlockSize + _lpoolXep - 1 ) / _lpoolXep;
  8    _totalMemSize = 0;
  9    _ssubPoolSize = new size_t[_ssubPoolNum];
 10    _lsubPoolSize = new size_t[_lsubPoolNum];
 11    _ssubPool[0= new XMemBlock*[_ssubPoolNum];
 12    _ssubPool[1= new XMemBlock*[_ssubPoolNum];
 13    forint i = 0; i < _ssubPoolNum; i++ )
 14    {
 15        _ssubPool[0][i] = 0;
 16        _ssubPool[1][i] = 0;
 17        _ssubPoolSize[i] = 0;
 18    }

 19    _lsubPool[0= new XMemBlock*[_lsubPoolNum];
 20    _lsubPool[1= new XMemBlock*[_lsubPoolNum];
 21    forint i = 0; i < _lsubPoolNum; i++ )
 22    {
 23        _lsubPool[0][i] = 0;
 24        _lsubPool[1][i] = 0;
 25        _lsubPoolSize[i] = 0;
 26    }

 27}

 28
 29XMemBlock* XMemPool::alloc( size_t size ) //byte unit
 30{
 31    if( size <= S_MEM_THRE )
 32    {
 33        size_t idx = ( size + _spoolXep - 1 ) / _spoolXep - 1;
 34        XMemBlock *block = 0;
 35        if( _ssubPool[0][idx] )
 36        {
 37            block = _ssubPool[0][idx];
 38            _ssubPool[0][idx] = block->_next;
 39            if( _ssubPool[1][idx] )
 40                _ssubPool[1][idx]->_pre = block;
 41            block->_next = _ssubPool[1][idx];
 42            _ssubPool[1][idx] = block;
 43            _ssubPool[1][idx]->_pre = 0;
 44            return block;
 45        }

 46        else if( _ssubPoolSize[idx] < _smaxSubPoolCapability )
 47        {
 48            size_t msize = (idx + 1)*_spoolXep;
 49            _totalMemSize += msize;
 50            block = new XMemBlock( idx, msize );
 51            _ssubPoolSize[idx]++;
 52            if( _ssubPool[1][idx] )
 53                _ssubPool[1][idx]->_pre = block;
 54            block->_next = _ssubPool[1][idx];
 55            _ssubPool[1][idx] = block;
 56            return block;
 57        }

 58    }

 59    else if( size <= _maxBlockSize )
 60    {
 61        size_t idx = ( size + _lpoolXep - 1 ) / _lpoolXep - 1;
 62        XMemBlock *block = 0;
 63        if( _lsubPool[0][idx] )
 64        {
 65            block = _lsubPool[0][idx];
 66            _lsubPool[0][idx] = block->_next;
 67            if( _lsubPool[1][idx] )
 68                _lsubPool[1][idx]->_pre = block;
 69            block->_next = _lsubPool[1][idx];
 70            _lsubPool[1][idx] = block;
 71            _lsubPool[1][idx]->_pre = 0;
 72            return block;
 73        }

 74        else if( _lsubPoolSize[idx] < _lmaxSubPoolCapability )
 75        {
 76            size_t msize = (idx + 1)*_lpoolXep;
 77            _totalMemSize += msize;
 78            block = new XMemBlock( idx, msize );
 79            _lsubPoolSize[idx]++;
 80            if( _lsubPool[1][idx] )
 81                _lsubPool[1][idx]->_pre = block;
 82            block->_next = _lsubPool[1][idx];
 83            _lsubPool[1][idx] = block;
 84            return block;
 85        }

 86    }

 87
 88     return (new XMemBlock( -1, size ));
 89}

 90
 91void XMemPool::free( XMemBlock *block )
 92{
 93    if( block->_index < 0 )
 94    {
 95        delete block;
 96        return;
 97    }

 98    if( block->_size <= S_MEM_THRE )
 99    {
100        if( block->_next )
101            block->_next->_pre = block->_pre;
102        if( block->_pre )
103            block->_pre->_next = block->_next;
104        else if!block->_next && !block->_pre )
105            _ssubPool[1][block->_index] = 0;
106        block->_next = _ssubPool[0][block->_index];
107        if( _ssubPool[0][block->_index] )
108            _ssubPool[0][block->_index]->_pre = block;
109        _ssubPool[0][block->_index] = block;
110    }

111    else
112    {
113        if( block->_next )
114            block->_next->_pre = block->_pre;
115        if( block->_pre )
116            block->_pre->_next = block->_next;
117        else if!block->_next && !block->_pre )
118            _lsubPool[1][block->_index] = 0;
119        block->_next = _lsubPool[0][block->_index];
120        if( _lsubPool[0][block->_index] )
121            _lsubPool[0][block->_index]->_pre = block;
122        _lsubPool[0][block->_index] = block;
123    }

124}

125
126void XMemPool::destroy()
127{
128    forint i = 0; i < _ssubPoolNum; i++ )
129    {
130        XMemBlock *block = _ssubPool[0][i], *tmp;
131        while( block )
132        {
133            tmp = block->_next;
134            delete block;
135            block = tmp;
136        }

137        _ssubPool[0][i] = 0;
138
139        block = _ssubPool[1][i];
140        while( block )
141        {
142            tmp = block->_next;
143            delete block;
144            block = tmp;
145        }

146        _ssubPool[1][i] = 0;
147        _ssubPoolSize[i] = 0;
148    }

149    forint i = 0; i < _lsubPoolNum; i++ )
150    {
151        XMemBlock *block = _lsubPool[0][i], *tmp;
152        while( block )
153        {
154            tmp = block->_next;
155            delete block;
156            block = tmp;
157        }

158        _lsubPool[0][i] = 0;
159
160        block = _lsubPool[1][i];
161        while( block )
162        {
163            tmp = block->_next;
164            delete block;
165            block = tmp;
166        }

167        _lsubPool[1][i] = 0;
168        _lsubPoolSize[i] = 0;
169    }

170}

171
172XMemPool::~XMemPool()
173{
174    destroy();
175    delete []_ssubPoolSize;
176    delete []_lsubPoolSize;
177    delete []_ssubPool[0];
178    delete []_ssubPool[1];
179    delete []_lsubPool[0];
180    delete []_lsubPool[1];
181}

 

1XMemPool samplePool(4096);
2XMemBlock *sampleBlock = samplePool.alloc(sizeof(int)*100);
3int *sampleData = sampleBlock->getMem<int>();
4samplePool.free(sampleBlock);



很多细节还没考虑到,谁能为我推荐一个好的设计方案?双O(1)的

posted on 2012-03-16 14:32 我执分别心 阅读(1469) 评论(11)  编辑 收藏 引用

评论

# re: 怎么实现释放和分配时间复杂度都为常数(O(1))的内存池[未登录] 2012-03-16 16:54 hdqqq

在alloc和free中看到了new和delete,这种分配不会是o(1)的。  回复  更多评论   

# re: 怎么实现释放和分配时间复杂度都为常数(O(1))的内存池 2012-03-16 17:00 我执分别心

@hdqqq
没有认真看代码吧, 只是内存池满了OR请求大小超过上限才会new delete
当然内存池没有预分配,是逐步增长的  回复  更多评论   

# re: 怎么实现释放和分配时间复杂度都为常数(O(1))的内存池 2012-03-16 18:53 陈梓瀚(vczh)

我以前也做过类似的。首先一个好的小尺寸缓存池可以O(1)new和delete这个显然你已经知道怎么做了,然后准备8 16 32 64各种尺寸,最后用平衡树组织起来。虽然这严格来算不是O(1),但是经验下他是O(1)的——只要你不要让节点有几十个那么多。至于大尺寸的,是没办法的。  回复  更多评论   

# re: 怎么实现释放和分配时间复杂度都为常数(O(1))的内存池 2012-03-16 19:06 我执分别心

@陈梓瀚(vczh)
我实现的这个虽然有缺陷,但在我的使用范围内,确实是严格O(1)的。如果要用到HASH或树之类的就是lg(n)的了。 SIZE按幂次增长我也想过,那样的话空间浪费厉害,不过跨度比较大的话确实可以考虑  回复  更多评论   

# re: 怎么实现释放和分配时间复杂度都为常数(O(1))的内存池 2012-03-16 19:11 陈梓瀚(vczh)

@我执分别心
不定尺寸池严格O(1)是不可能的,我不知道我有没有理解错你的意思,反正大概就是这个意思了,如果你要对付那些频繁new和delete的场景的话。  回复  更多评论   

# re: 怎么实现释放和分配时间复杂度都为常数(O(1))的内存池 2012-03-16 19:24 我执分别心

@陈梓瀚(vczh)
为什么不可能呢? 我这儿的实现其实很简单,关键是用block里面的index,它的本质是一个O(1)的HASH, 这样的代价就是创建pool的时候: 非常有必要对缓存大小事先按需求进行合理估计。  回复  更多评论   

# re: 怎么实现释放和分配时间复杂度都为常数(O(1))的内存池 2012-03-16 21:09 yrj

http://git.savannah.gnu.org/cgit/lwip.git/tree/src/core/memp.c  回复  更多评论   

# re: 怎么实现释放和分配时间复杂度都为常数(O(1))的内存池 2012-03-17 03:53 陈梓瀚(vczh)

@我执分别心
不要以为hash就真的是O(1)的,还记得之前很多语言的hashtable被用来做DDOS的事情吗?  回复  更多评论   

# re: 怎么实现释放和分配时间复杂度都为常数(O(1))的内存池 2012-03-17 09:25 我执分别心

@陈梓瀚(vczh)
size_t idx = ( size + _lpoolXep - 1 ) / _lpoolXep - 1; 它是O(1)不?  回复  更多评论   

# re: 怎么实现释放和分配时间复杂度都为常数(O(1))的内存池 2012-03-17 09:29 tb

厉害  回复  更多评论   

# re: 怎么实现释放和分配时间复杂度都为常数(O(1))的内存池[未登录] 2012-03-19 08:54 Chipset

小的容易做到,boundary tags, bitmap, freelist都行,大的需要比较复杂的数据结构,建议用PTrie,你可以参考下DLMalloc,谷歌下。

如果多处理器并行环境,那就非常困难了,传统的并发控制机制会成为瓶颈,还要小心False sharing, blowup...,你可以参考下JeMalloc,谷歌下。  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2012年3月>
26272829123
45678910
11121314151617
18192021222324
25262728293031
1234567

统计

常用链接

留言簿

随笔档案

文章分类

最新随笔

搜索

最新评论