Haskell: Paralleler Code ist langsamer als sequentielle Version

Question

Ich bin ziemlich neu in Haskell Threads (und parallele Programmierung im Allgemeinen) und ich bin mir nicht sicher, warum meine parallele Version eines Algorithmus langsamer als die entsprechende sequentielle Version läuft.

Der Algorithmus versucht, alle K-Kombinationen ohne Rekursion zu finden. Dazu verwende ich this Helferfunktion, die eine Zahl mit k Bits gegeben, gibt die nächste Nummer mit der gleichen Anzahl von Bits gesetzt:

import Data.Bits  

nextKBitNumber :: Integer -> Integer 
nextKBitNumber n 
    | n == 0  = 0 
    | otherwise = ripple .|. ones 
         where smallest  = n .&. (-n) 
          ripple  = n + smallest 
          newSmallest = ripple .&. (-ripple) 
          ones   = (newSmallest `div` smallest) `shiftR` 1 - 1 

Es ist nun leicht sequentiell alle k-Kombinationen zu erhalten, in der Bereich [(2^k - 1), (2^(nk) + ... + 2^(n-1)):

import qualified Data.Stream as ST 

combs :: Int -> Int -> [Integer] 
combs n k = ST.takeWhile (<= end) $ kBitNumbers start 
    where start = 2^k - 1 
     end = sum $ fmap (2^) [n-k..n-1] 

kBitNumbers :: Integer -> ST.Stream Integer 
kBitNumbers = ST.iterate nextKBitNumber 

main :: IO() 
main = do 
    params <- getArgs 
    let n = read $ params !! 0 
     k = read $ params !! 1 
    print $ length (combs n k) 

Meine Idee ist, dass dieser Bereich dieses leicht sein sollte parallelisierbaren Splitting in kleinere Teile. Zum Beispiel:

start :: Int -> Integer 
start k = 2^k - 1 

end :: Int -> Int -> Integer 
end n k = sum $ fmap (2 ^) [n-k..n-1] 

splits :: Int -> Int -> Int -> [(Integer, Integer, Int)] 
splits n k numSplits = fixedRanges ranges [] 
    where s      = start k 
     e      = end n k 
     step     = (e-s) `div` (min (e-s) (toInteger numSplits)) 
     initSplits    = [s,s+step..e] 
     ranges     = zip initSplits (tail initSplits) 
     fixedRanges [] acc  = acc 
     fixedRanges [x] acc  = acC++ [(fst x, e, k)] 
     fixedRanges (x:xs) acc = fixedRanges xs (acC++ [(fst x, snd x, k)]) 

An dieser Stelle möchte Ich mag jede Spaltung parallel laufen zu lassen, so etwas wie:

runSplit :: (Integer, Integer, Int) -> [Integer] 
runSplit (start, end, k) = ST.takeWhile (<= end) $ kBitNumbers (fixStart start) 
    where fixStart s 
        | popCount s == k = s 
        | otherwise  = fixStart $ s + 1 

für pallalelization Ich bin mit dem monad-par Paket:

import Control.Monad.Par 
import System.Environment 
import qualified Data.Set as S 

main :: IO() 
main = do 
    params <- getArgs 
    let n    = read $ params !! 0 
     k    = read $ params !! 1 
     numTasks  = read $ params !! 2 
     batches   = runPar $ parMap runSplit (splits n k numTasks) 
     reducedNumbers = foldl S.union S.empty $ fmap S.fromList batches 
    print $ S.size reducedNumbers 

Das Ergebnis ist, dass die sequenzielle Version viel schneller ist und wenig Speicher benötigt, während die parallele Version viel Speicher verbraucht und sich langsamer bemerkbar macht.

Was könnten die Gründe dafür sein? Sind Threads ein guter Ansatz für dieses Problem? Zum Beispiel erzeugt jeder Thread eine (möglicherweise große) Liste von ganzen Zahlen und der Haupt-Thread reduziert die Ergebnisse; Sind Threads, von denen erwartet wird, dass sie viel Speicher benötigen oder einfach dazu gedacht sind, einfache Ergebnisse zu erzeugen (d. h. nur CPU-intensive Berechnungen)?

Ich kompiliere mein Programm mit stack build --ghc-options -threaded --ghc-options -rtsopts --executable-profiling --library-profiling und führe es mit ./.stack-work/install/x86_64-osx/lts-6.1/7.10.3/bin/combinatorics 20 3 4 +RTS -pa -N4 -RTS für n = 20, k = 3 und numSplits = 4. Ein Beispiel des Profiling-Reports für die parallele Version finden Sie unter here und für die sequentielle Version here.

Answer 1

In Ihrer sequentiellen Version Aufruf combs keine Liste im Speicher aufzubauen, da nach length verbraucht ein Element es nicht mehr benötigt wird und freigegeben wird. In der Tat kann GHC nicht einmal Speicher dafür reservieren.

Zum Beispiel wird dies eine Weile dauern, aber nicht viel Speicher verbrauchen:

main = print $ length [1..1000000000] -- 1 billion 

In Ihrer parallelen Version Unterlisten generieren, so dass sie zusammen verketten, Baukästen, usw. und Daher müssen die Ergebnisse jeder Unteraufgabe im Speicher gehalten werden.

Ein fairer Vergleich wäre, dass jede parallele Task die length der k-Bit-Zahlen in ihrem zugewiesenen Bereich berechnet und dann die Ergebnisse addiert. Auf diese Weise müssten die k-Bit-Zahlen, die von jeder parallelen Aufgabe gefunden wurden, nicht im Speicher gehalten werden und würden eher wie die sequentielle Version funktionieren.

aktualisieren

Hier ist ein Beispiel dafür, wie parMap zu verwenden. Hinweis: Unter 7.10.2 hatte ich gemischte Erfolge, indem ich die Parallelität in Brand setzte - manchmal und manchmal auch nicht. (es heraus - ich war mit -RTS -N2 statt +RTS -N2.)

{- 
compile with: ghc -O2 -threaded -rtsopts foo.hs 

compare: 

    time ./foo 26 +RTS -N1 
    time ./foo 26 +RTS -N2 
-} 

import Data.Bits  
import Control.Parallel.Strategies 
import System.Environment 

nextKBitNumber :: Integer -> Integer 
nextKBitNumber n 
    | n == 0  = 0 
    | otherwise = ripple .|. ones 
         where smallest  = n .&. (-n) 
          ripple  = n + smallest 
          newSmallest = ripple .&. (-ripple) 
          ones   = (newSmallest `div` smallest) `shiftR` 1 - 1 

combs :: Int -> Int -> [Integer] 
combs n k = takeWhile (<= end) $ iterate nextKBitNumber start 
    where start = 2^k - 1 
     end = shift start (n-k) 

main :: IO() 
main = do 
    (arg1 : _) <- getArgs 
    let n = read arg1 
    print $ parMap rseq (length . combs n) [1..n] 

Answer 2

gute Ansätze für dieses Problem

Was meinst du mit dieses Problem? Wenn es, wie Sie schreiben, analysieren und Melodie ein paralleles Haskell Programm, dann ist dies erforderlich, weiterführende Informationen:

Simon Marlow: Parallel und Concurrent Programming in Haskell http://community.haskell.org/~simonmar/pcph/

insbesondere § 15 (Debugging, Tuning, ..)

Verwenden Sie threadscope! (Eine grafische Viewer für Gewindeprofil Informationen vom Compiler Haskell Glasgow generierten) https://hackage.haskell.org/package/threadscope