概述我实现了两个完全无锁的内存分配器：_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的设计对此也是脆弱的.我找到的一个解决方案(在接下来描述)在此不起作用.你可以为已分配的块数进行引用计数,它可能封闭线程"善变的"块的栈.会有一个更明智的(无锁的)方式,而不是通常的加锁指令的方式,来满足罕见的极端情况吗? 结果在这之后,一段长时间的修改Bug,下面是,理论上完美并行,无移动工作负载,在64核机器上的性能表现,:
这样, __nalloc和ptmalloc表现的一样差 (并不想我描述的那么差). 下面是gperftools的样本配置在GHC* 6核上面的性能表现:
*(在ALADDIN机器上,我没有获取到 libunwind/gperftools的配置) 下面是根据Linux perf得到的硬件计数器报告: Performance counter stats for './natest -t 6 -o 10000': 690,482,105 L1-dcache-loads 67,097,600 L1-dcache-misses # 9.72% of all L1-dcache hits [26.08%] 523,794,050 L1-dcache-stores 22,848,232 L1-dcache-misses 5,618,859 L1-dcache-prefetches 377,630 L1-dcache-misses 29,608,157 LLC-loads 14,276,385 LLC-misses # 48.22% of all LL-cache hits [21.63%] 45,153,262 LLC-stores 8,554,146 LLC-misses 6,247,900 LLC-prefetches 2,285,035 LLC-misses 389 page-faults 6,665,279,571 cpu-cycles 4,921,627,270 stalled-cycles-frontend # 73.84% frontend cycles idle 2,489,718,064 stalled-cycles-backend # 37.35% backend cycles idle 24,771,227 branch-misses 22,731,022 cache-misses # 46.787 % of all cache refs 48,583,721 cache-references 3,711,376,010 instructions # 0.56 insns per cycle # 1.33 stalled cycles per 0.415147303 seconds time elapsed 和tcmalloc对比: Performance counter stats for './tctest.sh -t 6 -o 10000': 691,325,411 L1-dcache-loads 18,485,376 L1-dcache-misses # 2.67% of all L1-dcache hits [27.18%] 403,827,409 L1-dcache-stores 6,107,731 L1-dcache-misses 1,874,221 L1-dcache-prefetches 397,279 L1-dcache-misses 5,351,265 LLC-loads 799,161 LLC-misses # 14.93% of all LL-cache hits [23.60%] 13,872,244 LLC-stores 2,803,597 LLC-misses 58,189 LLC-prefetches 6,720 LLC-misses 15,043 page-faults 1,679,857,462 cpu-cycles 566,843,996 stalled-cycles-frontend # 33.74% frontend cycles idle [23.33%] 515,528,620 stalled-cycles-backend # 30.69% backend cycles idle [23.07%] 5,163,499 branch-misses 2,378,294 cache-misses # 26.742 % of all cache refs [22.54%] 8,893,414 cache-references 2,850,831,772 instructions # 1.70 insns per cycle # 0.20 stalled cycles per insn [27.57%] 0.106878690 seconds time elapsed 需要指出的是,Linux sysfs在目标机器(ghc29)报告说到,当L1和L2对每个物理核心是局部缓存的时候,LL/L3缓存是共享的. __nalloc是有内存限制的. 它和tcmalloc一样,最多产生3.9x 的LLC引用,同时,最多导致6.3x的缺失.例如,对于每个free(), merge_adjacent()获取3个块头部,并插入到全局空闲链表.对于每个malloc(), shave获取3个块头部,并从空闲链表弹出.另一方面,tcmalloc的配置显示,它只是压入和弹出一个单链表. 最值得说的细节是,L1数据缓存加载只有9%的缺失,而在LLC中缺失了48%.这个效果在单线程的情况不存在.随着线程数量,分配数以及运行时间的增加,出现的概率也在增加.这样,_nalloc起初有足够的空间来适应工作集,然后就出现一些非预期的情况,给出上面的条件则更可能出现这样的效果. 我认为这是全局块链表的隐含代价.随着运行时间和分配数量的增加,在链表中相邻的块更可能来自不同的arena,每个arena可能已经被强制退出共享的LLC.当它获取这些块的时候,大多数分配强制加载多个高速缓存线到shave.如果malloc返回块处于"arena"无序状态,则free()更可能在这些块调用时处于更糟糕的状态,并在合并时,获取更多的外部高速缓存线. 这是纯单线程的效果--为什么在更多的线程的时候,情况会变得更糟糕呢?我认为,这是因为更多的线程导致访问超出了更多的arena.单线程程序可以为一个合适大小的块搜索所有的arena.但是在多个线程的情况下的一个线程,必须限制自身在子集之中,这样更可能使用mmap生成新的arena. 所以假设处于可怜的境地,即便是单线程的情况下,而在多线程未充分利用的情况下,结果会更糟糕.(这并不是我所听到的它使用的碎片--碎片是连续块"存在",但是你不能访问它,因为地址空间是分离的). 注意:在100%的并行基准测试中,不应该有冲突丢失--在同样的测试中,nalloc的低LLC丢失率反映了这种情况.回想一下,我应该通过某种方式来测试我的假设,而不是跳到一个新的分配器. 更新:在单线程情况下,我通过增加分配数进行"测试",得到了相同的缺失率.所以,实际上,这意味着我的序列算法先天不足,多线程未充分利用(或者其它属性)的时候,即_nalloc获取LLC的时候,情况更糟糕. 提到合并,除了全局链表,我找不到其它选择.我考虑过部分取消合并,保持单一的"当前arena"指针来检查,复杂度为O(1);或者,尝试提升链表中块的排序.但是418分配意味着,相比于改变简单的事情,增加复杂性看起来并不能获取益处. Alex的报告提到,它没有找到现代的合并访问分配器.我自己研究jemalloc,tcmalloc以及一些无锁malloc也没有任何发现.我觉得,我可能已经发现,为何每个人都避免合并访问了.在给定硬件后,他们一定认为这太幼稚太天真. nalloc介绍 我设计nalloc是为了低频率的,以一种更局部化的方式访问内存. 想法是使用同样的无锁包装器,但是使用"slab"分配来代替在arena间的合并访问.每个页/"slab"只提供单一大小的块.好处是,你无需存储头部,也无需检查邻近的块来分配或释放.你无需块的双链表,因为你不会"从中间删除".常见的分配是两次加载和一次存储,用来弹出有锁栈.缺点是,你会浪费空间. 算法:
如果你不在栈里为cmpxchg做循环计数,则时间复杂度为O(1). 最大的挑战是处理"善变的"块,如何以一种高效的方式,避免在_nalloc中的竞争或者其它竞争.考虑一些选择项(或者不考虑:可略过的),当线程M为slab S的所有者,同时线程F正在释放一个"善变的"块到S:
关键在于,M并非真正需要记录空slab.这样,在我上面描述的算法中,M有意的删除所有到S的引用,除了那些从S分配的块隐含的引用.如果F的插入会填满只包含善变的块的slab,那么M或者其它的任何线程都不会保留到S的引用,同时F可以对S任意操控.否则,F不能通知M,但M不会产生泄露,因为某个地方依旧保留着指向它的一个引用. 开心的是,"窃取"是我从开始就想支持的内容.假设你有一个生产者-消费者模型,消费者也需要内存.如果消费者已经将所有内存加载到缓存了,那么将所有的内存返还给生产者真的有意义吗?同时,即使"窃取"对于工作负载来说是不合适的,如果最后一个要加载slab到缓存的线程,就是释放它的线程,那么这样的效果会更好. 这个方案的代价是,你要么忍受冲突产生的丢失,要么为每个slab保留64B,用来将"善变的"块的栈从块的栈放入到不同的高速缓存线.对于大的slab,64B不算是太大的开销. 为了避免竞争,当尝试着查明slab是否为空,或者它是否只包含"善变的"块,我需要直接在我的无锁栈中存储一个大小值.我从标签字段获取了32位来存储. 当_nalloc中的arena链表没有工作的时候,slab栈会工作,因为每个slab可以保证满足一个特定大小的分配.它拥有我之前提到过的理论上的好处:在分配器以及使用内存的程序中的局部性,在分配器中的序列访问(查看下文),以及低碎片化(其它slab有更好的机会填充和释放).这是slab分配的一个优势,当我进行初始设计的时候我完全错过了--除了尝试和失败,我可能在任何情况下都不会发现它. 不像_nalloc中清除"善变的"栈的时间复杂度O(N),当stack_popall()交换时,弹出"善变的"块的时间复杂度为O(1).关键在于知道slab块的栈为空,这样,你就可以简单的移动"善变的"块的栈的栈顶节点到它上面,而无需断开链表. Intel的x86优化指南(和原因)指出,预取实际上会检测序列访问.所以slab也保留了起始于slab基底部的连续块段的大小.它们将更倾向于从段而不是从栈分配和释放(实际上,它们应该更倾向于从栈分配--我在后面实现了).这具备额外的效果,即让slab初始化的时间复杂度为O(1).因为在slab初始化后,栈的遍历字段不需要写入每个块. 未来的提升点可能在于使用两个栈--一个使用以前的顺序；一个严格按照降序,直到遇到连续段并添加。如果&second_stack->top处于同样的高速缓存线,那将花费很小的开销.(这听起来像更通用的算法的一个特殊情况.) 对于非少量分配的情况,这个算法缺乏一些合理性.对于每个位于0B和(FOO * 4096)B之间的16B,你不会真正拥有一个slab栈,但是你也不希望用1024B的块来满足513B的请求.另外,大的块由于头部而产生大的开销,所以,在那种情况下,你希望有大的slab--但是,如果没有完全使用,或者过量使用处于关闭状态,那么大的slab会浪费更多的内存.未来的提升点可能是,当它了解到是否需要为了速度而交换空间,以及是否浪费的空间会成为总使用空间的重大碎片时,弹性的放开块大小或过量使用开关(或者,为slab"善变的"块的栈,触发保留一个高速缓存线). 同时,通过一些修改,我认为,为了满足大的分配,使用空间有效的_nalloc可能变得合情合理.一个程序可能不会进行快速的大块分配而耗尽分配器,因为它会受制于用实际数据填充分配空间的时间(假设程序不会经常为大量事情一次性预分配空间). 我在完成设计后的唯一的优化是,用算术方法计算分配的大小来替代大小类查找表.这消除了5%的运行时.回想一下,这可能是因为全局LF栈的错误共享--我用__aligned__(64)来标记栈,因为担心这点,但是我并未标记表. 结果 结果根据上述准则生成。 nalloc在100%并行情况下，最终表现如下。
性能报告如下： Performance counter stats for './natest -t 6 -o 10000': 519,955,974 L1-dcache-loads 22,066,220 L1-dcache-misses # 4.24% of all L1-dcache hits [26.59%] 355,314,274 L1-dcache-stores 5,272,972 L1-dcache-misses 4,815,201 L1-dcache-prefetches 396,406 L1-dcache-misses 7,920,682 LLC-loads 1,391,780 LLC-misses # 17.57% of all LL-cache hits [22.11%] 12,972,675 LLC-stores 1,386,302 LLC-misses 14,266 LLC-prefetches 2,807 LLC-misses 384 page-faults 1,712,655,726 cpu-cycles # 0.000 GHz 692,724,604 stalled-cycles-frontend # 40.45% frontend cycles idle 492,748,671 stalled-cycles-backend # 28.77% backend cycles idle 7,614,825 branch-misses 2,800,160 cache-misses # 23.218 % of all cache refs 12,060,173 cache-references 2,413,914,436 instructions # 1.41 insns per cycle # 0.29 stalled cycles per insn [27.19%] 0.105481932 seconds time elapsed 它仍然有内存限制，但不是很严重。 相比于前面 tcmalloc 的表现，nalloc 更少的加载和存储。
重复的，上面表明 一个完美并行度的固定负载测试，线程随机分配、读写私有池，且空闲块 <=1024。线程间没有块移动。 结果看起来很好。在不到500LOC（提供的超过2000行复杂代码），nalloc与jemalloc和tcmalloc相比，它们各自有10000和20000 LOC。主要的一点是，nalloc的目标仅仅是一个测试和一个标准，剩下的是为生产准备的。许多知识都有差异和类似之处。但是，我认为这可能就是nalloc被设计用于覆盖不同地情况的原因。 在这些测试中llalloc是Lockless公司的Lockless分配器，这并不是100%无锁编程（它有一个锁在全局堆中）。运行时使用相同的测试，它比nalloc在串行下块两倍，但是这只是说其在64核实现的25x加速度。当以两倍长度运行时，它实现了相对于nalloc的约40x的加速度。在我的基准中，假设一次每线程（once-per-thread）的开销必须被控制，在那个阶段（大约用42ms时间来完成（time-to-completion）），但是我没有研究。 然而,我确信其它的分配器不会受到这的影响.但是,当问题大小增长的时候,它们表现的会更糟糕.同时,共享缓存可能会再次成为议题. 真正的无锁分配器,NBMalloc,Streamflow,以及Maged Michael实现的alloc,在ALADDIN上面都编译失败了(在我的机器上有两个编译失败了).我觉得,现在,我不应该尝试去解决这个问题. 对于64核的机器,完成时间的图表很难看懂,但是,我发现"工作"图表是并行和顺序执行特性的可读混合体.Y轴是线程数*完成时间(num_threads * time-to-completion).由于我期待着工作负载是平滑的分布,这就成为全部已做工作的一个大概统计.(相对于图中的曲线而言)好的斜率应该小于等于0.超过单一线程情况下(Y值)的Y值提供了近似的开销情况.
在第二个测试中,在线程分配和释放的全局池中,块的迁移非常高. 警告:这些测试有缺陷.请往下看.
在第三个测试中,单个线程生产块,供其它线程释放,块的迁移也非常高.
在第三个测试中,单个线程生产块,供其它线程释放,块的迁移也非常高. (此句原文中出现重复) 随着线程间通过全局池发送块的通讯开销占据主导,测试2和测试3会产生缺陷.在6核机器上运行测试2, 76%的运行时间花费在nalloc之外,大多数操作位于无锁栈之上.我已经将池划分为多个栈,同时%100保证栈位于不同的高速缓存线.测试需要重写,用来隐式的转换块,或者只是降低频率.在这点上,我宁愿加入Alex R.的探求,通过块迁移来查明真正的工作负载. 课程回顾
勘误表 "加速"可能是我的"性能"图表更具描述性的名字. 参考 |
