Performance von Floyd-Warshall in Haskell - Behebung eines Weltraumlecks

Zuerst einige allgemeine Codebereinigung:

In Ihrer Funktion fw ordnen Sie explizit veränderbare Vektoren zu und füllen diese. Für diesen genauen Zweck gibt es jedoch eine vorgefertigte Funktion, nämlich generate . fw kann daher als

Ebenso kann der Graph-Generierungscode durch replicate und accum ersetzt werden:

Beachten Sie, dass dadurch jegliche Notwendigkeit für eine Mutation vollständig beseitigt wird, ohne dass eine Leistung verloren geht.

Nun zu den eigentlichen Fragen:

1. Meiner Erfahrung nach ist deepseq sehr nützlich, aber nur als schnelle Lösung für Platzlecks wie diese. Das grundlegende Problem besteht nicht darin, dass Sie die Ergebnisse erzwingen müssen, nachdem Sie sie erstellt haben. Stattdessen bedeutet die Verwendung von deepseq , dass Sie die Struktur von Anfang an strikter aufgebaut haben sollten. In der Tat, wenn Sie ein Knallmuster in Ihrem Vektorerstellungscode wie folgt hinzufügen:

   %Vor%

   Dann ist das Problem behoben ohne deepseq . Beachten Sie, dass dies nicht mit dem generate -Code funktioniert, da vector aus irgendeinem Grund (ich könnte eine Feature-Anfrage dafür erstellen) keine strikten Funktionen für umrahmte Vektoren bietet. Wenn ich jedoch in der Antwort auf Frage 3 zu ungekoppelten Vektoren komme, die streng sind, arbeiten beide Ansätze ohne Striktheitsannotationen.

2. Soweit ich weiß, ist das Muster der wiederholten Erzeugung neuer Vektoren idiomatisch. Das einzige, was nicht idiomatisch ist, ist die Verwendung von Mutabilität - außer wenn sie unbedingt notwendig sind, werden mutable Vektoren im Allgemeinen davon abgeraten.

3. Es gibt ein paar Dinge zu tun:

   • Am einfachsten können Sie Map Int durch IntMap ersetzen. Da dies nicht wirklich der langsame Punkt der Funktion ist, spielt dies keine Rolle, aber IntMap kann bei hohen Arbeitslasten viel schneller sein.

   • Sie können zur Verwendung von nicht eingebetteten Vektoren wechseln. Obwohl der äußere Vektor eingerahmt bleiben muss, kann der innere Vektor sein, da Vektoren von Vektoren nicht entkoppelt werden können. Dies löst auch Ihr Striktheitsproblem - weil ungeschachtelte Vektoren in ihren Elementen streng sind, erhalten Sie kein Platzleck. Beachten Sie, dass dies auf meinem Computer die Leistung von 4,1 Sekunden auf 1,3 Sekunden verbessert, so dass das Unboxing sehr hilfreich ist.

   • Sie können den Vektor in einen einzigen reduzieren und Multiplikation und Division verwenden, um zwischen zweidimensionalen Indizes und einzelnen Indizes umzuschalten. Ich empfehle das nicht, da es ein bisschen involviert, ziemlich hässlich ist und aufgrund der Aufteilung den Code auf meinem Rechner verlangsamt.

   • Sie können repa verwenden. Dies hat den großen Vorteil, dass Sie Ihren Code automatisch parallelisieren. Beachten Sie, dass repa seine Arrays abflacht und die Divisionen, die zum Ausfüllen benötigt werden, anscheinend nicht korrekt entfernt (es ist möglich, verschachtelte Loops zu verwenden, aber ich denke, dass es eine einzelne Schleife und eine Division verwendet) gleiche Leistungseinbußen wie oben erwähnt, die Laufzeit von 1,3 Sekunden auf 1,8 bringen. Wenn Sie jedoch Parallelität aktivieren und einen Multicore-Computer verwenden, sehen Sie einige Vorteile. Unglücklicherweise ist dein aktueller Testfall zu klein, um viel Nutzen zu sehen. Also sehe ich ihn auf meiner 6-Kern-Maschine auf 1,2 Sekunden zurückfallen. Wenn ich die Größe wieder auf [1..v] anstelle von [1..50] zurückstelle, wird sie durch die Parallelität von 32 Sekunden auf 13 erhöht. Vermutlich, wenn Sie diesem Programm eine größere Eingabe geben, sehen Sie möglicherweise mehr Nutzen.

     Wenn Sie interessiert sind, habe ich meine repa -ifizierte Version hier gepostet.

   • BEARBEITEN: Verwende -fllvm . Testen auf meinem Computer, mit repa , bekomme ich 14,7 Sekunden ohne Parallelität, was fast so gut ist wie ohne -fllvm und mit Parallelität. Im Allgemeinen kann LLVM arraybasierten Code wie diesen sehr gut verarbeiten.