Performance von Floyd-Warshall in Haskell - Fixing ein Leck im Raum

Question

Ich wollte eine effiziente Implementierung der Floyd-Warshall alle Paare kürzester Weg Algorithmus in Haskell mit Vector s, um hoffentlich gute Leistung zu bekommen.

Die Implementierung ist recht einfach, aber anstatt ein 3-dimensionales | V | × | V | × | V | zu verwenden Matrix wird ein 2-dimensionaler Vektor verwendet, da wir immer nur den vorherigen k Wert lesen.

Somit ist der Algorithmus wirklich nur eine Reihe von Schritten, wo ein 2D-Vektor übergeben wird und ein neuer 2D-Vektor generiert wird. Der letzte 2D-Vektor enthält die kürzesten Wege zwischen allen Knoten (i, j).

Meine Intuition sagte mir, dass es wichtig wäre, um sicherzustellen, dass der vorherige 2D-Vektor vor jedem Schritt bewertet wurde, so habe ich BangPatterns auf das prev Argument die fw Funktion und die strengen foldl':

{-# Language BangPatterns #-} 

import   Control.DeepSeq 
import   Control.Monad  (forM_) 
import   Data.List   (foldl') 
import qualified Data.Map.Strict  as M 
import   Data.Vector   (Vector, (!), (//)) 
import qualified Data.Vector   as V 
import qualified Data.Vector.Mutable as V hiding (length, replicate, take) 

type Graph = Vector (M.Map Int Double) 
type TwoDVector = Vector (Vector Double) 

infinity :: Double 
infinity = 1/0 

-- calculate shortest path between all pairs in the given graph, if there are 
-- negative cycles, return Nothing 
allPairsShortestPaths :: Graph -> Int -> Maybe TwoDVector 
allPairsShortestPaths g v = 
    let initial = fw g v V.empty 0 
     results = foldl' (fw g v) initial [1..v] 
    in if negCycle results 
     then Nothing 
     else Just results 
    where -- check for negative elements along the diagonal 
     negCycle a = any not $ map (\i -> a ! i ! i >= 0) [0..(V.length a-1)] 

-- one step of the Floyd-Warshall algorithm 
fw :: Graph -> Int -> TwoDVector -> Int -> TwoDVector 
fw g v !prev k = V.create $ do           -- ← bang 
    curr <- V.new v 
    forM_ [0..(v-1)] $ \i -> 
    V.write curr i $ V.create $ do 
     ivec <- V.new v 
     forM_ [0..(v-1)] $ \j -> do 
     let d = distance g prev i j k 
     V.write ivec j d 
     return ivec 
    return curr 

distance :: Graph -> TwoDVector -> Int -> Int -> Int -> Double 
distance g _ i j 0 -- base case; 0 if same vertex, edge weight if neighbours 
    | i == j = 0.0 
    | otherwise = M.findWithDefault infinity j (g ! i) 
distance _ a i j k = let c1 = a ! i ! j 
         c2 = (a ! i ! (k-1))+(a ! (k-1) ! j) 
         in min c1 c2 

Wenn jedoch dieses Programm mit einem 1000-Node-Graphen mit 47978 Kanten ausgeführt wird, sieht die Sache gar nicht gut aus. Die Speicherauslastung ist sehr hoch und das Programm dauert viel zu lange. Das Programm wurde mit ghc -O2 kompiliert.

umgebaut ich das Programm für die Profilierung und begrenzt die Anzahl der Iterationen bis 50:

:

results = foldl' (fw g v) initial [1..50] 

ich das Programm mit +RTS -p -hc und +RTS -p -hd dann lief

Das ist ... interessant, aber ich denke, es zeigt, dass es acc ist Umhüllen von Tonnen von Thunks. Nicht gut.

Ok, also nach ein paar Schüsse in der Dunkelheit, fügte ich ein deepseq in fw um sicherzustellen, dass prevwirklich ist evaluted:

let d = prev `deepseq` distance g prev i j k 

Nun liegen die Dinge besser aussehen, und ich kann das Programm tatsächlich laufen zur Vervollständigung mit konstanter Speichernutzung. Es ist offensichtlich, dass der Knall auf dem Argument prev nicht genug war.

Zum Vergleich mit den vorherigen Graphen, hier ist der Speicherverbrauch für 50 Iterationen nach der deepseq Zugabe:

Ok, so sind die Dinge besser, aber ich habe noch einige Fragen:

1. Ist das die richtige Lösung für dieses Raumleck? Ich habe das Gefühl, dass das Einfügen eines deepseq ein bisschen hässlich ist?
2. Ist meine Verwendung von Vector hier idiomatisch/korrekt? Ich baue für jede Iteration einen komplett neuen Vektor und hoffe, dass der Garbage Collector die alten Vector s löschen wird.
3. Gibt es noch andere Dinge, die ich tun könnte, um das mit diesem Ansatz schneller zu machen?

Für Referenzen, hier ist graph.txt: http://sebsauvage.net/paste/?45147f7caf8c5f29#7tiCiPovPHWRm1XNvrSb/zNl3ujF3xB3yehrxhEdVWw=

Hier ist main:

main = do 
    ls <- fmap lines $ readFile "graph.txt" 
    let numVerts = head . map read . words . head $ ls 
    let edges = map (map read . words) (tail ls) 
    let g = V.create $ do 
     g' <- V.new numVerts 
     forM_ [0..(numVerts-1)] (\idx -> V.write g' idx M.empty) 
     forM_ edges $ \[f,t,w] -> do 
      -- subtract one from vertex IDs so we can index directly 
      curr <- V.read g' (f-1) 
      V.write g' (f-1) $ M.insert (t-1) (fromIntegral w) curr 
     return g' 
    let a = allPairsShortestPaths g numVerts 
    case a of 
    Nothing -> putStrLn "Negative cycle detected." 
    Just a' -> do 
     putStrLn $ "The shortest, shortest path has length " 
       ++ show ((V.minimum . V.map V.minimum) a') 

Answer 1

Zunächst einige allgemeine Code Cleanup:

In Ihrer fw Funktion explizit zuweisen und füllen veränderbare Vektoren. Es gibt jedoch eine vorgefertigte Funktion für genau diesen Zweck, nämlich generate. fw kann daher als

V.generate v (\i -> V.generate v (\j -> distance g prev i j k)) 

Ebenso neu geschrieben werden, kann der Graph Generation Code mit replicate und accum ersetzt:

let parsedEdges = map (\[f,t,w] -> (f - 1, (t - 1, fromIntegral w))) edges 
let g = V.accum (flip (uncurry M.insert)) (V.replicate numVerts M.empty) parsedEdges 

Beachten Sie, dass dies völlig alle Notwendigkeit beseitigt für eine Mutation, ohne eine Leistung zu verlieren.

Nun zu den eigentlichen Fragen:

1. Nach meiner Erfahrung deepseq ist sehr nützlich, aber nur als schnelle Lösung, um Platz Lecks wie dieser. 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 in erster Linie strenger gebaut haben sollten. In der Tat, wenn Sie ein Knall-Muster in Ihrem Vektor Erstellungscode hinzufügen wie folgt:

   let !d = distance g prev i j k 
   

   Dann wird das Problem ohne deepseq fixieren. Beachten Sie, dass dies nicht mit dem generate-Code funktioniert, da aus irgendeinem Grund (ich könnte eine Feature-Anforderung für diese erstellen) vector bietet keine strengen Funktionen für verpackte Vektoren. Wenn ich jedoch in der Antwort auf die Frage 3, die strikt sind, zu entkoffeinierten Vektoren komme, arbeiten beide Ansätze ohne Striktheitsanmerkungen.

2. Soweit ich weiß, ist das Muster der wiederholten Generierung neuer Vektoren idiomatisch. Das einzige, was nicht idiomatisch ist, ist die Verwendung von Veränderlichkeit - außer wenn sie unbedingt notwendig sind, wird von mutablen Vektoren generell abgeraten.

3. Es gibt ein paar Dinge zu tun:

   • Am einfachsten Sie Map Int mit IntMap ersetzen kann. Da dies nicht wirklich der langsame Punkt der Funktion ist, spielt dies keine große Rolle, aber IntMap kann bei hohen Arbeitslasten viel schneller sein.

   • Sie können zur Verwendung von ungeboxten 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 kompliziert ist, ziemlich hässlich und aufgrund der Aufteilung sogar den Code auf meinem Rechner verlangsamt.

   • können Sie 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, nicht richtig entfernt (es ist möglich, verschachtelte Loops zu verwenden, aber ich denke, dass es eine einzelne Schleife und eine Division verwendet), hat dieselbe Leistung Strafe wie ich oben erwähnt habe, bringt die Laufzeit von 1,3 Sekunden auf 1,8. 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 zurück auf [1..v] statt [1..50], die Parallelität bringt es von 32 Sekunden auf 13. Vermutlich, wenn Sie dieses Programm eine größere Eingabe geben, können Sie mehr Nutzen sehen.

     Wenn Sie interessiert sind, habe ich meine repa -ifizierte Version here veröffentlicht.

   • EDIT: Verwenden Sie -fllvm. Testen auf meinem Computer, mit repa, bekomme ich 14,7 Sekunden ohne Parallelität, die fast so gut ist wie ohne -fllvm und mit Parallelität. Im Allgemeinen kann LLVM Array-basierten Code wie diesen sehr gut verarbeiten.