Chinaunix首页 | 论坛 | 博客
  • 博客访问: 697656
  • 博文数量: 102
  • 博客积分: 10
  • 博客等级: 民兵
  • 技术积分: 1748
  • 用 户 组: 普通用户
  • 注册时间: 2012-02-23 15:42
个人简介

寻找严肃、沉默和专注的力量。

文章分类

全部博文(102)

文章存档

2015年(26)

2014年(8)

2013年(68)

分类: C/C++

2014-03-18 19:22:10

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 的大小。

  1. class b2BlockAllocator  
  2. {  
  3. public:  
  4.     b2BlockAllocator();  
  5.     ~b2BlockAllocator();  
  6.   
  7.     void* Allocate(int32 size);  
  8.     void Free(void* p, int32 size);  
  9.   
  10.     void Clear();  
  11.   
  12. private:  
  13.   
  14.     b2Chunk* m_chunks;  
  15.     int32 m_chunkCount;  
  16.     int32 m_chunkSpace;  
  17.   
  18.     b2Block* m_freeLists[b2_blockSizes];  
  19.   
  20.     static int32 s_blockSizes[b2_blockSizes];  
  21.     static uint8 s_blockSizeLookup[b2_maxBlockSize + 1];  
  22.     static bool s_blockSizeLookupInitialized;  
  23. };  
  24.   
  25.   
  26. const int32 b2_chunkSize = 4096;  
  27. const int32 b2_maxBlockSize = 640;  
  28. const int32 b2_blockSizes = 14;  
  29. const int32 b2_chunkArrayIncrement = 128;  
  30.   
  31.   
  32. int32 b2BlockAllocator::s_blockSizes[b2_blockSizes] =   
  33. {  
  34.     16, // 0  
  35.     32, // 1  
  36.     64, // 2  
  37.     96, // 3  
  38.     128,    // 4  
  39.     160,    // 5  
  40.     192,    // 6  
  41.     224,    // 7  
  42.     256,    // 8  
  43.     320,    // 9  
  44.     384,    // 10  
  45.     448,    // 11  
  46.     512,    // 12  
  47.     640,    // 13  
  48. };  
  49. uint8 b2BlockAllocator::s_blockSizeLookup[b2_maxBlockSize + 1];  
  50.   
  51. void* b2BlockAllocator::Allocate(int32 size)  
  52. {  
  53.     if (size == 0)  
  54.         return NULL;  
  55.   
  56.     b2Assert(0 < size && size <= b2_maxBlockSize);  
  57.   
  58.     int32 index = s_blockSizeLookup[size];  
  59.     b2Assert(0 <= index && index < b2_blockSizes);  
  60.   
  61.     if (m_freeLists[index])  
  62.     {  
  63.         b2Block* block = m_freeLists[index];  
  64.         m_freeLists[index] = block->next;  
  65.         return block;  
  66.     }  
  67.     else  
  68.     {  
  69.         if (m_chunkCount == m_chunkSpace)  
  70.         { // 实现m_chunks数组动态增长  
  71.             b2Chunk* oldChunks = m_chunks;  
  72.             m_chunkSpace += b2_chunkArrayIncrement;  
  73.             m_chunks = (b2Chunk*)b2Alloc(m_chunkSpace * sizeof(b2Chunk));  
  74.             memcpy(m_chunks, oldChunks, m_chunkCount * sizeof(b2Chunk));  
  75.             memset(m_chunks + m_chunkCount, 0, b2_chunkArrayIncrement * sizeof(b2Chunk));  
  76.             b2Free(oldChunks);  
  77.         }  
  78.   
  79.         b2Chunk* chunk = m_chunks + m_chunkCount;  
  80.         chunk->blocks = (b2Block*)b2Alloc(b2_chunkSize);  
  81. #if defined(_DEBUG)  
  82.         memset(chunk->blocks, 0xcd, b2_chunkSize);  
  83. #endif  
  84.         int32 blockSize = s_blockSizes[index];  
  85.         chunk->blockSize = blockSize;  
  86.         int32 blockCount = b2_chunkSize / blockSize;  
  87.         b2Assert(blockCount * blockSize <= b2_chunkSize);  
  88.         for (int32 i = 0; i < blockCount - 1; ++i)  
  89.         {  
  90.             b2Block* block = (b2Block*)((int8*)chunk->blocks + blockSize * i);  
  91.             b2Block* next = (b2Block*)((int8*)chunk->blocks + blockSize * (i + 1));  
  92.             block->next = next;  
  93.         }  
  94.         b2Block* last = (b2Block*)((int8*)chunk->blocks + blockSize * (blockCount - 1));  
  95.         last->next = NULL;  
  96.   
  97.         m_freeLists[index] = chunk->blocks->next;  
  98.         ++m_chunkCount;  
  99.   
  100.         return chunk->blocks;  
  101.     }  
  102. }  

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分配的内存的:

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

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

阅读(1504) | 评论(0) | 转发(0) |
0

上一篇:Telnet模拟http请求

下一篇:Object-C 基本语法

给主人留下些什么吧!~~