线程缓存(thread cache)

加锁(locking)

加锁的开销是比较大的（cpu要同步 cache），一般要几十个时钟周期，特别是 cpu 较多的时候，锁冲突概率大大增加。

malloc

不是在进入malloc就马上加锁，而是在 thread cache 耗尽后才加锁（用于从全局堆获取内存），加锁的频率被大大降低（通常情况下是几百倍）。

free

不是在每次 free 时都加锁，而是在 free 导致 local cache 空闲出整页内存时，才加锁将内存页交还给全局堆(global heap)。

radix-tree

tcmalloc 使用的核心数据结构是radix-tree ，这是trie-tree 的一个变种。tcmalloc 中的radix-tree更是大幅简化，相当于多层页表，32 位环境下是 2 层，64 位环境下是 3 层。这样，对一个指针的查找可以在O(1)
的时间内完成，并且可以查找范围（在合并内存页时是必须的）。

Hash 也是O(1)，但是Hash不能按范围查找，再加上其它一些缺陷(hash 冲突、rehash，O(1) 的常数项也较大等)，hash 不适合tcmalloc。

按尺寸分组

对小于一定尺寸(32K) 的malloc，每种尺寸在一些连续的内存页上分配。这被称为size-class，每种尺寸并不是完全等距的，请求的尺寸会按一定规则对齐到下一个size-class。

使用size-class，malloc 出的内存就不需要在相邻的内存上（紧邻在malloc出来的内存之前）做簿记(book keeping) 了。传统的malloc需要这样的簿记，以便free时能找到链接的块，并且得到正确的内存大小。

使用 size-class 不但可以省掉额外的内存消耗，并且，可以按 size-class对齐。

在malloc时，按请求的尺寸查找 相应的size-class，如果大于max-size-class（32k），就直接从全局堆分配，并且总是页对齐的。

free时，在radix-tree中查找free的内存地址，得到其所属的span（span就是一块连续多个页的内存），进而得到其它信息（如size-class等，如果是大块内存则直接从全局堆free）。对于小块内存，大多数情况下，剩下的事情就是一个简单的链表操作。如果这次free导致整个span空闲，就将span回收。

总结

tcmalloc 的巨大优势：

• 线程缓存，大幅减少了加锁，更有效利用cpu cache
• 使用size-class，减少了小块内存的book-keeping，并且能更好地对齐。

• 总的开销更低

其他相关文档

http://code.google.com/p/google-perftools/
General Information and Documentation
tcmalloc.html documentation in Chinese (against perftools 0.94)