Jak korzystać z równoległych strategii w Haskell

Question

Mam funkcję frequencyBy, którą chciałbym zrównoleglić. Tu następuje prosty przypadek testowy:

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 

chciałbym uruchomić map w frequencyBy równolegle. Próbuję to osiągnąć, używając parList rdeepseq (wszystkie inne rzeczy w main mają na celu upewnienie się, że nie wszystko jest zoptymalizowane). Jednak to nie działa, dwa wątki wykonują dwukrotnie więcej pracy niż jeden wątek w tym samym czasie. Nie rozumiem, co robię źle tutaj.

Answer 1

Może się zdarzyć, że narzut spowalnia działanie systemu, w zależności od tego, jaka jest duża wartość: x; jeśli praca, którą wykonujesz w każdej iskierce, jest porównywalna do czasu potrzebnego na odrodzenie każdej iskry (i oczywiście nie ma narzutu związanego z harmonogramem itp.), wtedy napotkasz problemy.

Możesz spróbować parListChunk, np. parListChunk 64 rdeepseq; będziesz musiał poeksperymentować, aby dowiedzieć się, którego rozmiaru porcji użyć. Podczas gdy twoja obecna strategia tworzy iskrę dla każdego elementu listy, parListChunk tworzy iskrę dla każdej porcji o określonym rozmiarze na liście i używa strategii określonej kolejno dla każdego elementu tej porcji.

Nawiasem mówiąc, foldr w frequencyBy prawdopodobnie spowalnia rzeczy ze względu na nadmierne tworzenie thunk; coś takiego jak

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

powinien to naprawić.

Oczywiście, jak zawsze, upewnij się, że kompilujesz z -O2 i działasz z +RTS -N.

Answer 2

Myślę, że twój paralelizm jest zbyt drobnoziarnisty. parList próbuje ocenić każdy element równolegle, a naprawdę nie ma tak wiele pracy dla jednego elementu.

Po zmianie z parList na parListChunk 500 czas realizacji wzrasta o prawie 50%; ponieważ jestem na dwurdzeniowym komputerze, który jest tak dobry, jak to tylko możliwe.

Dla porównania testowałem pod numerem x=20000.