Parallel Haskell - GHC GC'ing Funken

Question

Ich habe ein Programm, das ich parallelisieren möchte (vollständige einfügen mit ausführbaren Code here).

Ich habe profiliert und festgestellt, dass die meiste Zeit in findNearest verbracht wird, die im Wesentlichen eine einfache foldr über eine große Data.Map ist.

findNearest :: RGB -> M.Map k RGB -> (k, Word32) 
findNearest rgb m0 = 
    M.foldrWithKey' minDistance (k0, distance rgb r0) m0 
    where (k0, r0) = M.findMin m0 
      minDistance k r x@(_, d1) = 
      -- Euclidean distance in RGB-space 
      let d0 = distance rgb r 
      in if d0 < d1 then (k, d0) else x 

parFindNearest soll MapfindNearest parallel über Teilbäume des größeren auszuführen.

Leider GHC GC meine meisten Funken, bevor sie in nützliche Parallelität umgewandelt werden.

Hier ist das Ergebnis mit ghc -O2 -threaded von Kompilieren und Ausführen mit +RTS -s -N2

839,892,616 bytes allocated in the heap 
123,999,464 bytes copied during GC 
    5,320,184 bytes maximum residency (19 sample(s)) 
    3,214,200 bytes maximum slop 
      16 MB total memory in use (0 MB lost due to fragmentation) 

            Tot time (elapsed) Avg pause Max pause 
    Gen 0  1550 colls, 1550 par 0.23s 0.11s  0.0001s 0.0004s 
    Gen 1  19 colls, 18 par 0.11s 0.06s  0.0030s 0.0052s 

    Parallel GC work balance: 16.48% (serial 0%, perfect 100%) 

    TASKS: 6 (1 bound, 5 peak workers (5 total), using -N2) 

    SPARKS: 215623 (1318 converted, 0 overflowed, 0 dud, 198111 GC'd, 16194 fizzled) 

    INIT time 0.00s ( 0.00s elapsed) 
    MUT  time 3.72s ( 3.66s elapsed) 
    GC  time 0.34s ( 0.17s elapsed) 
    EXIT time 0.00s ( 0.00s elapsed) 
    Total time 4.07s ( 3.84s elapsed) 

    Alloc rate 225,726,318 bytes per MUT second 

    Productivity 91.6% of total user, 97.1% of total elapsed 

gc_alloc_block_sync: 9862 
whitehole_spin: 0 
gen[0].sync: 0 
gen[1].sync: 2103 

Wie Sie sehen können, ist die Mehrheit der Funken GC'd oder im Sande verlaufen, bevor umgewandelt wird. Ich habe versucht, mit unterschiedlicher Strenge zu experimentieren, findNearest einen kundenspezifischen strikten Paardatentyp anstelle eines Tupels zurückzugeben, oder rdeepseq von Control.Parallel.Strategies verwendend, aber meine Funken werden noch GC'd.

würde Ich mag

wissen

• warum werden meine Funken GC'd vor umgewandelt werden?
• Wie kann ich mein Programm ändern, um die Parallelität zu nutzen?

Answer 1

Ich bin nicht auf Experte in parallelen Strategien, also kann ich völlig falsch liegen. Aber:

Wenn Sie GC deaktivieren, indem Sie groß genug Zuteilung Bereich einstellen (z. B. mit -A20M Laufzeitoption), werden Sie sehen, dass die meisten Funken sind verpufft, nicht GC'd. Dies bedeutet, dass sie vor Ablauf des entsprechenden Funkens mit dem normalen Programmfluss ausgewertet werden.

minimumBy Kräfte parMap Ergebnisse sofort, beginnend mit der Auswertung von ihnen. Zur gleichen Zeit werden Funken geplant und ausgeführt, aber es ist zu spät. Wenn Spark abgeschlossen ist, wird der Wert bereits vom Hauptthread ausgewertet. Ohne -A20M werden die Funken GC'd, weil der Wert ausgewertet und GC'd noch vor dem Funken geplant wird.Hier

ist ein vereinfachtes Testfall:

import Control.Parallel.Strategies 

f :: Integer -> Integer 
f 0 = 1 
f n = n * f (n - 1) 

main :: IO() 
main = do 
    let l = [n..n+10] 
     n = 1 
     res = parMap rdeepseq f l 
    print res 

In diesem Fall werden alle Funken im Sande verlaufen sind:

(Einige Male sind sie GC'd)

Aber wenn ich Hauptfaden vor dem Druckergebnis liefern,

import Control.Parallel.Strategies 
import Control.Concurrent 

f :: Integer -> Integer 
f 0 = 1 
f n = n * f (n - 1) 

main :: IO() 
main = do 
    let l = [n..n+10] 
     n = 1 
     res = parMap rdeepseq f l 
    res `seq` threadDelay 1 
    print res 

Dann werden alle Funken umgewandelt werden:

SPARKS: 11 (11 converted, 0 overflowed, 0 dud, 0 GC'd, 0 fizzled) 

So, sieht aus wie Sie nicht genug Funken haben (versuchen l = [n..n+1000] in meinem Beispiel zu geben), und sie sind nicht schwer genug (versuchen n = 1000 in meinem Beispiel zu setzen) .