Parallel Haskell - GHC GC'ing sparks

Question

У меня есть программа, которую я пытаюсь распараллелить (полная паста с исполняемым кодом here).

Я профилировал и обнаружил, что большая часть времени проведена в findNearest, который по существу простой foldr над большим Data.Map.

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 предполагается выполнить findNearest параллельно над поддеревьев большего Map.

parFindNearest :: NFData k => RGB -> M.Map k RGB -> (k, Word32) 
parFindNearest rgb = minimumBy (comparing snd) 
        . parMap rdeepseq (findNearest rgb) 
        . M.splitRoot 

К сожалению, большинство моих искр GHC GC, прежде чем они превратятся в полезный параллелизм.

Вот результат компиляции с ghc -O2 -threaded и работает с +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 

Как вы можете видеть, большинство искр GC'd или выдохнуться перед преобразованием. Я пробовал экспериментировать с различной строгостью, имея findNearest, возвращающий пользовательский строгий тип данных пары вместо кортежа или используя rdeepseq от Control.Parallel.Strategies, но мои искры по-прежнему GC'd.

Я хотел бы знать,

• почему мои искры быть GC'd перед преобразованием?
• Как я могу изменить свою программу, чтобы воспользоваться параллелизмом?

Answer 1

Я не эксперт в параллельных стратегиях, поэтому я могу быть совершенно неправ. Но:

Если вы отключите GC, установив достаточно большую область выделения (например, используя параметр времени исполнения -A20M), вы увидите, что большинство искр испепелены, а не GC'd. Это означает, что они оцениваются обычным потоком программы до завершения соответствующей искры.

minimumBy силы parMap результаты немедленно, начиная с их оценки. В то же время искры планируются и выполняются, но уже слишком поздно. Когда искра закончена, значение уже оценивается основным потоком. Без -A20M искры GC'd, потому что значение оценивается и GC'd еще до того, как искра запланирована.

Вот упрощенный тест:

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 

В этом случае все искры заторможен:

(Несколько раз они GC'd)

Но если я перед началом печати,

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 

Тогда все искры конвертируются:

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

Так, похоже, у вас есть не хватает искры (попытаться установить l = [n..n+1000] в моем примере), и они не являются достаточно тяжелыми (попробуйте установить n = 1000 в моем примере) ,