Nah Lock: 一个无锁的内存分配器 已翻译 100%

oschina 投递于 2014/11/17 07:12 (共 30 段, 翻译完成于 12-18)
阅读 4429
收藏 79
6
加载中

概述

我实现了两个完全无锁的内存分配器:_nalloc 和 nalloc。  我用benchmark工具对它们进行了一组综合性测试,并比较了它们的指标值。

与libc(glibc malloc)相比,第一个分配器测试结果很差,但是我从中学到了很多东西,然后我实现了第二个无锁分配器,随着核数增加至30,测试结果线性提高。核数增加至60,测试结果次线性提高,但是仅比tcmalloc好一点。

想要安装,输入命令: git clone ~apodolsk/repo/nalloc,阅读 README文档。

daxiang
daxiang
翻译于 2014/11/17 08:50
2

背景

内存分配器很重要,因为大多数的程序在使用它们,并且许多程序在大量使用它们.对于数以亿计的好程序而言,一个糟糕的分配器会是竞争的中心点;而一个好的分配器会是天上掉下来的替代品,用来扭转不良内存访问的程序为硬件友好的模式.

我所知道的所有可伸缩的内存分配器,包括已存的无锁分配器,通过拆分地址空间到CPU或线程局部子堆(subheap),尝试将分配过程转化为数据并行问题.在最好的情况下,这会带来优化位置,减少错误共享和增强预处理的额外好处,因为每个线程访问的是线程私有的高速缓存线的邻近集合.

gones945
gones945
翻译于 2014/11/25 23:11
2

在最糟糕的情况下,使用内存分配器的程序和分配器地址不是并行的,这样就需要小心的设计,来减少导致内存块在线程间转移的人为的或者显式的通讯.再者,能实现这点的可用选项,与减少内存碎片和内存崩溃的需要相冲突.

这里无需描述时序算法.

tcmalloc 和 jemalloc 是性能最好的通用分配器中的两个.ptmalloc是glibc默认的分配器.

gones945
gones945
翻译于 2014/11/26 23:30
2

分析和挑战

对于这个项目是否和这个教程相匹配,我有些信心不足.所以,对这个问题,我尝试着提出一些非明显的分析.我在介绍里面提到过,所以你可以略过此处.

我提到的"可变的数据并行"是一个新的难点.内存分配与我们在类中所见的所有问题形成鲜明的对比,因为它们可以在工作前做并行性分析.例如,在渲染器中,你可以通过这种方式处理,即允许数据不经过通讯来处理,这样来达到工作和间隔之间程序化的平衡.

gones945
gones945
翻译于 2014/11/27 23:07
3

另一方面,一个并行分配器,由未知的依赖提供预分配的,模糊的工作负载,这些依赖需要未知数量的通讯来解决.由此,它需要扩大到不同的并行级别.

实际上,这意味着我不得不花费大量的时间考虑,"如果工作负载强制线程大量通讯,这个选择有意义吗?是有意义还是无意义呢?".(在这个方向,我没有任何收获.根据我的测试,这些分配器的状态,看起来和最糟糕的情况一样.)

gones945
gones945
翻译于 2014/11/27 23:23
2

令我非常兴奋的是,一些设计问题与web服务器非常类似。像服务器一样,在突发的工作负载中,分配器需要满足延迟和吞吐量的目标,这通过平衡资源使用的目标,如减少碎片和崩溃,来实现。“分配更多的节点,甚至比需要的还多”和“从全局堆中获取更多的页,甚至比需要的还多”有类似的开销和益处,随着而来“启动开销”的问题也会浮现。

接下来提到的,是我碰到的没那么抽象的困难点。

gones945
gones945
翻译于 2014/11/30 11:14
1

__nalloc

介绍

__nalloc是"幼稚的",因为它可能是,我每个学期开始会用到的,几乎同样的基础设计.我假定瓶颈在同步控制,于是,我计划将一个快速的单线程算法,加入到高效的无锁包装器.如果我更倾向于分析,而不是"做听起来很优雅的事情",或者使用已存的只有大概轮廓的分配器,我所遇到的一些神奇的,暂未命名的问题,可能从一开始就会变得非常明显.

__nalloc和nalloc的目标分配大小均小于或等于1024B,这主要是为了让任务更简单.

主要想法如下:

  • 在每个局部线程子堆栈运行单线程的分配器 ("附有范围标识,以及易于分开与合并的隔离链表,").

  • 使用页的无锁栈,从全局堆中分配内存.

  • 使用属于每个线程的另一个无锁栈,返回移动的/"善变的"块到它们的原始线程.

