我不是想重复<<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  

评论