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操作符我們可以調用對象的構造函數但是使用已經分配的內存。
http://rritw.com/a/JAVAbiancheng/SOA/20111117/143978.html