改善treap实施

Question

这是我对一种treap的实现(使用隐式键和一些存储在节点中的附加信息):http://hpaste.org/42839/treap_with_implicit_keys

根据分析数据,GC占用该程序80%的时间.据我所知,这是因为每次节点被"修改"时,都会重新创建到根节点的每个节点.

我能在这里做些什么来提高性能还是我必须进入ST monad的领域？

Answer 1

使用GHC 7.0.3,我可以重现您的重GC行为:

  $ time ./A +RTS -s
  %GC time      92.9%  (92.9% elapsed)
  ./A +RTS -s  7.24s user 0.04s system 99% cpu 7.301 total

我花了10分钟完成整个计划.这是我做的,按顺序:

• 设置GHC的-H标志,增加GC的限制
• 检查拆包
• 改善内联
• 调整第一代分配区域

结果加速10倍,GC约45%的时间.

为了使用GHC的魔术-H标志,我们可以减少运行时间:

  $ time ./A +RTS -s -H
  %GC time      74.3%  (75.3% elapsed)
  ./A +RTS -s -H  2.34s user 0.04s system 99% cpu 2.392 total

不错!

Tree节点上的UNPACK编译指示不会执行任何操作,因此请删除它们.

内联update削减更多运行时:

 ./A +RTS -s -H  1.84s user 0.04s system 99% cpu 1.883 total

内联也是如此 height

 ./A +RTS -s -H  1.74s user 0.03s system 99% cpu 1.777 total

因此,尽管速度很快,GC仍然占主导地位 - 毕竟,我们正在测试分配.我们可以做的一件事就是增加第一代尺寸:

 $ time ./A +RTS -s -A200M
 %GC time      45.1%  (40.5% elapsed)
 ./A +RTS -s -A200M  0.71s user 0.16s system 99% cpu 0.872 total

正如JohnL建议的那样,增加展开门槛会有所帮助,

 ./A +RTS -s -A100M  0.74s user 0.09s system 99% cpu 0.826 total

这是什么,比我们开始快10倍？不错.

使用GHC-GC-调,你可以看到运行时的一个函数-A和-H,

有趣的是,最佳运行时间使用非常大的-A值,例如

$ time ./A +RTS -A500M   
./A +RTS -A500M  0.49s user 0.28s system 99% cpu 0.776s