TCMalloc

Golang 竟然就用了鼎鼎大名的 TCMalloc
TCMalloc 是 Google 开发的内存分配器,在不少项目中都有使用,例如在 Golang 中就使用了类似的算法进行内存分配。它具有现代化内存分配器的基本特征:对抗内存碎片、在多核处理器能够 scale。据称,它的内存分配速度是 glibc2.3 中实现的 malloc的数倍。

如何分配定长记录?



首先是基本问题,如何分配定长记录?例如,我们有一个 Page 的内存,大小为 4KB,现在要以 N 字节为单位进行分配。为了简化问题,就以 16 字节为单位进行分配。



解法有很多,比如,bitmap。4KB / 16 / 8 = 32, 用 32 字节做 bitmap即可,实现也相当简单。



出于最大化内存利用率的目的,我们使用另一种经典的方式,freelist。将 4KB 的内存划分为 16 字节的单元,每个单元的前8个字节作为节点指针,指向下一个单元。初始化的时候把所有指针指向下一个单元;分配时,从链表头分配一个对象出去;释放时,插入到链表。



由于链表指针直接分配在待分配内存中,因此不需要额外的内存开销,而且分配速度也是相当快。



如何分配变长记录?
定长记录的问题很简单,但如何分配变长记录的。对此,我们把问题化归成对多种定长记录的分配问题。



我们把所有的变长记录进行“取整”,例如分配7字节,就分配8字节,31字节分配32字节,得到多种规格的定长记录。这里带来了内部内存碎片的问题,即分配出去的空间不会被完全利用,有一定浪费。为了减少内部碎片,分配规则按照 8, 16, 32, 48, 64, 80这样子来。注意到,这里并不是简单地使用2的幂级数,因为按照2的幂级数,内存碎片会相当严重,分配65字节,实际会分配128字节,接近50%的内存碎片。而按照这里的分配规格,只会分配80字节,一定程度上减轻了问题。



大的对象如何分配?
上面讲的是基于 Page,分配小于Page的对象,但是如果分配的对象大于一个 Page,我们就需要用多个 Page 来分配了:



这里提出了 Span 的概念,也就是多个连续的 Page 会组成一个 Span,在 Span 中记录起始 Page 的编号,以及 Page 数量。



分配对象时,大的对象直接分配 Span,小的对象从 Span 中分配。



Span如何分配?
对于 Span的管理,我们可以如法炮制:
还是用多种定长 Page 来实现变长 Page 的分配,初始时只有 128 Page 的 Span,如果要分配 1 个 Page 的 Span,就把这个 Span 分裂成两个,1 + 127,把127再记录下来。对于 Span 的回收,需要考虑Span的合并问题,否则在分配回收多次之后,就只剩下很小的 Span 了,也就是带来了外部碎片 问题。



为此,释放 Span 时,需要将前后的空闲 Span 进行合并,当然,前提是它们的 Page 要连续。



问题来了,如何知道前后的 Span 在哪里?
从Page到Span
由于 Span 中记录了起始 Page,也就是知道了从 Span 到 Page 的映射,那么我们只要知道从 Page 到 Span 的映射,就可以知道前后的Span 是什么了。



最简单的一种方式,用一个数组记录每个Page所属的 Span,而数组索引就是 Page ID。这种方式虽然简洁明了,但是在 Page 比较少的时候会有很大的空间浪费。



为此,我们可以使用 RadixTree 这种数据结构,用较少的空间开销,和不错的速度来完成这件事:



乍一看可能有点懵,这个跟 RadixTree 能扯上关系吗?可以把 RadixTree 理解成压缩过的前缀树(trie),所谓压缩,就是在一条路径上的节点都只有一个子节点,就把这条路径合并到父节点去,因此内部节点最少会有 Radix 个字节点
实现时,可以通过一定的空间换来时间,也就是减少层数,比如说3层。每层都是一个数组,用一个地址的前 1/3 的bit 索引数组,剩下的 bit 对下一层进行寻址。实际的寻址也可以非常快。



