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 的大小。
- class b2BlockAllocator
- {
- public:
- b2BlockAllocator();
- ~b2BlockAllocator();
-
- void* Allocate(int32 size);
- void Free(void* p, int32 size);
-
- void Clear();
-
- private:
-
- b2Chunk* m_chunks;
- int32 m_chunkCount;
- int32 m_chunkSpace;
-
- b2Block* m_freeLists[b2_blockSizes];
-
- static int32 s_blockSizes[b2_blockSizes];
- static uint8 s_blockSizeLookup[b2_maxBlockSize + 1];
- static bool s_blockSizeLookupInitialized;
- };
-
-
- const int32 b2_chunkSize = 4096;
- const int32 b2_maxBlockSize = 640;
- const int32 b2_blockSizes = 14;
- const int32 b2_chunkArrayIncrement = 128;
-
-
- int32 b2BlockAllocator::s_blockSizes[b2_blockSizes] =
- {
- 16,
- 32,
- 64,
- 96,
- 128,
- 160,
- 192,
- 224,
- 256,
- 320,
- 384,
- 448,
- 512,
- 640,
- };
- uint8 b2BlockAllocator::s_blockSizeLookup[b2_maxBlockSize + 1];
-
- void* b2BlockAllocator::Allocate(int32 size)
- {
- if (size == 0)
- return NULL;
-
- b2Assert(0 < size && size <= b2_maxBlockSize);
-
- int32 index = s_blockSizeLookup[size];
- b2Assert(0 <= index && index < b2_blockSizes);
-
- if (m_freeLists[index])
- {
- b2Block* block = m_freeLists[index];
- m_freeLists[index] = block->next;
- return block;
- }
- else
- {
- if (m_chunkCount == m_chunkSpace)
- {
- 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);
- #if defined(_DEBUG)
- memset(chunk->blocks, 0xcd, b2_chunkSize);
- #endif
- int32 blockSize = s_blockSizes[index];
- chunk->blockSize = blockSize;
- int32 blockCount = b2_chunkSize / blockSize;
- b2Assert(blockCount * blockSize <= b2_chunkSize);
- for (int32 i = 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;
-
- return chunk->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操作符我们可以调用对象的构造函数但是使用已经分配的内存。