Verbesserung Treap Umsetzung

Hier ist meine Implementierung einer Art Treap (mit impliziten Schlüsseln und einigen zusätzlichen Informationen in Knoten gespeichert): http://hpaste.org/42839/treap_with_implicit_keys Verbesserung Treap Umsetzung

Nach Angaben GC Profilierung nimmt 80% der Zeit für dieses Programm. Soweit ich weiß, wird dies durch die Tatsache verursacht, dass jedes Mal, wenn ein Knoten "modifiziert" wird, jeder Knoten auf dem Pfad zum Stamm neu erstellt wird.

Gibt es etwas, was ich hier tun kann, um die Leistung zu verbessern, oder muss ich in das Reich von ST Monad absteigen?

Quelle

2011-01-07 adamax

@adamax: Dieses Verhalten (alles bis zur Wurzel neu erstellen) ist in unveränderlichen Strukturen üblich, haben Sie rein funktionale Datenstrukturen von Chris Okasaki gelesen? http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf er schrieb mehrere Artikel dazu. –

Vielleicht sollten Sie dies überprüfen, indem Sie Ihr Programm mit '+ RTS -s -RTS' ausführen, da ich diese 80%, von denen Sie sprechen, nicht sehe, wenn ich mit 7.0.1 einen kurzen Lauf machte, sehe ich etwa 16% Zeit in GC. – ScottWest

@ScottWest: Ich kompiliere es mit ghc-O2 -prof --make test.hs und laufe mit ./test + RTS -s -RTS, es sagt% GC-Zeit 77,4% (77,4% verstrichen), die Gesamtzeit ist 8,7 Sekunden. Aber meine Ghc-Version ist 6.12.1. Nur aus Interesse, wie hoch ist die Gesamtzeit in Ihrem System? – adamax

Mit GHC 7.0.3, kann ich Ihr schweres GC Verhalten reproduzieren:

$ 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

Ich verbrachte 10 Minuten durch das Programm gehen. Hier ist, was ich tat, um:

Set GHC des -H Flagge, zunehmende Grenzen in der GC
prüfen Auspacken
verbessern inlining
Stellen Sie die erste Generation Zuweisungsbereich

Dies führt zu einer 10-fachen Beschleunigung und GC zu 45% der Zeit.

Um mit GHC Magie -H Flagge, können wir die Laufzeit einiges reduzieren:

$ 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

Nicht schlecht!

Die UNPACK-Pragmas auf den Tree Knoten werden nichts tun, also entfernen Sie diese.

Inlining update rasiert mehr Laufzeit aus:

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

ebenso wie inlining height

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

So, während es schnell ist, GC noch dominiert - da wir Zuordnung zu test, nachdem alle . Eine Sache, die wir tun können, ist die erste Generation Größe zu erhöhen:

$ 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

Und die Entfaltung Schwelle erhöht, wie Johnl vorgeschlagen, hilft ein wenig,

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

das, was ist, 10x schneller als wir begonnen ? Nicht schlecht.

Mit ghc-gc-tune können Sie Laufzeit als Funktion der -A sehen und -H,

Time and GC

Interessanterweise sind die besten Laufzeiten verwenden sehr große -A Werte, z.B.

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

Quelle

2011-04-17 00:16:27

Wow, das ist unglaublich! Ich habe ein ähnliches Verhalten mit ghc 6.12.1, die größte Beschleunigung wird durch Inlining 'update' und Einstellung der ersten Gengröße erreicht. Eine Frage, hast du vergessen, die Option "Größe" für -H einzuschließen? Just -H scheint nichts zu tun, während -H64m zum Beispiel tut. – adamax

Mit GHC 7 erhöht -H alle Grenzwerte für den GC –

Genauer gesagt ist -H eine Art "automatisches -A", es erhöht die -A-Einstellung, ohne jedoch den Gesamtspeicherverbrauch zu erhöhen. Dies ist möglich, weil wir GC kopieren, so dass zwischen großen GCs viel Speicher ungenutzt bleibt. Das Erhöhen von -A ist nicht immer eine gute Idee - in einigen Programmen wird es die Dinge wegen vermehrter Cache-Misses noch verschlimmern. –

Antwort

Verwandte Themen