PageHeap
到这里,我们已经实现了 PageHeap,对所有 Page进行管理:
全局对象分配
既然有了基于 Page 的对象分配,和Page本身的管理,我们把它们串起来就可以得到一个简单的内存分配器了:
按照我们之前设计的,每种规格的对象,都从不同的 Span 进行分配;每种规则的对象都有一个独立的内存分配单元:CentralCache。在一个CentralCache 内存,我们用链表把所有 Span 组织起来,每次需要分配时就找一个 Span 从中分配一个 Object;当没有空闲的 Span 时,就从 PageHeap 申请 Span。



看起来基本满足功能,但是这里有一个严重的问题,在多线程的场景下,所有线程都从CentralCache 分配的话,竞争可能相当激烈。



ThreadCache
到这里 ThreadCache 便呼之欲出了:



每个线程都一个线程局部的 ThreadCache,按照不同的规格,维护了对象的链表;如果ThreadCache 的对象不够了,就从 CentralCache 进行批量分配;如果 CentralCache 依然没有,就从PageHeap申请Span;如果 PageHeap没有合适的 Page,就只能从操作系统申请了。



在释放内存的时候,ThreadCache依然遵循批量释放的策略,对象积累到一定程度就释放给 CentralCache;CentralCache发现一个 Span的内存完全释放了,就可以把这个 Span 归还给 PageHeap;PageHeap发现一批连续的Page都释放了,就可以归还给操作系统。



至此,TCMalloc 的大体结构便呈现在我们眼前了。



总结
这里用图解的方式简单讲述了 TCMalloc 的基本结构,如何减少内部碎片,如何减少外部碎片,如何使用伙伴算法进行内存合并,如何使用单链表进行内存分配,如何通过线程局部的方式提高扩展性。



不过实现一个高性能的内存分配器绝非如此简单,TCMalloc 中有许多策略,许多参数,许多细节的考量,都值得我们深究。
要使用TCMalloc,只要将tcmalloc通过“-ltcmalloc”链接器标志接入你的应用即可。



你也可以通过使用LD_PRELOAD在不是你自己编译的应用中使用tcmalloc:



$ LD_PRELOAD=”/usr/lib/libtcmalloc.so”



LD_PRELOAD比较讨巧,我们也不十分推荐这种用法。



TCMalloc还包含了一个堆检查器以及一个堆测量器。



如果你更想链接不包含堆测量器和检查器的TCMalloc版本(比如可能为了减少静态二进制文件的大小),你可以接入libtcmalloc_minimal。



=====================



VisualStudio 2005 / 2008(2010等应该一样,只不过没测试过)使用方法:



1.链接tcmalloc静态库



2.拷贝dll到工作目录



3.在强制符号引用中加入:__tcmalloc



4.重新编译、运行\



===================================



打开后发现有个libtcmalloc_minimal和一堆单元测试,libtcmalloc_minimal就是我想要的东东了。
编译这个项目,没错误。发现是个动态库,把编译出的libtcmalloc_minimal.dll libtcmalloc_minimal.lib 拿到测试工程文件夹里。
这个项目文件夹中 google-perftools-1.6/src/windows/google/tcmalloc.h 有个这个头文件,也拿到测试工程源代码里。
工程只要在链接器-》输入-》附加依赖项加入libtcmalloc_minimal.lib就可以了,编译执行,没问题。做测试可以看出没有替换原有的malloc,new,使用了自定义的tc_malloc这样的申请方式,比较下效率:
for(i = 0; i < 100000; i++) { char p = (char)malloc(i%1000); free(p); } 用时:0.331秒 占用内存852
for(i = 0; i < 100000; i++) { char p = (char)tc_malloc(i%1000); tc_delete(p); } 用时:0.009秒 占用内存1380 (会多用出500K左右的空间)
可以大概看出差距和机制,较多的使用空间来优化时间
================================



