Замедление при использовании параллельных стратегий в Haskell

Я работал над упражнениями детерминированного параллельного программирования Андре Лона в упражнениях хэскелла. Я пытался преобразовать последовательный код N-Queens в параллель с помощью стратегий, но я заметил, что параллельный код работает намного медленнее, чем последовательный код, а также ошибки с недостаточным пространством стека.

Это код для параллельных N-Queens,

import Control.Monad
import System.Environment
import GHC.Conc
import Control.Parallel.Strategies
import Data.List
import Data.Function

type PartialSolution = [Int] -- per column, list the row the queen is in
type Solution = PartialSolution

type BoardSize = Int

chunk :: Int -> [a] -> [[a]]
chunk n [] = []
chunk n xs = case splitAt n xs of
         (ys, zs) -> ys : chunk n zs

-- Generate all solutions for a given board size.
queens :: BoardSize -> [Solution]
--queens n = iterate (concatMap (addQueen n)) [[]] !! n
queens n = iterate (\l -> concat (map (addQueen n) l `using` parListChunk (n `div`            numCapabilities) rdeepseq)) [[]] !! n


-- Given the size of the problem and a partial solution for the
-- first few columns, find all possible assignments for the next
-- column and extend the partial solution.
addQueen :: BoardSize -> PartialSolution -> [PartialSolution]
addQueen n s = [ x : s | x <- [1..n], safe x s 1 ]

-- Given a row number, a partial solution and an offset, check
-- that a queen placed at that row threatens no queen in the
-- partial solution.
safe :: Int -> PartialSolution -> Int -> Bool
safe x []    n = True
safe x (c:y) n = x /= c && x /= c + n && x /= c - n && safe x y (n + 1)

main = do
        [n] <- getArgs
        print $ length $ queens (read n)

Линия (\l -> concat (map (addQueen n) l using parListChunk (n div numCapabilities) rdeepseq)) - это то, что я изменил с исходного кода. Я видел решение Simon Marlow, но я хотел узнать причину замедления и ошибки в моем коде.

Спасибо заранее.

Ответы

Ответ 1

Вы слишком много работаете. Параметр parListChunk div n numCapabilities, вероятно, что, 7 в вашей системе (2 ядра и вы работаете с n ~ 14). Список будет расти очень быстро, поэтому нет смысла вырабатывать такие небольшие единицы работы (и я не понимаю, почему это имеет смысл привязывать его к значению n).

Если я добавлю коэффициент в десять (создавая в этом случае блок искрообразования 70), я получаю четкий выигрыш в производительности по сравнению с одиночной резьбой. Кроме того, у меня нет проблемы со стеком, на которую вы ссылаетесь, - если это исчезнет с изменением вашего значения parListChunk, тогда я сообщу об этом как об ошибке.

Если я сделаю chunking каждые 800, тогда время заканчивается на 5.375s против 7.9s. Более 800, и производительность снова начинает ухудшаться, ymmv.

EDIT:

[[email protected] Test]$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 7.0.4
[[email protected] Test]$ ghc -O2 so.hs -rtsopts -threaded -fforce-recomp ; time ./so 13 +RTS -N2
[1 of 1] Compiling Main             ( so.hs, so.o )
Linking so ...
73712
real    0m5.404s

[[email protected] Test]$ ghc -O2 so.hs -rtsopts -fforce-recomp ; time ./so 13
[1 of 1] Compiling Main             ( so.hs, so.o )
Linking so ...
73712
real    0m8.134s