概述我实现了两个完全无锁的内存分配器：_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,这主要是为了让任务更简单.
主要想法如下:
下面是一个更详细的算法.如果觉得上面附加的描述言之有理,你可以略过此处.不管怎样,在最后提到的关于"善变的块"的部分很有意思:
基准测试 我编写了三个基准测试程序,分别在perf, gperftools和vtune中进行分析. 第一个测试中,每个线程随机分配,写入和释放到一个私有的内存池. 第二个测试中,线程分配到一个全局池,它实现为一个无锁栈的集合. 第三个测试中,单线程分配到一个全局池,其他线程从全局池中释放内存. 全部的工作负载在线程间保持恒定.分配大小限制到小于等于1024B.每个线程最大分配字节数受到限制,但是线程在释放旧的分配空间后,可以申请新的空间.全局时间使用gettimeofday()来计算时间间隔. 除了提到的,即将展示的图表是由第一个测试生成的. 按时间先后顺序优化和评论 我需要经常上下对齐地址.令人吃惊的是,我的align_up()和align_down()函数,只是一个增加或减少,以及取模运算,竟然占用了9%的运行时间.我为2的平方使用bitops来替换这些函数,之前的开销完全消除.它没有提升规模,但是我惊奇的发现,某种方式的算术中,div竟有如此大的差别. 我最初的设计是使用"arena"双链表而不是块.我原以为它会增加碎片和位置,以及,按顺序预取会耗尽arena.取而代之的是,线程通过O(n)的时间复杂度搜索成千上万个"不是足够满"的arena,寻找一个足够的连续空闲空间,来满足大的分配请求.像旋转arena之类的技巧起不到作用. Arena初始化消耗了15%的运行时间.在相关的ASM中,最耗时的指令是第一个MOV到内存的指令.这可能会令人讨厌,但是我碰巧得知Linux过量使用了内存.那就是,mmap()会保留虚拟地址,但是,它假定你并非实际需要内存,同时,在你真正使用之前,你不会获取物理帧.我认为arena_init是页面故障处理,为了实现那些新的VM映射.有人告诉我一个mmap的标识来取消过度使用. 这个堵塞了页面故障,但是余下的工作只是移动到mmap().我实现了一个批量和预取的组合(每个arena的分配也进行了N个其它的分配),从那时起,mmap()的消耗小于1%.这样运行并不明显,但是看起来可能最耗时的部分在VM片段树的查找.内核对每个请求只处理其中之一--明显的分阶段处理系统调用以及加锁的开销. 在这点上,你可能会争论,使用mmap(NULL, MAP_ANOP,...),_nalloc只是将疑难的常见分配问题转移到内核.但是,有人不管在什么情况下,都不得不调用mmap().同时,如果你打算抢占式的使用mmap()分配自己管理的大块内存,你无法取消过度使用.只要mmap的开销不占支配地位,这样做就是正确的事情.这可能是,我读过的许多无锁分配器论文,也认同这个技巧的原因.好奇于内核是否可以进行无锁分配,是一件有趣的事情.我简短的尝试过,并以失败告终,Linux使用了锁.但是Alexia Massalin在Synthesis之中将锁去掉了. 另一个不那么正确的事情是,我从未将内存返还给系统.释放后再使用可能会让页的栈出栈变得极其脆弱.这和我在无锁栈里面评论里提到的Bug是一样的.这颇具讽刺,因为评论也指出我的项目是因这个问题而萌发.如果我要解决这个问题,这会是一个假想的方案:在栈上面使用引用计数,只有在arena出栈时,引用计数为0才释放.你可以通过跟踪引用计数最后为0的标签值来检查.然后,在尝试释放时,检查页出栈的标签值是否小于等于上面提到的标签值. 在向Kayvon发邮件声称"正确"后,我认识到有非常糟糕和明显的竞态条件:
nalloc的设计对此也是脆弱的.我找到的一个解决方案(在接下来描述)在此不起作用.你可以为已分配的块数进行引用计数,它可能封闭线程"善变的"块的栈.会有一个更明智的(无锁的)方式,而不是通常的加锁指令的方式,来满足罕见的极端情况吗? |
