Как использовать параллельные стратегии в Haskell

Question

У меня есть функция frequencyBy, которую я хотел бы распараллелить. Вот простой тестовый пример:

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

Я бы хотел запустить map в frequencyBy параллельно. Я пытаюсь добиться этого с помощью parList rdeepseq (все остальные вещи в main просто для того, чтобы не все было оптимизировано). Однако это не работает, два потока выполняют вдвое больше работы, чем один поток одновременно. Я не понимаю, что я делаю здесь не так.

Answer 1

Возможно, что накладные расходы замедляют процесс, в зависимости от того, насколько велик x ; если работа, которую вы выполняете в каждой искре, сопоставима со временем, которое требуется для создания каждой искры (и, конечно, есть планирование накладных расходов и т. д.), тогда у вас возникнут проблемы.

Вы можете попробовать parListChunk, например parListChunk 64 rdeepseq; вам придется поэкспериментировать, чтобы выяснить, какой размер куска использовать. В то время как ваша текущая стратегия создает искру для каждого элемента списка, parListChunk создает искру для каждого блока определенного размера в списке и использует указанную вами стратегию последовательно для каждого элемента этого блока.

Кстати, foldr в frequencyBy, вероятно, замедляет работу из-за чрезмерного создания грома; что-то вроде

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

должен это исправить.

Конечно, как всегда, убедитесь, что вы компилируете с -O2 и работаете с +RTS -N.

Answer 2

Я думаю, что ваш параллелизм слишком мелкозернистый.parList пытается оценить каждый элемент параллельно, и для любого отдельного элемента действительно не так много работы.

Когда я изменяю с parList на parListChunk 500, время выполнения увеличивается почти на 50%;поскольку я нахожусь на двухъядерной машине, это примерно так же хорошо, как и получается.

Для справки, я тестировал с x=20000.