実装

Question

をtreap改善はここで（暗黙のキーとノードに保存されているいくつかの追加情報を）treapの一種の私の実装です：データGCをプロファイリングによるとhttp://hpaste.org/42839/treap_with_implicit_keys

は、このプログラムのために時間の80％を取ります。私が理解する限りでは、ノードが「変更される」たびに、ルートへのパス上の各ノードが再作成されるという事実が原因です。

私はパフォーマンスを向上させるためにここでできることがありますか、またはSTモナドの領域に降りていかなければなりませんか？

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プラグマは何もしないので、それらを削除します。我々は割り当てをテストしていることから、結局 - それは高速ですが、GCはまだ支配しているんだからheight

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

をインライン化するよう

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

：

インラインupdateは、より多くのランタイムをオフに剃ります。 、

$ 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が示唆されているように、展開のしきい値を増やす私たちが始めたよりも何を、10倍は速くなり

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

、少し助け：私たちが行うことができます ことの一つは、最初の世代のサイズを増やしています？悪くない。

ghc-gc-tuneを使用して

---

、あなたが-Aと-Hの機能としてランタイムを見ることができ、

興味深いことに、最高の実行時間は、例えば、非常に大きな-A値を使用

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