平时做项目不喜欢动态库,就想弄个静态库。静态搞起来麻烦一点:
1.把lib项目中 常规-》配置类型改成静态库
2.把 c/c++-》预处理器-》预处理定义中的_USRDLL;去掉
3.重新编译
4.把你的使用这个库的工程中config.h 和 tcmalloc.h中 # define PERFTOOLS_DLL_DECL //__declspec(dllimport) 后面这个注释掉
5.使用工程要 c/c++-》代码生成-》运行时库改成多线程MT(如果是debug就改成多线程调试,这在动态库版本中是不用改的)
6.链接器-》输入-》附加依赖项加入libtcmalloc_minimal.lib(这个是静态版本,比较大4.225MB 囧动态才164 + 54 KB)
7.链接器-》输入-》忽略指定库中填 libcmt.lib (debug版本libcmtd.lib)
8.这个挺好玩的 - 如果你在程序中没有调用 tc_xxx 这样的函数,那么与libcmt.lib冲突的这个库(也就是tcmalloc静态库)是不被链接到程序中的,程序会出现链接错误而导致程序通不过编译。只要你调用了,程序中的malloc 和 new就相当于被重载(这个用词不官方,就是这个意思)了。很好玩吧~!
9.编译执行



这样你的程序(频繁的申请释放内存)就可以跑得飞快了,这个库也比linux下的要好,linux下的大于128的时候就直接调用原生函数了。
用的时候别忘了google的这个项目是有版权的但的确是免费的,每页源代码上都有版权信息。
让我们的程序跑得更加疯狂吧
========================================



概览



TCMalloc给每个线程分配了一个线程局部缓存。小分配可以直接由线程局部缓存来满足。需要的话,会将对象从中央数据结构移动到线程局部缓存中,同时定期的垃圾收集将用于把内存从线程局部缓存迁移回中央数据结构中。



TCMalloc将尺寸小于<=
32K的对象(“小”对象)和大对象区分开来。大对象直接使用页级分配器(一个页是一个4K的对齐内存区域)从中央堆直接分配。即,一个大对象总是页对齐的并占据了整数个数的页。



连续的一些页面可以被分割为一系列小对象,而他们的大小都相同。例如,一个连续的页面(4K)可以被划分为32个128字节的对象。



小对象的分配



每个小对象的大小都会被映射到170个可分配的尺寸类别中的一个。例如,在分配961到1024字节时,都会归整为1024字节。尺寸类别这样隔开:较小的尺寸相差8字节,较大的尺寸相差16字节,再大一点的尺寸差32字节,如此类推。最大的间隔(对于尺寸 >= ~2K的)是256字节。



一个线程缓存对每个尺寸类都包含了一个自由对象的单向链表。



当分配一个小对象时:



我们将其大小映射到对应的尺寸类中。
查找当前线程的线程缓存中相应的自由列表。
如果自由列表不空,那么从移除列表的第一个对象并返回它。当按照这个快速通道时,TCMalloc不会获取任何锁。这就可以极大提高分配的速度,因为锁/解锁操作在一个2.8GHz Xeon上大约需要100纳秒的时间。



如果自由列表为空:



从该尺寸类别的中央自由列表(中央自由列表是被所有线程共享的)取得一连串对象。
将他们放入线程局部的自由列表。
将新获取的对象中的一个返回给应用程序。



如果中央自由列表也为空:(1) 我们从中央页分配器分配了一连串页面。(2) 将他们分割成该尺寸类的一系列对象。(4) 像前面一样,将部分对象移入线程局部的自由列表中。



大对象的分配



一个大对象的尺寸(> 32K)会被除以一个页面尺寸(4K)并取整(大于结果的最小整数),同时是由中央页面堆来处理的。中央页面堆又是一个自由列表的阵列。对于i < 256而言,第k个条目是一个由k个页面组成的自由列表。第256个条目则是一个包含了长度>= 256个页面的自由列表:



k个页面的一次分配通过在第k个自由列表中查找来完成。如果该自由列表为空,那么我们则在下一个自由列表中查找,如此继续。最终,如果必要的话,我们将在最后一个自由列表中查找。如果这个动作也失败了,我们将向系统获取内存(使用sbrk、mmap或者通过在/dev/mem中进行映射)。



如果k个页面的一次分配行为由连续的长度> k的页面满足了,剩下的连续页面将被重新插回到页面堆的对应的自由列表中。



跨度(Span)



TCMalloc管理的堆由一系列页面组成。连续的页面由一个“跨度”(Span)对象来表示。一个跨度可以是已被分配或者是自由的。如果是自由的,跨度则会是一个页面堆链表中的一个条目。如果已被分配,它会是一个已经被传递给应用程序的大对象,或者是一个已经被分割成一系列小对象的一个页面。如果是被分割成小对象的,对象的尺寸类别会被记录在跨度中。



