Box2D 内存管理 - 小型对象分配器（SOA）的实现

转载自：http://blog.csdn.net/ring0hx/article/details/6978437

Box2D用C++编写(当然还有其它语言的移植版)，但是为了快速有效的使用内存，创建对象的时候它并没有使用C++标准的new 和delete关键字，而是自己实现了一个被称作小型对象分配器（smaller object allocator简称SOA）的类b2BlockAllocator。根据Box2D手册描述，Box2D倾向于分配大量50~300字节的小型对象，而且多数小型对象的生命周期都很短，如果每次都通过malloc或new在系统堆上分配内存，用完后立刻销毁，效率太低，而且会产生内存碎片。b2BlockAllocator维护了一些不定尺寸并可扩展的内存池，当有内存分配请求时,SOA 会返回一块大小最匹配的内存。当内存块释放之后, 它会被回收到池中。这些操作都十分快速,只有很小的堆流量。使用内存池应该是高性能C/C++编程中备受推崇的技术，著名C++开源函数库boost就提供了内存池，memcached也使用了称作Slab Allocation机制来管理内存。网上有很多介绍Slab Allocation的文章，今天研究了一下Box2D的SOA实现，写下来备忘，对于想要自己实现内存池的童鞋也是不错的参考。

先上b2BlockAllocator的主要代码，这里引用的是cocos2d附带的box2d代码，可能是版本较老或者针对移动设备做了一些调整，直接从box2d官网上下的新版略有不同，例如b2_chunkSize 的大小。

classb2BlockAllocator
{
public:
b2BlockAllocator();
~b2BlockAllocator();

void*Allocate(int32size);
voidFree(void*p,int32size);

voidClear();

private:

b2Chunk*m_chunks;
int32m_chunkCount;
int32m_chunkSpace;

b2Block*m_freeLists[b2_blockSizes];

staticint32s_blockSizes[b2_blockSizes];
staticuint8s_blockSizeLookup[b2_maxBlockSize+1];
staticbools_blockSizeLookupInitialized;
};


constint32b2_chunkSize=4096;
constint32b2_maxBlockSize=640;
constint32b2_blockSizes=14;
constint32b2_chunkArrayIncrement=128;


int32b2BlockAllocator::s_blockSizes[b2_blockSizes]=
{
16,//0
32,//1
64,//2
96,//3
128,//4
160,//5
192,//6
224,//7
256,//8
320,//9
384,//10
448,//11
512,//12
640,//13
};
uint8b2BlockAllocator::s_blockSizeLookup[b2_maxBlockSize+1];

void*b2BlockAllocator::Allocate(int32size)
{
if(size==0)
returnNULL;

b2Assert(0<size&&size<=b2_maxBlockSize);

int32index=s_blockSizeLookup[size];
b2Assert(0<=index&&index<b2_blockSizes);

if(m_freeLists[index])
{
b2Block*block=m_freeLists[index];
m_freeLists[index]=block->next;
returnblock;
}
else
{
if(m_chunkCount==m_chunkSpace)
{//实现m_chunks数组动态增长
b2Chunk*oldChunks=m_chunks;
m_chunkSpace+=b2_chunkArrayIncrement;
m_chunks=(b2Chunk*)b2Alloc(m_chunkSpace*sizeof(b2Chunk));
memcpy(m_chunks,oldChunks,m_chunkCount*sizeof(b2Chunk));
memset(m_chunks+m_chunkCount,0,b2_chunkArrayIncrement*sizeof(b2Chunk));
b2Free(oldChunks);
}

b2Chunk*chunk=m_chunks+m_chunkCount;
chunk->blocks=(b2Block*)b2Alloc(b2_chunkSize);
#ifdefined(_DEBUG)
memset(chunk->blocks,0xcd,b2_chunkSize);
#endif
int32blockSize=s_blockSizes[index];
chunk->blockSize=blockSize;
int32blockCount=b2_chunkSize/blockSize;
b2Assert(blockCount*blockSize<=b2_chunkSize);
for(int32i=0;i<blockCount-1;++i)
{
b2Block*block=(b2Block*)((int8*)chunk->blocks+blockSize*i);
b2Block*next=(b2Block*)((int8*)chunk->blocks+blockSize*(i+1));
block->next=next;
}
b2Block*last=(b2Block*)((int8*)chunk->blocks+blockSize*(blockCount-1));
last->next=NULL;

m_freeLists[index]=chunk->blocks->next;
++m_chunkCount;

returnchunk->blocks;
}
}

b2_chunkSize = 4096： 一次性分配的连续内存页（为了和block区分，我把chunk叫做内存页）的大小，为4096字节，也就是说SOA每次向系统堆请求内存的时候都是4096字节。

b2_maxBlockSize = 640：可以向SOA申请的内存块大小上限。大于640字节的对象就不属于需要SOA管理的小型对象了，不应该使用SOA来分配。

b2_blockSizes = 14：SOA可以分配从16字节到640字节不等的14种不同大小的内存块。具体的大小由静态数组s_blockSizes给出，它们都是16的倍数。

s_blockSizeLookup：静态数组，大小为640+1，由b2BlockAllocator构造的时候初始化，用于根据请求的内存大小查询最小可容纳的内存块应该多大。例如请求的内存大小为152字节，s_blockSizeLookup[152]的值是5，即对应s_blockSizes中第6个元素160，那么最小可容纳的内存块就是160字节。

m_chunks： 存放已经分配的内存页对象的数组。数组的大小为m_chunkSpace，初始化的时候m_chunkSpace=b2_chunkArrayIncrement=128。这里m_chunks用指针的形式而非数组的形式来表示是为了实现动态增长。当m_chunkCount == m_chunkSpace时会重新分配一块比原来大128*sizeof(b2Chunk)的新空间，再把旧数组的内容复制到新数组中。

m_chunkCount：SOA已经分配的内存页的个数，通过m_chunks+小于m_chunkCount的偏移量i就可以找到第i+1个内存页。

m_freeLists：保存了已分配的页中还未被使用的块的开始地址的数组。

为了更直观展示SOA是如何管理内存的，我画了某时刻的内存分配示意图：

每当有内存分配请求时，b2BlockAllocator会先把请求的大小a通过s_blockSizeLookup转换成s_blockSizes的index，通过这个index可以得到最小可容纳a的内存大小b。然后通过m_freeLists[index]来查询是否已经有块大小为b的可用内存页，如果有，直接返回空闲块并把m_freeLists[index]指向该页中的下一个空闲块。如果没有，通过malloc调用一次分配一个新的4096内存页并把它按b等分，然后返回第一个块并将m_freeLists[index]指向下一个未被使用的块。

最后看一下box2d是如何使用SOA分配的内存的：

void*mem=m_blockAllocator.Allocate(sizeof(b2Body));
b2Body*b=new(mem)b2Body(def,this);

Allocate根据请求大小返回一个指向新内存的void指针，通过C++ placement new操作符我们可以调用对象的构造函数但是使用已经分配的内存。