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上面都编译失败了(在我的机器上有两个编译失败了).我觉得,现在,我不应该尝试去解决这个问题. |
