Cómo utilizar las estrategias paralelas en Haskell

Question

Tengo una función frequencyBy que me gustaría paralelizar. Aquí sigue un caso de prueba sencilla:

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 

me gustaría correr el map en frequencyBy en paralelo. Estoy tratando de lograr esto usando parList rdeepseq (todas las demás cosas en main es solo para asegurar que no todo está optimizado). Sin embargo, esto no funciona, dos subprocesos hacen el doble de trabajo que un subproceso al mismo tiempo. No entiendo lo que estoy haciendo mal aquí.

Answer 1

Es posible que la sobrecarga disminuya la velocidad, dependiendo de cuán grande sea x; Si el trabajo que estás haciendo en cada chispa es comparable al tiempo que lleva engendrar cada chispa (y, por supuesto, hay una sobrecarga de programación, etc.), entonces tendrás problemas.

Puedes probar parListChunk, p. Ej. parListChunk 64 rdeepseq; Tendrás que experimentar para descubrir qué tamaño de fragmento usar. Mientras que su estrategia actual crea una chispa para cada elemento de la lista, parListChunk crea una chispa para cada fragmento de un cierto tamaño en la lista, y utiliza la estrategia que especifica secuencialmente sobre cada elemento de ese trozo.

Por cierto, el foldr en frequencyBy probablemente está ralentizando las cosas debido a la creación excesiva de procesador; algo así como

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

debería arreglar eso. Por supuesto, como siempre, asegúrese de compilar con -O2 y ejecutar con +RTS -N.

Answer 2

Creo que su paralelismo es demasiado fino. parList intenta evaluar cada elemento en paralelo, y realmente no hay mucho trabajo para un elemento.

Cuando cambio de parList a parListChunk 500 el tiempo de ejecución aumenta en casi un 50%; como estoy en una máquina de doble núcleo que es casi tan buena como se pone.

Como referencia, estaba probando con x=20000.