结果在这之后,一段长时间的修改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也没有任何发现.我觉得,我可能已经发现,为何每个人都避免合并访问了.在给定硬件后,他们一定认为这太幼稚太天真. |