由页面号索引的中央数组可以用于找到某个页面所属的跨度。例如,下面的跨度a占据了2个页面,跨度b占据了1个页面,跨度c占据了5个页面最后跨度d占据了3个页面。



在一个32位的地址空间中,中央阵列由一个2层的基数树来表示,其中根包含了32个条目,每个叶包含了 215个条目(一个32为地址空间包含了 220个 4K 页面,所以这里树的第一层则是用25整除220个页面)。这就导致了中央阵列的初始内存使用需要128KB空间(215*4字节),看上去还是可以接受的。



在64位机器上,我们将使用一个3层的基数树。



解除分配



当一个对象被解除分配时,我们先计算他的页面号并在中央阵列中查找对应的跨度对象。该跨度会告诉我们该对象是大是小,如果它是小对象的话尺寸类别是什么。如果是小对象的话,我们将其插入到当前线程的线程缓存中对应的自由列表中。如果线程缓存现在超过了某个预定的大小(默认为2MB),我们便运行垃圾收集器将未使用的对象从线程缓存中移入中央自由列表。



如果该对象是大对象的话,跨度会告诉我们该对象覆盖的页面的范围。假设该范围是[p,q]。我们还会查找页面p-1和页面q+1对应的跨度。如果这两个相邻的跨度中有任何一个是自由的,我们将他们和[p,q]的跨度接合起来。最后跨度会被插入到页面堆中合适的自由列表中。



小对象的中央自由列表



就像前面提过的一样,我们为每一个尺寸类别设置了一个中央自由列表。每个中央自由列表由两层数据结构来组成:一系列跨度和每个跨度一个自由对象的链表。



通过从某个跨度中移除第一个条目来从中央自由列表分配一个对象。(如果所有的跨度里只有空链表,那么首先从中央页面堆中分配一个尺寸合适的跨度。)



一个对象可以通过将其添加到他包含的跨度的链表中来返回到中央自由列表中。如果链表长度现在等于跨度中所有小对象的数量,那么该跨度就是完全自由的了,就会被返回到页面堆中。



线程缓存的垃圾收集



某个线程缓存当缓存中所有对象的总共大小超过2MB的时候,会对他进行垃圾收集。垃圾收集阈值会自动根据线程数量的增加而减少,这样就不会因为程序有大量线程而过度浪费内存。



我们会遍历缓存中所有的自由列表并且将一定数量的对象从自由列表移到对于得中央列表中。



从某个自由列表中移除的对象的数量是通过使用一个每列表的低水位线L来确定的。L记录了自上一次垃圾收集以来列表最短的长度。注意,在上一次的垃圾收集中我们可能只是将列表缩短了L个对象而没有对中央列表进行任何额外访问。我们利用这个过去的历史作为对未来访问的预测器并将L/2个对象从线程缓存自由列表中移到相应的中央自由列表中。这个算法有个很好的特性是,如果某个线程不再使用某个特定的尺寸时,该尺寸的所有对象都会很快从线程缓存被移到中央自由列表,然后可以被其他缓存利用。



性能备注



PTMalloc2单元测试



PTMalloc2包(现在已经是glibc的一部分了)包含了一个单元测试程序t-test1.c。它会产生一定数量的线程并在每个线程中进行一系列分配和解除分配;线程之间没有任何通信除了在内存分配器中同步。



t-test1(放在tests/tcmalloc/中,编译为ptmalloc_unittest1)用一系列不同的线程数量(1~20)和最大分配尺寸(64B~32KB)运行。这些测试运行在一个2.4GHz 双核心Xeon的RedHat 9系统上,并启用了超线程技术, 使用了Linux glibc-2.3.2,每个测试中进行一百万次操作。在每个案例中,一次正常运行,一次使用LD_PRELOAD=libtcmalloc.so。



下面的图像显示了TCMalloc对比PTMalloc2在不同的衡量指标下的性能。首先,现实每秒全部操作(百万)以及最大分配尺寸,针对不同数量的线程。用来生产这些图像的原始数据(time工具的输出)可以在t-test1.times.txt中找到。



