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

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, // 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
};
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)
        { // 实现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);
#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操作符我们可以调用对象的构造函数但是使用已经分配的内存。