gones945
gones945
翻译于 2014/12/01 21:49
1

下面是一个更详细的算法.如果觉得上面附加的描述言之有理,你可以略过此处.不管怎样,在最后提到的关于"善变的块"的部分很有意思:

  • 每个线程保留着各种大小空闲内存块的"空闲双链表".

  • 每个块位于一个"arena",它是一个页大小的块内存,地址和大小"自然对齐".线程通过从页的全局无锁栈获取更多的arena来填充空闲链表.

    • 当页的栈为空的时候,线程通过调用mmap()从OS分配一批页获取arena.

    • 每个新的arena保留这最大空间的单一块.

  • 在malloc()之中, 一个线程从栈里取出一个匹配请求大小的块.

    • 它削去多余的空间使之成为新的块.

    • 如果链表为空,它会尝试下一个最大的块,直到分配完毕而不得不获取新的arena.

  • 在free()之中, 一个线程会尽可能的合并空闲块及其相邻的部分.

    • 为了实现这点,每个块B需要4B的头信息来存储内存中"is_free"标识,B大小以及B的"左边"的大小.

    • 所有合并的相邻的空间都会从它们的空闲链表中删除.

  • 如果线程F释放了线程M分配的块B,线程F会将块B插入到一个与线程M相关联的"善变的"无锁栈.

    • 当线程M用完了块,它会在单个cmpxchg操作中取出整个栈的内容,然后将每个块加入到它的空闲链表.

    • 线程F如何找到这个链表呢?每个arena保留了线程"善变的"块的栈的指针.因为arena是自然对齐的,线程F可以根据线程B的地址计算线程B的arena的地址.

    • 每个arena也有一个内部栈存储"非自身占有的块".如果由于线程退出,而不得不在所有的块空闲之前释放arena,它会修改arena的"善变的块"指针指向"非自身占有的块"的栈.

gones945
gones945
翻译于 2014/12/02 23:35
2

基准测试

我编写了三个基准测试程序,分别在perf, gperftools和vtune中进行分析.

第一个测试中,每个线程随机分配,写入和释放到一个私有的内存池.

第二个测试中,线程分配到一个全局池,它实现为一个无锁栈的集合.

第三个测试中,单线程分配到一个全局池,其他线程从全局池中释放内存.

全部的工作负载在线程间保持恒定.分配大小限制到小于等于1024B.每个线程最大分配字节数受到限制,但是线程在释放旧的分配空间后,可以申请新的空间.全局时间使用gettimeofday()来计算时间间隔.

gones945
gones945
翻译于 2014/12/03 23:15
1

除了提到的,即将展示的图表是由第一个测试生成的.

按时间先后顺序优化和评论

我需要经常上下对齐地址.令人吃惊的是,我的align_up()和align_down()函数,只是一个增加或减少,以及取模运算,竟然占用了9%的运行时间.我为2的平方使用bitops来替换这些函数,之前的开销完全消除.它没有提升规模,但是我惊奇的发现,某种方式的算术中,div竟有如此大的差别.

我最初的设计是使用"arena"双链表而不是块.我原以为它会增加碎片和位置,以及,按顺序预取会耗尽arena.取而代之的是,线程通过O(n)的时间复杂度搜索成千上万个"不是足够满"的arena,寻找一个足够的连续空闲空间,来满足大的分配请求.像旋转arena之类的技巧起不到作用.

gones945
gones945
翻译于 2014/12/03 23:45
1
本文中的所有译文仅用于学习和交流目的,转载请务必注明文章译者、出处、和本文链接。
我们的翻译工作遵照 CC 协议,如果我们的工作有侵犯到您的权益,请及时联系我们。
加载中

评论(5)

虎爷
虎爷
擦,纯文章啊,没看到代码,也没看到链接
虎爷
虎爷
这个,实用么,还是说学习用的?
shines77
shines77
miss应该翻译成(缓存)未命中, hit翻译成(缓存)命中
calvinwilliams
calvinwilliams
我曾经设计过一个栈式堆内存池,申请使用完的堆内存块无需释放,内存池会帮你自动释放,或者托管以便下次重复申请时直接取用,还能自动释放fd、fp、自定义对象,降低了对程序员的要求。
daxiang
daxiang
静候对内存分配器熟悉的同学来翻译~
返回顶部
顶部