Come usare Parallel Strategies in Haskell

Question

Ho una funzione frequencyBy che vorrei parallelizzare. Qui di seguito un semplice caso di test:

import Control.Parallel.Strategies 
import Control.DeepSeq 
import System.Environment 

frequencyBy :: (a -> b -> Bool) -> [a] -> [b] -> [(a,Int)] 
frequencyBy f as bs = map 
    (\a ->(a, foldr (\b -> if f a b then (+) 1 else id) 0 bs)) as 

main :: IO() 
main = do 
    x:xs <- getArgs 
    let result = frequencyBy (==) [1::Int .. 10000] [1 .. (read x)] `using` 
       parList rdeepseq 
    print $ product $ map snd $ result 

vorrei correre il map in frequencyBy in parallelo. Sto cercando di raggiungere questo obiettivo utilizzando parList rdeepseq (tutte le altre cose nello main servono solo a garantire che non tutto sia ottimizzato). Tuttavia, questo non funziona, due thread fanno il doppio del lavoro di un thread nello stesso tempo. Non capisco cosa sto facendo male qui.

Answer 1

Potrebbe essere che il sovraccarico rallenti, a seconda di quanto è grande x; se il lavoro che fai in ogni scintilla è paragonabile al tempo necessario per generare ogni scintilla (e ovviamente c'è un sovraccarico di pianificazione, ecc.), allora ti imbatterai in problemi.

Si potrebbe provare parListChunk, ad es. parListChunk 64 rdeepseq; dovrai sperimentare per capire quale dimensione del blocco usare. Mentre la tua strategia attuale sta creando una scintilla per ogni elemento della lista, parListChunk crea una scintilla per ogni pezzo di una certa dimensione nella lista, e usa la strategia specificata in modo sequenziale su ogni elemento di quella porzione.

A proposito, il foldr in frequencyBy sta probabilmente rallentando le cose a causa della creazione eccessiva del thunk; qualcosa come

frequencyBy :: (a -> b -> Bool) -> [a] -> [b] -> [(a,Int)] 
frequencyBy f as bs = map (\a -> (a, sum . map (const 1) . filter (f a) $ bs)) as 

dovrebbe risolvere quello.

Naturalmente, come sempre, assicurati di compilare con -O2 ed esegui con +RTS -N.

Answer 2

Penso che il tuo parallelismo sia troppo fine. parList tenta di valutare ogni elemento in parallelo, e non c'è davvero molto lavoro per ogni elemento.

Quando cambio da parList a parListChunk 500 il tempo di esecuzione aumenta di quasi il 50%; dato che sono su una macchina dual-core, è più che buona.

Per riferimento, stavo testando con x=20000.