TCMalloc要比PTMalloc2更具有一致地伸缩性——对于所有线程数量>1的测试,小分配达到了约7~9百万操作每秒,大分配降到了约2百万操作每秒。单线程的案例则明显是要被剔除的,因为他只能保持单个处理器繁忙因此只能获得较少的每秒操作数。PTMalloc2在每秒操作数上有更高的方差——某些地方峰值可以在小分配上达到4百万操作每秒,而在大分配上降到了<1百万操作每秒。
TCMalloc在绝大多数情况下要比PTMalloc2快,并且特别是小分配上。线程间的争用在TCMalloc中问题不大。
TCMalloc的性能随着分配尺寸的增加而降低。这是因为每线程缓存当它达到了阈值(默认是2MB)的时候会被垃圾收集。对于更大的分配尺寸,在垃圾收集之前只能在缓存中存储更少的对象。
TCMalloc性能在约32K最大分配尺寸附件有一个明显的下降。这是因为在每线程缓存中的32K对象的最大尺寸;对于大于这个值得对象TCMalloc会从中央页面堆中进行分配。



下面,CPU时间的每秒操作数(百万)以及线程数量的图像,最大分配尺寸64B~128KB。



这次我们再一次看到TCMalloc要比PTMalloc2更连续也更高效。对于<32K的最大分配尺寸,TCMalloc在大线程数的情况下典型地达到了CPU时间每秒约0.5~1百万操作,同时PTMalloc通常达到了CPU时间每秒约0.5~1百万,还有很多情况下要比这个数字小很多。在32K最大分配尺寸之上,TCMalloc下降到了每CPU时间秒1~1.5百万操作,同时PTMalloc对于大线程数降到几乎只有零(也就是,使用PTMalloc,在高度多线程的情况下,很多CPU时间被浪费在轮流等待锁定上了)。



注意



对于某些系统,TCMalloc可能无法与没有链接libpthread.so(或者你的系统上同等的东西)的应用程序正常工作。它应该能正常工作于使用glibc 2.3的Linux上,但是其他OS/libc的组合方式尚未经过任何测试。



TCMalloc可能要比其他malloc版本在某种程度上更吃内存,(但是倾向于不会有其他malloc版本中可能出现的爆发性增长。)尤其是在启动时TCMalloc会分配大约240KB的内部内存。



不要试图将TCMalloc载入到一个运行中的二进制程序中(例如,在Java中使用JNI)。二进制程序已经使用系统malloc分配了一些对象,并会尝试将它们传递到TCMalloc进行解除分配。TCMalloc是无法处理这种对象的。



TCMalloc全称Thread-Caching Malloc,即线程缓存的malloc,实现了高效的多线程内存管理,用于替代系统的内存分配相关的函数(malloc、free,new,new[]等)。
TCMalloc是gperftools的一部分,除TCMalloc外,gperftools还包括heap-checker、heap-profiler和cpu-profiler。本文只讨论gperftools的TCMalloc部分。
git仓库:https://github.com/gperftools/gperftools.git
官方介绍:https://gperftools.github.io/gperftools/TCMalloc.html



一)简介



    tcmalloc是与glibc、malloc同一级别的内存管理库,tcmalloc会hack所有glibc提供的接口,为调用者提供透明的内存分配。


(二)总体结构



PageHeap
内存管理单位:span(连续的page的内存)



CentralCache
内存管理单位:object(由span切成的小块,同一个span切出来的object都是相同的规格)



ThreadCache
线程私有的缓存,理想情况下,每个线程的内存需求都在自己的ThreadCache中完成,线程之间不需要竞争,非常高效。



内存管理单位:class(由span切成的小块)



(三)分配与回收



    基本思想:前面的层次分配内存失败,则从下一层分配一批补充上来;前面的层次释放了过多的内存,则回收一批到下一层次。


分配



1)小块内存(<256KB)。



ThreadCache:先尝试在list_[class]的FreeList分配。



CentralCache:找到对应class的tc_slots链表,从链表中分配 -> 从nonempty_链表分配(尽量分配batch_size个object)



HeadPage:伙伴系统对应的npages的span链表 (normal->returned)-> 更大的npages的span链表,拆小



kernel:申请若干个page的内存(可能大于npages)



