1、动机
tcmalloc要比glibc2.3 malloc（基于ptmalloc2实现）要快，ptmalloc2调用一次malloc+free大概需要300ns（2.8GHz P4），而tcmalloc执行同样的操作仅需50ns。
tcmalloc降低了在多线程程序中的锁竞争情况。对于小对象，tcmalloc基本达到了零竞争（笔者注：从CentralHeap申请一次内存，足以支撑单线程长期使用，而不需要再次向CentralHeap申请内存）。对于大对象，tcmalloc尝试使用细粒度且高效的自旋锁（笔者注：没看懂，需要细看代码）
tcmalloc的另一个好处在于小对象的空间效率高。例如，分配N个8字节对象可能要使用大约8N*1.01字节的空间，即多用1%的内存空间。而ptmalloc2会为每个对象一个4字节的header，那么假如要求8字节对齐，那么最终N个8字节对象需要占用16N字节的空间。
2、使用方法
要使用tcmalloc，只要将tcmalloc通过-ltcmalloc连接到应用程序即可。
也可以使用LD_PRELOAD在不是你自己编译的应用程序中使用：
$ LD_PRELOAD="/usr/lib/libtcmalloc.so"
tcmalloc还包含一个堆检查器（heap checker）和堆测量器（heap profiler）。
如果你想链接不包含heap checker和heap profiler的tcmalloc（比如为了减少静态二进制文件的大小），你应该连接libtcmalloc_minimal
3、综述
tcmalloc为每个线程分配一个thread-local cache，小对象的分配直接从thread-local cache中分配。根据需要将对象从CentralHeap中移动到thread-local cache，同时定期的用垃圾回收器把内存从thread-local cache回收到Central free list中。
tcmalloc将<=32k的对象归类为小对象，小对象是从thread-local cache中分配的。>32k的称为大对象，大对象是直接使用页级分配器（page-level allocator）从Central page Heap中进行分配，即一个大对象总是按页对齐的。（笔者注：大对象的分配又是如何降低多线程竞争的情况的？）
4、小对象分配
每个小对象的大小都会被映射到与之接近的170个可分配的尺寸类别中（allocatable size-classes）。比如所有大小在961~1024字节之间的小对象都会被归整为1024字节。尺寸类别隔开规则：较小的尺寸相差8字节，较大的尺寸相差16字节，更大的尺寸相差32字节，以此类推，最大的尺寸间隔为256字节。
一个thread-local cache包含各size-class的对象组成的单链表，如图所示：
当分配小对象时：
- 将其映射到对应的size-class；
- 在当前线程的thread-local cache中查找对应size-class的free-list，如果free list非空，那么将链表上第一个对象移除并返回给应用，这样tcmalloc的内存分配不会产生任何锁竞争。这样极大的提高了内存分配速度，因为lock/unlock操作在一个2.8GHz Xeon上大约需要100ns；
- 如果free list为空，那么将从Central free list中批量获取一批对应size-class的对象，并将其添加到thread-local cache的对应链表上，后续同2。（笔者注：此处对CentralHeap的访问需要加锁）
- 如果Central free list也为空，那么将从中央页分配器（central page allocatpr）分配一系列页面（对应span），将其分割成一系列对应size-class的对象，并将新分配的对象添加到CentralHeap的链表上，后续同3。（笔者注：此处对central page allocatpr的访问也需要加锁）
5、大对象分配
大对象（>32k）由中央页堆（central page heap）分配，中央页堆是由空闲内存页表组成的数组，如下图所示。
分配k个页面：首先在地k个空闲内存链表上查找，如果该链表为空，那么就在下一个空闲内存链表中查找，以此类推，最终将在最后空闲内存链表中查找。如果该操作也失败，那么则向系统申请内存（笔者注：使用sbrk、mmap等向OS申请内存）。
6、Spans
tcmalloc管理的heap由一系列page组成，一系列连续的页面由一个span对象来表示。一个span可以是已被分配或者是空闲的。如果是空闲的，span会是一个页面堆链表中的一个条目。如果已被分配，它会或者是一个已经被传递给应用程序的大对象，或者是一个已经被分割成一系列小对象的一个页面。注意，如果被分割成小对象，对象的尺寸会被记录在span中。
tcmalloc利用radix tree来实现一个central array，其通过页面号索引来找到该页面所属的span对象（page->span映射），如下图苏所示：
7、释放
对一个对象释放时，先计算其页面号（笔者注：address >> 2获取页面号），并在central array中查找对应的span。span中记录了该对象是大是小，如果是小对象的话尺寸类型是多少。
如果是小对象，将其插入到当前线程cache对应的空闲内存链表中。如果线程cache超过了某个预定的大小（默认2M），那么便运行垃圾回收器将未使用的对象从线程缓存中移入Central free list中。
如果是大对象，span会告诉我们该对象包含的页面范围。假设该范围是[p,q]。tcmalloc还会查找页面p-1和页面q+1对应的span（笔者注：通过central array查询）。如果这两个span有任何一个是空闲的，将他们与[p,q]的span结合起来。最后将合并后的span插入到page heap中。
8、小对象的central free list
如上所述，我们为每个尺寸类型设置了一个central free list。Central free list由两层数据结构实现：一系列span和每个span对象上分割出来的一个空闲内存链表。
一个object是通过从某个span对象的空闲链表中取出一个条目来分配的，如果所有的跨度里只有空链表，那么首先从central page heap中分配一个尺寸合适的span。
一个object通过将其添加到对应span的空闲链表上来将内存返还给central free list。如果链表长度等于span对象中所有小对象的数量，那么该span就可以被返还给page heap。
9、thread cache的垃圾回收
thread cache会在所有object总大小超过2M时进行垃圾回收。当线程增多时，垃圾回收器或动态下调阈值（2M->others），从而保证不会浪费内存。
10、总结
如下图所示，tcmalloc的内存分配分为四层：
ThreadCache（用于小对象分配）：线程本地缓存，每个线程独立维护一个该对象，多线程在并发申请内存时不会产生锁竞争。
CentralCache（Central free list，用于小对象分配）：全局cache，所有线程共享。当thread cache空闲链表为空时，会批量从CentralCache中申请内存；当thread cache总内存超过阈值，会进行内存垃圾回收，将空闲内存返还给CentralCache。
Page Heap（小/大对象）：全局页堆，所有线程共享。对于小对象，当centralcache为空时，会从page heap中申请一个span；当一个span完全空闲时，会将该span返还给page heap。对于大对象，直接从page heap中分配，用完直接返还给page heap。
系统内存：当page cache内存用光后，会通过sbrk、mmap等系统调用向OS申请内存。
11、结合应用考虑
1）ThreadCache是面向pthread的，对于baidu-rpc，如果是隶属于一个pthread的多个bthread，其将复用同一个ThreadCahce。
2）非对称malloc/free：在应用代码中会出现如下场景，一个小对象是在A线程中分配，但是在B线程中释放。这会导致A线程会很快用光ThreadCache中分配的内存，需要重新从CentralCache中申请内存；而B线程则会很快达到2M阈值，从而向CentralCache返还内存。这种场景下tcmalloc的性能会表现不佳，因为访问CentralCache会出现多线程竞争，是一个加锁操作（100ns级别），因此在实际编码中尽量避免这类用法。
参考文献：
http://goog-perftools.sourceforge.net/doc/tcmalloc.html
