TCMalloc
英文原文：
Nah Lock: A Lock-Free Memory Allocator
概述
我实现了两个完全无锁的内存分配器：_nalloc 和 nalloc。 我用benchmark工具对它们进行了一组综合性测试，并比较了它们的指标值。
与libc（glibc malloc）相比，第一个分配器测试结果很差，但是我从中学到了很多东西，然后我实现了第二个无锁分配器，随着核数增加至30，测试结果线性提高。核数增加至60，测试结果次线性提高，但是仅比tcmalloc好一点。
想要安装，输入命令： git clone ~apodolsk/repo/nalloc，阅读 README文档。
背景
内存分配器很重要,因为大多数的程序在使用它们,并且许多程序在大量使用它们.对于数以亿计的好程序而言,一个糟糕的分配器会是竞争的中心点;而一个好的分配器会是天上掉下来的替代品,用来扭转不良内存访问的程序为硬件友好的模式.
我所知道的所有可伸缩的内存分配器,包括已存的无锁分配器,通过拆分地址空间到CPU或线程局部子堆(subheap),尝试将分配过程转化为数据并行问题.在最好的情况下,这会带来优化位置,减少错误共享和增强预处理的额外好处,因为每个线程访问的是线程私有的高速缓存线的邻近集合.
在最糟糕的情况下,使用内存分配器的程序和分配器地址不是并行的,这样就需要小心的设计,来减少导致内存块在线程间转移的人为的或者显式的通讯.再者,能实现这点的可用选项,与减少内存碎片和内存崩溃的需要相冲突.
这里无需描述时序算法.
tcmalloc 和 jemalloc 是性能最好的通用分配器中的两个.ptmalloc是glibc默认的分配器.
分析和挑战
对于这个项目是否和这个教程相匹配,我有些信心不足.所以,对这个问题,我尝试着提出一些非明显的分析.我在介绍里面提到过,所以你可以略过此处.
我提到的"可变的数据并行"是一个新的难点.内存分配与我们在类中所见的所有问题形成鲜明的对比,因为它们可以在工作前做并行性分析.例如,在渲染器中,你可以通过这种方式处理,即允许数据不经过通讯来处理,这样来达到工作和间隔之间程序化的平衡.
另一方面,一个并行分配器,由未知的依赖提供预分配的,模糊的工作负载,这些依赖需要未知数量的通讯来解决.由此,它需要扩大到不同的并行级别.
实际上,这意味着我不得不花费大量的时间考虑,"如果工作负载强制线程大量通讯,这个选择有意义吗?是有意义还是无意义呢?".(在这个方向,我没有任何收获.根据我的测试,这些分配器的状态,看起来和最糟糕的情况一样.)
令我非常兴奋的是，一些设计问题与web服务器非常类似。像服务器一样，在突发的工作负载中，分配器需要满足延迟和吞吐量的目标,这通过平衡资源使用的目标,如减少碎片和崩溃,来实现。“分配更多的节点,甚至比需要的还多”和“从全局堆中获取更多的页,甚至比需要的还多”有类似的开销和益处，随着而来“启动开销”的问题也会浮现。
接下来提到的,是我碰到的没那么抽象的困难点。
__nalloc
介绍
__nalloc是"幼稚的",因为它可能是,我每个学期开始会用到的,几乎同样的基础设计.我假定瓶颈在同步控制,于是,我计划将一个快速的单线程算法,加入到高效的无锁包装器.如果我更倾向于分析,而不是"做听起来很优雅的事情",或者使用已存的只有大概轮廓的分配器,我所遇到的一些神奇的,暂未命名的问题,可能从一开始就会变得非常明显.
__nalloc和nalloc的目标分配大小均小于或等于1024B,这主要是为了让任务更简单.
主要想法如下:
-
在每个局部线程子堆栈运行单线程的分配器 ("附有范围标识,以及易于分开与合并的隔离链表,").
-
使用页的无锁栈,从全局堆中分配内存.
-
使用属于每个线程的另一个无锁栈,返回移动的/"善变的"块到它们的原始线程.
下面是一个更详细的算法.如果觉得上面附加的描述言之有理,你可以略过此处.不管怎样,在最后提到的关于"善变的块"的部分很有意思:
每个线程保留着各种大小空闲内存块的"空闲双链表".
每个块位于一个"arena",它是一个页大小的块内存,地址和大小"自然对齐".线程通过从页的全局无锁栈获取更多的arena来填充空闲链表.
在malloc()之中, 一个线程从栈里取出一个匹配请求大小的块.
在free()之中, 一个线程会尽可能的合并空闲块及其相邻的部分.
如果线程F释放了线程M分配的块B,线程F会将块B插入到一个与线程M相关联的"善变的"无锁栈.
当线程M用完了块,它会在单个cmpxchg操作中取出整个栈的内容,然后将每个块加入到它的空闲链表.
线程F如何找到这个链表呢?每个arena保留了线程"善变的"块的栈的指针.因为arena是自然对齐的,线程F可以根据线程B的地址计算线程B的arena的地址.
每个arena也有一个内部栈存储"非自身占有的块".如果由于线程退出,而不得不在所有的块空闲之前释放arena,它会修改arena的"善变的块"指针指向"非自身占有的块"的栈.
基准测试
我编写了三个基准测试程序,分别在perf, gperftools和vtune中进行分析.
第一个测试中,每个线程随机分配,写入和释放到一个私有的内存池.
第二个测试中,线程分配到一个全局池,它实现为一个无锁栈的集合.
第三个测试中,单线程分配到一个全局池,其他线程从全局池中释放内存.
全部的工作负载在线程间保持恒定.分配大小限制到小于等于1024B.每个线程最大分配字节数受到限制,但是线程在释放旧的分配空间后,可以申请新的空间.全局时间使用gettimeofday()来计算时间间隔.
除了提到的,即将展示的图表是由第一个测试生成的.
按时间先后顺序优化和评论
我需要经常上下对齐地址.令人吃惊的是,我的align_up()和align_down()函数,只是一个增加或减少,以及取模运算,竟然占用了9%的运行时间.我为2的平方使用bitops来替换这些函数,之前的开销完全消除.它没有提升规模,但是我惊奇的发现,某种方式的算术中,div竟有如此大的差别.
我最初的设计是使用"arena"双链表而不是块.我原以为它会增加碎片和位置,以及,按顺序预取会耗尽arena.取而代之的是,线程通过O(n)的时间复杂度搜索成千上万个"不是足够满"的arena,寻找一个足够的连续空闲空间,来满足大的分配请求.像旋转arena之类的技巧起不到作用.
本文中的所有译文仅用于学习和交流目的，转载请务必注明文章译者、出处、和本文链接。
2KB翻译工作遵照
CC 协议，如果我们的工作有侵犯到您的权益，请及时联系我们。
2KB项目（www.2kb.com，源码交易平台）,提供担保交易、源码交易、虚拟商品、在家创业、在线创业、任务交易、网站设计、软件设计、网络兼职、站长交易、域名交易、链接买卖、网站交易、广告买卖、站长培训、建站美工等服务
