我不是想重复<<STL源码剖析>>中第2章的内容,顺便广告一下,这本书写得很不错,看完那章回来就从http://www.sgi.com/tech/stl/download.html下载了一份源码,慢慢分析.
1,经典的内存池
为了满足一些小单位的频繁内存配置和回收,如果直接使用malloc()和free()等系统函数,将会使效率很低,同样也会造成很多内存碎片,加重系统垃圾回收的负担.内存池的设计初衷也正在此,将一大片内存一次配置,将小单位内存配置模拟OS的空闲块链,就相当于在中间增加了一层'软分配器',正如在主存和CPU之间增加的cache,小小的投入可以带来性能上的飞跃.但是,我们要问,为什么会这样?
这个问题可以从优秀的SGI STL中寻找答案.
2,SGI STL中的allocater
恰恰这份实现的STL并没有按标准,它是一个无参数的分配器,它有两套配置器,一个是
template <int __inst>
class __malloc_alloc_template;
只是一个简单的封装,其实还是用的C的malloc,从名字就可以看出来,当然它有自己的内存不足时的处理接口.另一个是
template <bool threads, int inst>
class __default_alloc_template;
这是我们需要研究的.可以在内部头文件stl_alloc.h中得到完整的源码.
它维护了一个空闲链的链表,共16个,每一个空闲链的块大小不同,分别是8,16,...,128,对于长为n的配置请求,如果n>128则调用第一套配置器,否则,将n上补成8的倍数,调用对应这16个链中的一个空闲链,从中摘一个块出来,如果链空,则再向后面的内存池请求一大块空间.总的看上去,它不是一个简单的单一的内存池策略,而是一个对不同大小的配置请求进行自适应的分配策略,具体情况如何不多说,下面分析性能.
3,性能的瓶颈在哪?
从应用的角度,操作比较少,简单来说无非是2个,申请allocate(n)和释放deallocate(n),申请的时候,如果空闲链非空,则只需摘一个块下来,速度是O(1),可以想像成几乎不需要时间.如果空闲链空,则需从后备池中拿一块出来,如果后备池中非空,拿过来也只需要摘一个大块,比如摘20个对应块长,当然还需要进行空闲链初始化,将它们链接起来,总的来说还是O(1),但是代价会稍大一些,可以想像成只需要极短的时间.非常不巧的时候,后备池可能也会空,这个时候就要从系统堆中申请或者从其它大小的空闲链中'偷',后者不能治本,而前者又只能回到malloc()调用,这里就是关键所在,如果这种非常不巧的情况发生得多,那性能就差,反之就好.此外,deallocate(n)没有这么多情况,只需要往空闲链中插入一个结点就行了,始终O(1).
这里是allocate(n) :
static void* allocate(size_t __n)
{
void* __ret = 0;
if (__n > (size_t) _MAX_BYTES) {
__ret = malloc_alloc::allocate(__n);
}
else {
_Obj* __STL_VOLATILE* __my_free_list
= _S_free_list + _S_freelist_index(__n);
// Acquire the lock here with a constructor call.
// This ensures that it is released in exit or during stack
// unwinding.
# ifndef _NOTHREADS
/*REFERENCED*/
_Lock __lock_instance;
# endif
_Obj* __RESTRICT __result = *__my_free_list;
if (__result == 0) <-------注意这里
__ret = _S_refill(_S_round_up(__n));
else {
*__my_free_list = __result -> _M_free_list_link;
__ret = __result;
}
}
return __ret;
};
如果空闲链空,则转由_S_refill()重填空闲链,传入的_S_round_up(n)是对n进行向上按8的倍数取整.再看_S_refill() :
template <bool __threads, int __inst>
void*
__default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
{
int __nobjs = 20;
char* __chunk = _S_chunk_alloc(__n, __nobjs); <-------注意这里
_Obj* __STL_VOLATILE* __my_free_list;
_Obj* __result;
_Obj* __current_obj;
_Obj* __next_obj;
int __i;
if (1 == __nobjs) return(__chunk);
__my_free_list = _S_free_list + _S_freelist_index(__n);
/* Build free list in chunk */ <-------这之后是把空闲链链起来
__result = (_Obj*)__chunk;
*__my_free_list = __next_obj = (_Obj*)(__chunk + __n);
for (__i = 1; ; __i++) {
__current_obj = __next_obj;
__next_obj = (_Obj*)((char*)__next_obj + __n);
if (__nobjs - 1 == __i) {
__current_obj -> _M_free_list_link = 0;
break;
} else {
__current_obj -> _M_free_list_link = __next_obj;
}
}
return(__result);
}
它是调用_S_chunk_alloc()从后备内存池拿内存,两个参数的意义是,n是小块大小,nobjs是要多少块,后者是引用传入,表示可以传出表示返回值,返回时表示实际上能满足的块数,默认是请求20块,但有可能内存不够这么多,再看_S_chunk_alloc() :
template <bool __threads, int __inst>
char*
__default_alloc_template<__threads, __inst>::_S_chunk_alloc(size_t __size,
int& __nobjs)
{
char* __result;
size_t __total_bytes = __size * __nobjs;
size_t __bytes_left = _S_end_free - _S_start_free;
if (__bytes_left >= __total_bytes) { <------剩余内存能够满足全部需求
__result = _S_start_free;
_S_start_free += __total_bytes;
return(__result);
} else if (__bytes_left >= __size) { <------剩余内存能够满足至少一个块的需求
__nobjs = (int)(__bytes_left/__size);
__total_bytes = __size * __nobjs;
__result = _S_start_free;
_S_start_free += __total_bytes;
return(__result);
} else { <-------剩余不够的情况
size_t __bytes_to_get = <--------注意这里的bytes_to_get怎么计算的
2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
// Try to make use of the left-over piece.
if (__bytes_left > 0) {
_Obj* __STL_VOLATILE* __my_free_list =
_S_free_list + _S_freelist_index(__bytes_left);
((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list;
*__my_free_list = (_Obj*)_S_start_free;
}
_S_start_free = (char*)malloc(__bytes_to_get); <-------转为用malloc()申请堆内存
if (0 == _S_start_free) {
size_t __i;
_Obj* __STL_VOLATILE* __my_free_list;
_Obj* __p;
// Try to make do with what we have. That can't
// hurt. We do not try smaller requests, since that tends
// to result in disaster on multi-process machines.
for (__i = __size;
__i <= (size_t) _MAX_BYTES;
__i += (size_t) _ALIGN) {
__my_free_list = _S_free_list + _S_freelist_index(__i);
__p = *__my_free_list;
if (0 != __p) {
*__my_free_list = __p -> _M_free_list_link;
_S_start_free = (char*)__p;
_S_end_free = _S_start_free + __i;
return(_S_chunk_alloc(__size, __nobjs));
// Any leftover piece will eventually make it to the
// right free list.
}
}
_S_end_free = 0; // In case of exception.
_S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);
// This should either throw an
// exception or remedy the situation. Thus we assume it
// succeeded.
}
_S_heap_size += __bytes_to_get; <-------也注意这里
_S_end_free = _S_start_free + __bytes_to_get;
return(_S_chunk_alloc(__size, __nobjs));
}
}
顺藤摸瓜终于摸到最后了,最终的内存分配还是用的malloc(),只是这样一种处理结构能够自适应的应付大量的小单元配置问题,可以把小单元的空间配置比成网络中的客户端请求,你在设计服务器程序,你想让这种宏观上的空间配置不会导致系统的灾难,同时又想性能达到最好,客户请求时需要allocate(),离开时需要deallocate(),在某一时间或某一小的时间段,请求被处理但又没离开的服务假设有n(t)个,则这个时候至少需要O(n(t))的空间在使用,如果在将来的任何时刻都不会比这个时刻的服务大(峰值),那么这样的配置器会保持最优的效率运行,因为它们始终都是在空间链里摘块.那么问题是在峰值到来之前,如果将来还有更大的服务请求,性能又会如何呢?
每次往内存池里灌'活水'时,从系统拿的内存大小都不一样,注意上面的:
size_t __bytes_to_get =
2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
total_bytes = 块大 * 20(某常数) <=128*20 = 常数
_S_round_up()是向上按8的倍数取整,这里的_S_heap_size又是什么呢?下面代码有
_S_heap_size += __bytes_to_get;
一开始值是0,也就是说它是堆上申请大小的总和(某时刻),>>4相当于/16,如果没有这个,那新获得的大小是前面全部大小的总和还要多一点,比如,如果某刻有10k大小的堆内存在使用,又需要重新申请时,就再申请一倍(10k),翻倍地在增长,这种情况有点太'激进'了,所以/16缓和一下,但是增长率还是指数的.
假设峰值情况最大规模为n(n个客户在服务且没有离开),不管之前的增长情况如何,malloc()被调用的次数t=O(log(n)),因为从系统申请的空间大小按次数指数增长,当然就内存的使用情况来看,越往后需要的大小越大,代价也会增大,总的来说还是能够使整体性能提高,因为malloc()的调用并不算频繁,而且可以自适应,很好的协调实际需求.
4,小结
SGI STL中的alloc是由两套分配器合作的,如果请求的是小单位空间则由默认配置器分配,从空闲链中按向上8的整数倍取整后的大小摘取块,如果链空则由后备内存池取20块,如果内存池空则向malloc()请求,且每次请求的大小会按指数增长率增长,以此适应不同的规范的需求.
rickone 2007/11
评论