[原创]Doug Lea's malloc(dlmalloc) 学习笔记（1）

cucook

转载请保持完整并注明出处：
http://cucook.cublog.cn
Doug Lea的malloc实现（一般称为dlmalloc）是glibc内存管理算法ptmalloc的原型，ptmalloc是在dlmalloc基础上针对多线程优化的实现。
dlmalloc是公认的性能相当出色的内存管理算法（侯捷先生的《池內春秋— Memory Pool 的設計哲學和無痛運用》提到过）。这个笔记是我学习dlmalloc的总结，把它写出来和大家共同研究，由于目前仍在学习中，因此难免会有错漏之处，欢迎大家指正。
这篇笔记是针对2.8.3版本的dlmalloc。当前版本的glibc所用的ptmalloc是基于2.7.x版本的dlmalloc的。2.8.x与之前的版本有一个很大的不同之处：使用树（bitwise digital trees (aka tries) ）管理大块空闲内存。另外，2.8.0的dlmalloc还进行了代码重构，代码与之前版本有较大变化。
废话少说，先先看看dlmalloc分配和释放内存的示意流程图，注意，是示意流程图，只能反映主要流程和思想。
分配流程


释放流程



主要流程还是很简单的，和一般的最优适配的内存管理算法没有什么不同，为什么dlmalloc算法快呢？主要原因是
使用"boundary tag"，使得合并空闲块的时间复杂度是O(1)（不算更新空闲链的时间）
针对每种大小的小空闲块，都有单独的链表
使用bitwise digital trees (aka tries)管理大块空闲块，树的相关操作的步骤受size_t的约束，对于32位的size_t，步骤是6到21步，大部分情况下，步骤较少。
大量使用位运算
具体的情况下回再写。

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/16402/showart_91217.html