一个快速的内存分配池

dreams

对于现代的游戏引擎来说，为了提高性能和有效的管理内存，需要使用各种各样
的内存分配模型，内存池作为一种有效的分配模型被大量的使用，它通过一次分配
足够的内存来减少对new delelte使用以提高引擎的性能，并且由于每一个内存块
都有相同的大小因此非常易于管理，并可以防止内存的泄露。它通常被用于需要
分配大量相同对象的场合，如粒子系统这样的地方。

对于在运行时可以明确知道分配数量的物体，可以通过一个静态数组来实现它，
但对于不知道分配数量的地方，设计就变的有些复杂，通常需要使用一个链表来
进行实现，如STL的list容器，不过使用它有一个很大的缺点，链表对表中的对象
进行查询操作时速度不是很理想，会极大影响它的性能。因此需要寻找一个比较
好的方法对其进行改进。

通常设计内存池有两个问题必须考虑，一个是内存分配的策略，由于你不是明确
知道待分配物体的数量，因此每次分配多大数量的内存是一个值得注意的问题。
另一个是如何对内存池进行管理，使用什么样的数据结构才能在常数时间内来获得
指定的内存。对于第一个问题解决的方案很多，你可以每次都分配一个指定数量
的内存块，也可以在每次分配时都分配比上一次多一倍的内存，哪种方案更好，需要
你自己在实际使用中体会。第二个问题是本文的核心，一般的做法是将已经分配的
内存块分成两个部分，已使用和未使用两个链表，但是这样做的性能并不理想，下面
看看如何对其进行改进：

我们先建立一个结构用于保存每次分配的一整块内存：
sturct MemChunk
{
  MemChunk* m_pPre;
  MemChunk* m_pNext;
  unsigned int m_nSize;
  char m_Data[1];
}
在这个结构中m_pPre，m_pNext用于建立一个双向链表将每一次分配的内存连接起来，
m_nSize表示当前内存块的大小，m_Data是所分配的内存指针，必须注意这是一个BYTE
指针。我们现在假设当前的内存池用于对CObject物体分配内存，每次分配都一次分配
64个CObject物体的内存，因此m_nSize的大小为64*sizeof(CObject)。下面看看如何
保存未使用的内存块，我们需要一个指针来指向当前未使用的内存块。
void* s_pCurrent;
然后令它指向当前还未使用的内存块。
s_pCurrent = pMemChunk->mData;
下面是本文最关键的部分，为了提高性能我们令每一个未使用的内存块的头部都保存
一个指针，让它指向下一个未使用的内存块，这样就为未使用的内存块形成了一个单
向链表。当你需要一个物体的内存时可以这么做：
void* returnPtr = s_pCurrent;
s_pCurrent = *((void **)s_pCurrent);
return returnPtr;
这样returnPtr就是你要获得的内存指针，而s_pCurrent通过一个简单的指针转换巧妙
的又指向了下一个内存块，如果上一句看不懂，请你重新复习一下C++教材中关于指针
的解释。
当你需要释放一个物体的内存时，方法和此类似。
*((void**)pMem = s_pCurrent;
s_pCurrent = pMem;
这样就可以将内存块重新连接到未使用的内存块链表中。通常对指针进行转换的时间
非常短，比一般的链表的插入、删除操作速度快的多，因此这个技巧是非常值得借鉴
的做法。

square.jerry

这种思想是一 种创新，其实有人这么做了。但你的思想有一个主要问题没有解决，或者说你这个内存池只能分配固定类型的对象，既我这次分配的是CObject,下一次也必须还是分配的CObject类型。因为，如果我做了一个删除操作，中间空出的一个CObject所占用的内存不能分配比CObject更大的类型对象，如果分配比COject更小的对象，又会大量浪费内存。而且另一个问题就是无法确定分配需要的量。楼主这种方法对固定类型对象且比较好确定分配的数量的情况下还是很有用的。

rename

void* s_pCurrent;
(void **)s_pCurrent;
这样的作用是什么呀？

bluefire9213

我讨厌内存碎块，到不得已时才用链表，树等，即使是用了，也是在切换场景时申请，然后把碎块拼起来。

william9527

看了stlport，觉得它的Allocate类做的不错，基于内存块的大小使用不同的策略分配内存，或许可以在实际中使用一下先。