今天， 总算把SGI STL default memory allocator 看懂了， 闲话少说， 先把结果拿出来。
实验的平台跟昨天一样， 实验的思路也没有变。 不过， 最后的数据是以昨天的数据为基准， 取百分比得到的。
图一， allocate 1000 次， memory request size from 8 -- 128 bytes
图二， allocate 10000 次， memory request size from 8 -- 128 bytes
结论很明显，
1. 随着allocate memory 次数的增加， STL allocator performance的优越性越能够得到体现， 图一， allocate 大致为 70 -- 80%， 而图二， 则为 40 -- 80%。
2. 唯一的疑问点就是， deallocate， 图一的结果是没有什么好说的， 但图二的结果并不是预期的， 我所认为的是 deallocate 所占百分比并不应过高， 毕竟在STL deallocator的操作只是链表的插入，百分比应变化不大啊？ 费解， 不过， 这里的deallocator只是把申请到的memory返回给free_list, 并没有真真还给系统。 先放着， 以后再看看。
接下来， 谈谈 SGI STL default memory allocator 的设计， 这里只谈谈第二级allocator, 针对的是小而频繁的allocation, 小指memory request < 128 bytes.
首先， 有两个概念， free_list 和 memory pool
1. free_list maintains lists of already allocated memory chunks from memory pool. There are totally 16 lists in the free_list array, corresponding to 8 bytes, 16 bytes, ... 128 bytes, respectively.
2. Memory pool is in charge of provide memory chunks when free_list is exausted or there is no chunks for the corresponding list item in the free_list.
The most complicated function in STL allocator is char* chunk_alloc(size_t size, int& nobjs), which is called in refill(size_t n). There are three cases in chunk_alloc.
1. There are enough memory in the memory pool:
In that case, just update the watermark of memory pool, and return the memory.
2. There are not sufficient memory in memory pool, although the memory in memory pool is larger than the requested size of a block:
In that case, update the watermark of memory pool, and return the memory.
3. There is no enough memory in memory pool:
a. In that case, first, calculate the size of memory to be allocated:
size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);b. Then collect the unused memory in memory pool, and merger them into the corresponding list item in free_list.
c. Now use C std library function malloc() to allocate memory from heap:
In that case, there are also two sub cases:
1. malloc fail: in that case, the usused memory in free_list will be examined and reassigned in free_list.
2. malloc success: update watemark of memory, and recursively call chunk_alloc(size_t, nobjs) to update nobjs.
大致就这么多， 有些细微的地方， 如为什么在计算memory size的时候， 要加上 ROUND_UP(heap_size>>4), 还是没有搞明白， 书上也没有写清楚。 不过， 整个memory pool 的管理有了比较透彻的了解。 它的优点在于避免了频繁的malloc(), 这个函数将会调用system call多次， overhead 确实很大。
明天继续下一章。
8:40:45 PM Monday, May 11, 2009