关于Memory Pool的一些想法及实现
在《Effective C++》(Second Edition)中Item 10 "Write operator delete if you write operator new"中提到一个Memory Pool技术, 并给出一个例子
void *Airplane::operator new(size_t size)
{
if(size != sizeof(Airplane))
return ::operator new(size);
Airplane *p = headOfFreeList;
if(p)
headOfFreeList = p->next;
else
{
Airplane * newBlock = static_cast<Airplane *>(::operator new(BLOCK_SIZE*sizeof(Airplane)));
}
for(int i=1; i<BLOCK_SIZE-1; ++i)
newBlock[i].next = &newBlock[i+1];
newBlock[BLOCK_SIZE-1].next = 0;
p= newBlock;
headOfFreeList = &newBlock[1];
}
书中提到, 用这种技术的好处有二: 一. 节省空间, 普通的new操作由于需要记住申请的大小, 一般需要更多的空间. 而应用这种技术则不需要额外的空间. 二. 操作速度快, 此种的new和delete操作只是对链表的添加和删除操作, 不需要做真正的系统空间分配, 速度更快.
但明显, 例子中给出的操作只能针对Airplane类进行操作, 试想, 能不能扩展到对任何类进行这样的Memory Pool操作呢?
第一想法就是用template.
花了一中午的时间写了一个CMemoryPool模板类. 如下所示
#ifndef __MEMORYPOOL_H__
#define __MEMORYPOOL_H__
#include <vector>
template <class _T>
class CMemoryPool
{
public:
CMemoryPool(size_t init_size = 100) : INIT_SIZE(init_size)
{
headOfFreeList = NULL;
}
~CMemoryPool()
{
for(int i=0; i<m_memoryHeadVector.size(); ++i)
{
Envelope *block = m_memoryHeadVector[i];
::operator delete(block);
}
}
_T *alloc()
{
Envelope *p = headOfFreeList;
if(p)
headOfFreeList = p->next;
else
{
const size_t ObjectSize = (sizeof(_T) > sizeof(Envelope)) ? sizeof(_T) : sizeof(Envelope);
// 申请空间
Envelope *newBlock = static_cast<Envelope *>(::operator new(INIT_SIZE * ObjectSize));
// 初始化空闲空间列表
for(int i=1; i<INIT_SIZE; ++i)
((Envelope *)((char *)newBlock + i * ObjectSize))->next = (Envelope *)((char *)newBlock + (i+1) * ObjectSize);
(newBlock + (INIT_SIZE - 1) * ObjectSize)->next = NULL;
// 保存首址
m_memoryHeadVector.push_back(newBlock);
p = newBlock;
headOfFreeList = (Envelope*)((char *)newBlock + ObjectSize);
}
return (_T *)p;
}
void free(_T *p)
{
if(p==NULL)
return;
Envelope *freeBlock = (Envelope *)p;
freeBlock->next = headOfFreeList;
headOfFreeList = freeBlock;
}
private:
union Envelope
{
_T *object;
union Envelope *next;
};
const size_t INIT_SIZE; // 默认每次分配多少初始大小的空间
Envelope *headOfFreeList; // 当前自由空间首址
std::vector<Envelope *> m_memoryHeadVector; // 申请空间首址向量
};
#endif // !defined __MEMORYPOOL_H__
问题点数：100、回复次数：52Top
1 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2006-03-08 15:58:58 得分 0
此模板类对于内建类型, 可做如下使用.
#include <iostream>
#include "MemoryPool.h"
int main()
{
CMemoryPool<double> d_Pool;
double *p[10];
int i;
for(i=0; i<10; ++i)
{
p[i] = d_Pool.alloc();
std::cout<<p[i]<<std::endl;
}
for(i=0; i<5; ++i)
d_Pool.free(p[i]);
for(i=0; i<5; ++i)
p[i] = d_Pool.alloc();
for(i=0; i<10; ++i)
std::cout<<p[i]<<std::endl;
return 0;
}
如果仅仅这样使用, 还没有达到所要求的目的.
关键是对于自己的自定义类, 通过重载operator new与operator delete来使用Memory Pool
如下:
#include <iostream>
#include "MemoryPool.h"
class MyClass
{
public:
MyClass();
~MyClass();
static void * operator new(size_t t);
static void operator delete(void *p);
private:
static CMemoryPool<MyClass> st_objectPool;
};
CMemoryPool<MyClass> MyClass::st_objectPool(10);
MyClass::MyClass()
{
std::cout<<"A() called"<<std::endl;
}
MyClass::~MyClass()
{
std::cout<<"~A() called"<<std::endl;
}
void * MyClass::operator new(size_t t)
{
if(t != sizeof(MyClass))
return ::operator new(t);
return MyClass::st_objectPool.alloc();
}
void MyClass::operator delete(void *p)
{
MyClass::st_objectPool.free((MyClass *)p);
}
int main()
{
MyClass *ptr;
ptr = new MyClass;
delete ptr;
return 0;
}
Top
2 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2006-03-08 16:02:32 得分 0
到此, 已经完成了对于任何类的一个CMemoryPool类的写法.
自然会想到, 怎么样去写一个基类CMemoryPoolBaseClass, 让所有继承该类的子类都具有这种内存池的动态内存分配方式呢?
这是留下一个未解决的问题, 不知大家有什么好的想法, 或对于Effective C++中Item 10中的Memory Pool有更好的设计方案, 不妨在此帖中讨论讨论.Top
3 楼steedhorse（晨星）回复于 2006-03-08 16:08:24 得分 0
顶一顶。Top
4 楼xhs1115（木亘）回复于 2006-03-08 16:15:03 得分 5
在STL的源码中就使用了此技巧，如vector的动态扩展就是据于Memory PoolTop
5 楼pankun（剑神一笑 Console下面干革命）回复于 2006-03-08 16:15:48 得分 10
我以前写过的内存池可以实现.就是父类重载new 和 delete就可以了,大概是这样的
template<unsigned int Size = 0,
unsigned int Count = MEMORYPOOL_DEFAULT_SIZE,
unsigned int ReAlloc = MEMORYPOOL_DEFAULT_SIZE>
class MemObj
{
public:
#ifdef USE_MEMORY_POOL
inline static void * operator new(size_t)
{
return pool_->alloc();
}
inline static void operator delete(void *rawmemory, size_t)
{
if (NULL == rawmemory) return;
pool_->free(rawmemory);
}
#endif//USE_MEMORY_POOL
};
Top
6 楼pankun（剑神一笑 Console下面干革命）回复于 2006-03-08 16:18:48 得分 0
另外楼主,要高效,就自己写链表,内存池类不要用vector了...
然后尽量用模块,一些数据编译期就决定下来.不要留到运行期才计算Top
7 楼txj_killer（流浪的天行）回复于 2006-03-08 16:19:03 得分 20
我觉得书中最大的问题就是有增加没有减少，造成如果内存需求存在单峰值时会出现很大的浪费，所以应该加入一个降低池大小的策略，比如使用比率低于某个比率长于多少时间时则减半之类的。。。Top
8 楼pankun（剑神一笑 Console下面干革命）回复于 2006-03-08 16:19:07 得分 0
打错字了.模块=模板Top
9 楼pankun（剑神一笑 Console下面干革命）回复于 2006-03-08 16:20:10 得分 0
没认真看,楼主是使用的自己的链表.汗Top
10 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2006-03-08 16:26:34 得分 0
>> 另外楼主,要高效,就自己写链表,内存池类不要用vector了...
程序中的Vector是用于将申请的空间首址记录下来, 因为程序中对于空间不够的处理策略是: 再申请一块新的大内存空间, 不是普通的申请更大的连续空间,然后抛弃原先的空间, 这样, 这个内存池实际上是由数目不定的相同大小的不一定连续的内存块组成, 那么在释放的时候就必需知道这些内存块的首址.
>> 比如使用比率低于某个比率长于多少时间时则减半之类的
对于书的使用策略, 是无法降低内存池的大小的, 在经过多次分配时, 内存的空闲链表已经不再是连续的, 你无法去释放一个整块的内存.Top
11 楼txj_killer（流浪的天行）回复于 2006-03-08 17:44:19 得分 0
可以仿照系统堆内存那样定时整理一下，不过效率就有问题了。。。Top
12 楼xlsue（小林）回复于 2006-03-08 21:01:35 得分 10
觉得sgi stl中的memory pool实现得很妙。。。Top
13 楼sankt（宠辱不惊,看庭前花开花落;去留无意,望天空云卷云舒.）回复于 2006-03-10 19:33:45 得分 0
学习
Top
14 楼cattlenzq（吃狼的豆腐（不要给分了，散起来真麻烦！））回复于 2006-03-10 21:16:19 得分 5
建议大家看下<<STL源码解(剖?)析>>,里面有很多这样的问题
Top
15 楼zengwujun（月之海 为linux入门奋斗100天）回复于 2006-03-11 09:15:07 得分 0
留言，给我1分啊，要不过段时间我就看不到帖子了Top
16 楼limlzm（凡叶）回复于 2006-03-11 09:52:01 得分 0
markTop
17 楼junnyfeng（风歌）回复于 2006-03-11 10:30:41 得分 0
学习Top
18 楼ox_thedarkness（）回复于 2006-03-11 11:45:11 得分 20
union Envelope{
_T *object;
union Envelope *next;
};
_T* object?? 也许你的意思是 _T object ? 看你的代码有这种感觉。
说实在的，我没看懂楼主的代码。你没有给 Envelope 链表的_T* 分配内存。（相应的，CMemoryPool的析构中也没有释放节点中的 _T* ） 我不清楚你的代码咋运作的。
而且，楼主的代码在我的VC7.1 Debug模式下无法执行，直接出错。
至于 _T object，这个写法要求默认构造函数。Top
19 楼ox_thedarkness（）回复于 2006-03-11 11:51:08 得分 0
恩阿，下面这种写法非法，不明白道理：
union Envelope{
_T object;
Envelope *next;
};Top
20 楼ox_thedarkness（）回复于 2006-03-11 12:27:24 得分 0
对于继承，我有一个想法。
operator new 本身是可继承的，他接受 size_t 作为参数。
可以这样设计：
1 一个通用单纯 MemPool 模版，参数为 size_t ，分配相同大小对象，返回 void*
2 专用 ClassMemPool 类（或者类模版），分配接口为： alloc( size_t )
他包含多个MemPool， 对每种不同的 size_T 使用一个不同的MemPool。
3 基类模版。提供 operator new 、 operator delete（可惜[]版本不适合这样的技巧）,并且调用 void* ClassMemPool :: alloc( size_t )，以及 ClassMemPool :: free( void* )
这样，所有派生类都会继承这对 operator new 和 delete了
///////////////////////////////////////////////////////////
这带来一个问题是 ClassMemPool 的删除效率，delete 只传递一个参数( void* )，需要识别属于哪个容器。 解决方案我只能想出两种。 我建议提供四种不同风格的模版供选择：
1 静态容器。删除时必须指定大小。这个方案很高效，不过用于继承体系的时候，一般需要派生类重载 operator delete。 问题是如何强制派生类提供正确的 operator delete。
2 不做额外簿记工作，或者把簿记工作放在容器内部。 搜索 MemPool 容器，对比要删除的 p。 很低效，但是内存消耗少，而且安全。
3 在对象头部提供一个额外的标志位记录其大小。这个增大了内存开销，没有上一个例子安全。 但是时间开销和最初的一样。Top
21 楼pankun（剑神一笑 Console下面干革命）回复于 2006-03-11 12:50:02 得分 0
这带来一个问题是 ClassMemPool 的删除效率，delete 只传递一个参数( void* )，需要识别属于哪个容器。
--------------------------
用不着啊.MemPool模板化,子类继承时从不同的MemPool<size>继承,编译器就能在编译期确定哪个子类属于哪个容器Top
22 楼Kenmark（fenix）回复于 2006-03-11 12:52:36 得分 0
DING 小雨的Top
23 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2006-03-11 15:58:14 得分 0
union Envelope{
_T object;
Envelope *next;
};
---------------
union定义的成员中不能出现有构造函数的对象, 通俗点说, 它的成员只能是一些内建数据类型.
所以只能以指针类型代替, 但指针类型只占4个字节, 在实际分配内存的时候,还是按_T类型分配内存,只不过这时候的指针偏移需要你自己通过强制类型转换实施.Top
24 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2006-03-11 16:33:07 得分 0
而且，楼主的代码在我的VC7.1 Debug模式下无法执行，直接出错。
-----------------
程序中的一点小错误:
(newBlock + (INIT_SIZE - 1) * ObjectSize)->next = NULL;
这儿内存非法操作了 改为
((Envelope*)((char *)newBlock + (INIT_SIZE - 1) * ObjectSize))->next = NULL;
就OK了.
完整的如下
#ifndef __MEMORYPOOL_H__
#define __MEMORYPOOL_H__
#include <list>
template <class _T>
class CMemoryPool
{
public:
CMemoryPool(size_t init_size = 100) : INIT_SIZE(init_size), m_memoryHeadList(5)
{
headOfFreeList = NULL;
}
~CMemoryPool()
{
std::list<Envelope *>::iterator iter;
for(iter = m_memoryHeadList.begin(); iter != m_memoryHeadList.end(); ++iter)
{
Envelope *block = *iter;
::operator delete(block);
}
}
_T *alloc()
{
Envelope *p = headOfFreeList;
if(p)
headOfFreeList = p->next;
else
{
const size_t ObjectSize = (sizeof(_T) > sizeof(Envelope)) ? sizeof(_T) : sizeof(Envelope);
// 申请空间
Envelope *newBlock = static_cast<Envelope *>(::operator new(INIT_SIZE * ObjectSize));
// 初始化空闲空间列表
for(int i=1; i<INIT_SIZE; ++i)
((Envelope *)((char *)newBlock + i * ObjectSize))->next = (Envelope *)((char *)newBlock + (i+1) * ObjectSize);
((Envelope*)((char *)newBlock + (INIT_SIZE - 1) * ObjectSize))->next = NULL;
// 保存首址
m_memoryHeadList.push_back(newBlock);
p = newBlock;
headOfFreeList = (Envelope*)((char *)newBlock + ObjectSize);
}
return (_T *)p;
}
void free(_T *p)
{
if(p==NULL)
return;
Envelope *freeBlock = (Envelope *)p;
freeBlock->next = headOfFreeList;
headOfFreeList = freeBlock;
}
private:
union Envelope
{
_T *object;
union Envelope *next;
};
const size_t INIT_SIZE;// 默认每次分配多少初始大小的空间
Envelope *headOfFreeList; // 当前自由空间首址
std::list<Envelope *> m_memoryHeadList; // 申请空间首址向量
};
#endif // !defined __MEMORYPOOL_H__
>> 说实在的，我没看懂楼主的代码。你没有给 Envelope 链表的_T* 分配内存。（相应的，CMemoryPool的析构中也没有释放节点中的 _T*
--------------------------
注意看看我在分配内存的时候, 并没有按照sizeof(Envelope)来分配的, 这一点是我在此实现中感觉很不爽的, 如果将Envelope改为结构体, 则没有这样的麻烦了. 为了能使用union又不受它那个成员只能是内建数据类型, 只好用一个指针域在那儿占个位子.
Top
25 楼ox_thedarkness（）回复于 2006-03-11 18:09:14 得分 0
= = 厄，可是那个union看起来实在是很词不达意啊... 其实完全可以用:
union Envelope{
unsigned char mem[ sizeof (_T) ];
Envelope* next;
};Top
26 楼sjf1（蜗牛）回复于 2006-03-11 19:22:53 得分 0
hen haoTop
27 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2006-03-11 19:59:02 得分 0
union Envelope{
unsigned char mem[ sizeof (_T) ];
Envelope* next;
};
-------------------
这个主意不错, 可以试试!Top
28 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2006-03-11 20:02:49 得分 0
刚试了一下, 很不幸, 还是跟
union Envelope
{
_T object;
union Envelope *next;
};
一样的结果
在unsigned char mem[ sizeof (_T) ];
还是存在未定义类型_T存在.无法编译通过Top
29 楼ox_thedarkness（）回复于 2006-03-11 22:23:36 得分 10
阿？ 我这里可以阿，VC7.1和 DevC++4.9 均通过。 楼主不会是VC6巴... 大概是模版支持问题。 手头没有VC6，不过那冬冬对C++支持太不友善了。 实在不行，这样总可以把....
template< size_t sz >
union Envelope_tmpl{
unsigned char mem[ sz ];
Envelope* next;
};
然后
typedef Evelope Evelope_tmpl< sizeof (_T) >;
如果typedef 不行那么一个个 Evelope_tmpl< sizeof (_T)>
如果还不行就... 厄... 没辙了...Top
30 楼wkcmail（asdf）回复于 2006-03-12 01:11:50 得分 0
mark
Top
31 楼deepass（渴望突破）回复于 2006-03-12 13:41:28 得分 0
学习中^_^Top
32 楼NicholasWu（尼古）回复于 2006-03-12 17:21:00 得分 5
侯捷的<<池内春秋>>Top
33 楼citywanderer2005（流浪狗）回复于 2006-03-12 17:26:05 得分 0
这个要顶Top
34 楼mmosquito（）回复于 2006-03-13 01:29:42 得分 5
好像boost支持memerypool，去看一下不就行了Top
35 楼cunsh（村少）回复于 2006-03-13 02:30:53 得分 0
mark
xuexi;Top
36 楼MagicCarmack（MagiC++）回复于 2006-03-13 02:54:16 得分 0
这个要顶!!Top
37 楼losedxyz（我真的一无所有）回复于 2006-03-13 08:50:32 得分 0
mark
Top
38 楼ox_thedarkness（）回复于 2006-03-13 10:37:29 得分 0
- -b 更正一下... 下面这个模版中的 typedef 似乎是非法的：
typedef Evelope Evelope_tmpl< sizeof (_T) >;Top
39 楼tatbaby（岛主）回复于 2006-03-13 18:46:29 得分 0
mark!Top
40 楼iamcaicainiao（老菜，长征）回复于 2006-03-14 09:52:40 得分 0
先顶一顶。菜。还看不懂。Top
41 楼wjlsmail（小脖领）回复于 2006-03-14 12:42:20 得分 0
StudyTop
42 楼sandrowjw（我的小猫照片给弄坏了，心都碎了）回复于 2006-03-14 15:38:25 得分 10
按类型分好还是按块的大小分好呢？其实malloc动作只能分配几种大小的块，其他的都是有内部碎片的，而且许多情况下不同类型分配达到块的大小是差不多的。当然在大量小对象的情况下按类型和按块差别应该不大。
另外，感觉通用内存池的一个缺点就是要记录的东西还是太多，如果释放的时候是整块释放而不是一个一个小对象这样释放，就不用记录那么多东西了（当然这有点像GC）。Top
43 楼jerdy2000（）回复于 2006-03-14 15:51:02 得分 0
markTop
44 楼Atomictry（天影）回复于 2006-03-15 09:47:11 得分 0
m...a...r...k...Top
45 楼shines（郭子）回复于 2006-03-15 11:01:23 得分 0
guan zhuTop
46 楼foochow（无聊,灌水......）回复于 2006-03-15 11:16:48 得分 0
路过帮顶。。。Top
47 楼foochow（无聊,灌水......）回复于 2006-03-15 11:17:19 得分 0
学习：^_^Top
48 楼ouyh12345（五岭散人）回复于 2006-03-15 11:22:45 得分 0
学习Top
49 楼20040216（每天几行）回复于 2006-03-15 13:16:18 得分 0
狗屁的东西，还又这么多人讨论
如果内存池这东西可以统一，stl早就做了
程序根据功能的实现会使用不同的内存池实现机制
Top
50 楼fellow99（Fellow）回复于 2006-03-16 09:16:40 得分 0
不是简简单单一个类就可以搞定的。。。Top
51 楼dylin（家住红灯区,市府前）回复于 2006-03-22 02:19:29 得分 0
haTop
52 楼hihi110（赵海）回复于 2006-03-28 20:13:23 得分 0
mark
Top
相关问题
关键词
得分解答快速导航
相关链接
广告也精彩
反馈
