做网站用哪个ecalipse,wordpress 业务逻辑,关于asp_sql网站开发的书籍,免费做优化的网站建设参考《STL源码剖析-侯捷》一书 (SGI版本STL)
前置
六大组件 空间配置器实现
SGI版本的空间配置器有两个#xff0c;一个名为allocator#xff0c;一个名为alloc。前者符合部分标准#xff0c;但效率不好#xff0c;只是对operator new和operator delete进行了封装#…参考《STL源码剖析-侯捷》一书 (SGI版本STL)
前置
六大组件 空间配置器实现
SGI版本的空间配置器有两个一个名为allocator一个名为alloc。前者符合部分标准但效率不好只是对operator new和operator delete进行了封装没有做过多的处理。 而普通的内存申请方式会导致几个问题
内存碎片的问题 首先对于内存碎片的问题很好理解。use代表已经分配了的内存free代表空闲空间。此时如果用户要求分配4kb的内存会发现找不到满足条件的内存块尽管总体剩下了5kb但是他们不是连续的 效率问题 假设用户当前需要1kb那么OS就给用户1kb然后待会又想要1kbOS又得跑去分配1kb的大小空间给用户这样就很头疼了。主要是因为每一次系统分配空间是需要从用户态转变为内核态的因为每一次分配空间都需要触发缺页中断(具体内容见内存管理之虚拟内存)直接使用malloc与new进行申请每块空间前有额外空间浪费具体看Glibc之malloc实现原理如果申请失败没有处理方案等等问题
所以为了解决上述问题STL采取了使用alloc来为容器管理空间。
具体实现思想
只贴少量代码具体代码看侯捷老师的书结合SGI版本的源码看这里主要理清楚思想
首先alloc主要分为两级空间配置器
一级空间配置器(__malloc_alloc_template)
思路非常简单大于128字节的内存申请使用一级空间配置器。其内部使用malloc()和free()两个C式接口完成内存开辟与释放。 开辟内存失败仿写了C中的set_new_handle()即自定义自己的out-of-memory handler。这个handle是函数指针作为回调函数的方式使用当要求内存配置需求无法被系统满足时在抛出bad_alloc异常之前调用一个你指定的函数也就是该handle指针指向的函数。
在当前SGI的处理中如果内存申请失败malloc返回NULL则会进入OOM_malloc函数也就是out_of_memory时的处理函数该函数不断内循环以期成功获取内存但如果没有自定义的内存获取失败处理函数也就是没有new_handle的话就直接抛异常。
template int inst//该非类型参数没派上用场所以在代码的最后一行直接传了0
class __malloc_alloc_template
{
private:static void* oom_malloc(size_t);
public:// 对malloc的封装static void* allocate(size_t n){// 申请空间成功直接返回失败交由oom_malloc处理void* result malloc(n);if (0 result)result oom_malloc(n);return result;}// 对free的封装static void deallocate(void* p, size_t /* n */){free(p);}// 模拟set_new_handle// 该函数的参数为函数指针返回值类型也为函数指针// void (* set_malloc_handler( void (*f)() ) )()static void (*set_malloc_handler(void (*f)()))(){void (*old)() __malloc_alloc_oom_handler;__malloc_alloc_oom_handler f;return(old);}
};
// malloc申请空间失败时代用该函数
template int inst
void* __malloc_alloc_templateinst::oom_malloc(size_t n)
{void (*my_malloc_handler)();void* result;for (;;){// 检测用户是否设置空间不足应对措施如果没有设置抛异常模式new的方式my_malloc_handler __malloc_alloc_oom_handler;if (0 my_malloc_handler){__THROW_BAD_ALLOC;}// 如果设置执行用户提供的空间不足应对措施(*my_malloc_handler)();// 继续申请空间可能就会申请成功result malloc(n);if (result)return(result);}
}
typedef __malloc_alloc_template0 malloc_alloc;二级空间配置器(__default_alloc_template) 小额区块带来的不仅是内存碎片配置时的额外负担也是一个大问题额外负担永远无法避免但是区块越小额外负担所占的比例就越大愈显得浪费------《STL源码剖析》 二级空间配置器的实现要比一级空间配置器复杂得多。 之所以采用小于等于128字节大小的空间使用二级空间配置器是因为SGI对于小块内存的定义为小于128字节。为了降低小块内存频繁申请的问题故采用二级空间配置器。 其内部最主要的实现思路就是内存池。另alloc默认采用二级空间配置器的模式进行内存分配。 在内存池中采用哈希桶的方式来提高用户获取空间的速度与高效管理。 哈希桶
当用户所需内存不满足哈希桶内的8的倍数的内存大小时SGI二级空间配置器将会将内存需求量上调至8的倍数。 其中每一个区块的节点如下方代码中union obj来维护第一个字段用来指向下一个相同大小的区块的指针第二个字段用来指向自己因此通过使用union的方式来节省维护链表的空间 分配策略如下
enum { __ALIGN 8 }; // 如果用户所需内存不是8的整数倍向上对齐到8的整数倍
enum { __MAX_BYTES 128 }; // 大小内存块的分界线
enum { __NFREELISTS __MAX_BYTES / __ALIGN }; // 采用哈希桶保存小块内存时所需桶的个数template bool threads, int inst//第一参数是多线程环境下使用的不做讨论太复杂第二参数没排上用场
class __default_alloc_template
{
private:// 如果用户所需内存块不是8的整数倍向上对齐到8的整数倍static size_t ROUND_UP(size_t bytes){return (((bytes)__ALIGN - 1) ~(__ALIGN - 1));}
private:union obj{union obj* free_list_link;char client_data[1];};
private:static obj* free_list[__NFREELISTS];// 哈希函数根据用户提供字节数找到对应的桶号static size_t FREELIST_INDEX(size_t bytes){return (((bytes)__ALIGN - 1) / __ALIGN - 1);}static void*refill(size_t n);// start_free与end_free用来标记内存池中大块内存的起始与末尾位置static char* start_free;static char* end_free;// 用来记录该空间配置器已经想系统索要了多少的内存块static size_t heap_size;public://在下面的代码块中展示就不放在一起了static void* allocate(size_t n);static void deallocate(void* p, size_t n);static void* reallocate(void* p,size_t old_sz,size_t new_sz);};// 函数功能向空间配置器索要空间
// 参数n: 用户所需空间字节数
// 返回值返回空间的首地址
//该函数是空间配置器的标准接口函数-allocate
static void* allocate(size_t n)
{obj* __VOLATILE* my_free_list;obj* __RESTRICT result;// 检测用户所需空间释放超过128(即是否为小块内存)if (n (size_t)__MAX_BYTES){// 不是小块内存交由一级空间配置器处理return (malloc_alloc::allocate(n));}// 根据用户所需字节找到对应的桶号my_free_list free_list FREELIST_INDEX(n);result *my_free_list;// 如果该桶中没有内存块时向该桶中补充空间if (result 0){// 将n向上对齐到8的整数被保证向桶中补充内存块时内存块一定是8的整数倍void* r refill(ROUND_UP(n));return r;}// 维护桶中剩余内存块的链式关系*my_free_list result-free_list_link;return (result);
};
static void* deallocate(void* p, size_t n);//头插到哈希桶具体不展示了不然太长了。可以查看相关源码allocate发现 free list 中没有可用区块了时 就调用 refill()准备为 free list 重新填空间。新的空间将由内存池(经chunk alloc()完成)。默认取得20 个新节点(新区块)但万一内存池空间不足获得的节点数 (区块数)可能小于 20。 refill流程图 refill代码
template int inst
char *__default_alloc_templateinst::chunk_alloc(size_t size, int nobjs)
{// 计算nobjs个size字节内存块的总大小以及内存池中剩余空间总大小char *result;size_t total_bytes size * nobjs;size_t bytes_left end_free - start_free;// 如果内存池可以提供total_bytes字节返回if (bytes_left total_bytes){result start_free;start_free total_bytes;return (result);}else if (bytes_left size){// nobjs块无法提供但是至少可以提供1块size字节内存块提供后返回nobjs bytes_left / size;total_bytes size * nobjs;result start_free;start_free total_bytes;return (result);}else{// 内存池空间不足连一块小块内存都不能提供// 向系统堆求助往内存池中补充空间// 计算向内存中补充空间大小本次空间总大小两倍 向系统申请总大小/16size_t bytes_to_get 2 * total_bytes ROUND_UP(heap_size 4);// 如果内存池有剩余空间(该空间一定是8的整数倍)将该空间挂到对应哈希桶中if (bytes_left 0){// 找对用哈希桶将剩余空间挂在其上obj **my_free_list free_list FREELIST_INDEX(bytes_left);((obj *)start_free)-free_list_link *my_free_list;*my_ree_list (obj *)start_free;}// 通过系统堆向内存池补充空间如果补充成功递归继续分配start_free (char *)malloc(bytes_to_get);if (0 start_free){// 通过系统堆补充空间失败在哈希桶中找是否有没有使用的较大的内存块int i;obj **my_free_list, *p;for (i size; i __MAX_BYTES; i __ALIGN){my_free_list free_list FREELIST_INDEX(i);p *my_free_list;// 如果有将该内存块补充进内存池递归继续分配if (0 ! p){*my_free_list p-free_list_link;start_free (char *)p;end_free start_free i;return (chunk_alloc(size, nobjs));}}// 山穷水尽只能向一级空间配置器求助// 注意此处一定要将end_free置空因为一级空间配置器一旦抛异常就会出问题end_free 0;start_free (char *)malloc_alloc::allocate(bytes_to_get);}// 通过系统堆向内存池补充空间成功更新信息并继续分配heap_size bytes_to_get;end_free start_free bytes_to_get;return (chunk_alloc(size, nobjs));}
}上述的 chunk_alloc() 函数以 end_free - start_free 来判断内存池的剩余容量。如果剩余容量充足就直接调出 20 个块返给free list。如果剩余容量不足以提供 20个区块但还足够供应一个以上的区块就拨出这不足 20 个区块的空间出去。这时候其 nobjs 参数将被修改为实际能够供应的区块数如果内存池连1个区块空间都无法供应此时便利用 malloc()从 heap 中配置内存为内存池分配更多空间以应付需求。新容量的大小为需求量的两倍再加上一个随着配置次数增加而愈来愈大的附加量。 举个例子假设调用 chunk_alloc(3220)(即需要20个32字节的区块)于是 malloc() 配置 40 个 32 bytes 区块其中第1个交出另19 个交给 free_list[3]维护余20个留给内存池。 调用chunk_alloc(64,20)此时 free list对应桶没有足够对应区块必须向内存池要求支持。 内存池只够供应10个64 bytes 区块就把这10个区块返回第1个交给用户余 9个由 free lst[7] 维护。此时内存池全空。接下来再调用 调用chunk_alloc(9620此时 free_list对应桶空空如也必须问内存池要求文持 而内存池此时也是空的于是以 malloc()配置40n (附加量)个96 bytes 区块其中第1个交出另19 个交给 free list[11] 维护余 20n (附加量)个区块留给内存池
以上差不多就是SGI空间配置器的基本原理想看详细分析的参见《STL源码剖析》。