2)大块内存(>256KB)。



HeadPage:伙伴系统对应的npages的span链表 (normal->returned)-> 更大的npages的span链表,拆小



kernel:申请若干个page的内存(可能大于npages)



回收
与申请流程类似



1)ThreadCache => CentralCache



ThreadCache容量限额:



a、为每一个ThreadCache初始化一个比较小的限额,然后每当ThreadCache由于cache超限而触发object到CentralCache的回收时,就增大限额。



b、预设所有ThreadCache的总容量,一个ThreadCache容量不够时,从其他ThreadCache收刮(轮询)。



c、每个ThreadCache也有最大最小值限制,不能无限增大限额。



d、每个ThreadCache超过限额时,对其每个FreeList回收。



单个FreeList的限额:



a、慢启动。初始长度限制为1,限额1~batch_size之间为慢启动,每次限额+1。



b、超过batch_size,限额按照batch_size整数倍扩展。



c、FreeList限额超限,直接回收batch_size个object。



2)CentralCache => PageHeap



只要一个span里面的object都空闲了,就将它回收到PageHeap。



3)PageHead中的normal => returned



a、每当PageHeap回收到N个page的span时(这个过程中可能伴随着相当数目的span分配),触发一次normal到returned的回收,只回收一个span。
b、这个N值初始化为1G内存的page数,每次回收span到returned链之后,可能还会增加N值,但是最大不超过4G。
c、触发回收的过程,每次进来轮询伙伴系统中的一个normal链表,将链尾的span回收即可。



(四)数据结构



PageHeap
1)page到span的映射关系通过radix tree来实现,逻辑上理解为一个大数组,以page的值作为偏移,就能访问到page对应的span节点。



2)为减少查询radix tree的开销,PageHeap还维护了一个最近最常使用的若干个page到object的对应关系cache。为了保持cache的效率,cache只提供64个固定坑位。



3)空闲span的伙伴系统为上层提供span的分配与回收。当需要的span没有空闲时,可以把更大尺寸的span拆小;当span回收时,又需要判断相邻的span是否空闲,以便组合他们



4)normal和returned:多余的内存放到returned中,与normal隔离。normal的内存总是优先被使用,kernel倾向于一直保留他们;而returned的内存不常被使用,kernel内存不足时优先swap他们。
CentralFreeList
1)维护span的链表,每个span下面再挂一个由这个span切分出来的object的链。便于在span内的object都已经free的情况下,将span整体回收给PageHeap;每个回收回来的object都需要寻找自己所属的span后才挂进freelist,比较耗时。



2)empty的span链和nonempty的span链:CentralFreeList中的span链表有nonempty_和empty_两个,根据span的object链是否有空闲,放入对应链表。如果span的内存已经用完则把这个span移到empty链表中。



3)通过页找到对应span:被CentralFreeList使用的span,都会把这个span上的所有页都注册到radixtree中,这样对于这个span上的任意页都可以通过页ID找到这个span。



4)如果span的内存已经完全被释放(span->refcount==0),则把这个span归还到PageHead中。
ThreadCache
1)tcmalloc为每个线程创建一个ThreadCache对象,当线程结束的时候,ThreadCache对象会随之销毁。



2)ThreadCache为每种类型的内存都保存了一个单项链表。



(五)适用场景



tcmalloc适用线程内小内存分配需求,一般情况下只有大空间分配才使用中央堆,中央堆分配回收我记得是需要加锁,成本高。



tcmalloc VS ptmalloc(glibc 2.3 malloc)
  对于小内存来说,tcmalloc提供线程级别的内存分配,这样就减少了线程之间的竞争,ptmalloc2也提供线程级别分配,但是它的内存被分配到某个线程后就不能重新分配给别的线程,这造成了较大的资源浪费。对于大内存来说,tcmalloc也采用了细粒度且高效的分配策略。
  在2.8 GHz P4环境下,tcmalloc执行小内存malloc/free的时间大约为50ns,小于ptmalloc2的300ns。
  另外在空间利用上,tcmalloc额外空间比较少,N个8字节的对象占用的总空间大概为8N*1.01,而ptmalloc2用4个字节管理每个对象,造成的空间利用率较小。
  
  


Category golang