SGI STL空间配置器和内存池
最近在看侯捷老师的《STL源码剖析》，非常感叹其中空间配置器实现的巧妙和细致，对效率真正是锱铢必较。
一般我们所习惯的内存配置和释放是通过new和delete来完成的，而new运算包含了两个阶段：1.调用::operator new配置内存 2.调用构造函数 Foo() 构造对象。delete运算也包含两个阶段：1.调用析构函数 ~Foo() 将对象析构 2.调用::operator delete释放内存。
1 #if 02 # include <new>3 # define __THROW_BAD_ALLOC throw bad_alloc4 #elif !define( __THROW_BAD_ALLOC)5 # include <iostream.h>6 #define __THROW_BAD_ALLOC cerr<<" out of memory "<<endl;exit(1)7 #endif
然后我们看二级配置器，它是以内存池 ( memory pool ) 来管理的：它由16个自由链表构成，每次配置一大块内存，并维护对应之自由链表 ( free-lists )，下次若有相同大小的内存请求，就直接从free-lists 中拨出这块内存，同时，如果客端释放小额区块时，刚把它回收到对应大小的自由链表 ( free-lists )中。
这16个肩负重任的 free-lists 分别管理大小为 8，16，24，32，40，56，64，72，80，88，96，104，112，120，128 bytes 大小的小额区块，所以当申请小额内存时，内存的需求量会被上调至 8 的倍数，以便于管理。接下来内存池就要登场了……
首先由空间配置函数 allocate() 进行空间的配置，如果能够在 free-lists 中找到对应大小的区块，就把对应的区块拨出，返回。否则就要调用 refill() 对 free-lists 进行填充，新的空间来自内存池，由 chunk_alloc() 完成。缺省是取得20个新区块，但如果内存池空间不足数量会小于20。取得的新区块，把第一块 return ,剩余的则维护到free-list中。
我们看下 chunk_alloc() 是怎么工作的：
从内存池是取出新空间可能发生三种情况
1. 内存池剩余量完全满足需求量
2. 内存池剩余量不能完全满足需求量，但足够供应 >= 1 个 区块
3. 内存池剩余量一个区块都不能供应
1 chunk_alloc(size, nobjs) 2 { 3 …… 4 5 if(bytes_left >= total_bytes) // 1.剩余量大于需求量 6 {……} 7 else if(bytes_left >= size) //2.能供应至少一个区块 8 {……} 9 else{10 …… //3.一个都不能供应11 }12 }首先我们看第一种情况：内存池剩余量完全满足需求量
这种情况是最好的情况，直接返回所需的区块就可以了
第二种情况： 内存池剩余量不能完全满足需求量，但足够供应 >= 1 个 区块
这种情况也好办，我们只要计算出实际能够供应的区块的个数，然后返回这些区块就可以了
剩下最后一种情况：内存池剩余量一个区块都不能供应
这种情况比较麻烦了，我们首先要进行 “善后” , 把剩余的这些残余的空间回收到 free-lists 中，然后才申请分配新的空间。申请新空间的大小为所需空间的2倍，再加上一个随着配置次数增加而增加的附加量。内存池向堆空间索要内存，用malloc(), 如果成功，则调整内存池的起点和终点，递归调用 chunk_alloc() 就行了,否则如果分配内存失败，就要想法从其它地方找点内存来用了，没错！就是 free-lists,向那些较大，且有剩余区块没用的free-list索要内存，如果找到了，就挖一块返回，调用chunk_alloc() 返回区块，否则就没办法了，只能调用一级配置器了，因为那里有out-of-memory处理例程，兴许还能找出点内存，如果能找到，那最好了，调用chunk_alloc()把区块返回给refill(),返回结果并调整free-lists，否则，真是天要亡我啊！只能抛出异常了……