Strategie parallele efficienti

Question

Sto provando a ragionare su strategie parallele. Penso di capire cosa fanno ciascuno dei combinatori, ma ogni volta che provo a usarli con più di un core, il programma rallenta considerevolmente.

Ad esempio, un po 'di tempo fa ho provato a calcolare gli istogrammi (e da loro parole univoche) da ~ 700 documenti. Ho pensato che usare la granularità a livello di file sarebbe ok. Con -N4 ottengo il saldo di lavoro di 1,70. Tuttavia con -N1 viene eseguito in metà tempo rispetto a -N4. Non sono sicuro di quale sia la domanda, ma mi piacerebbe sapere come decidere dove/quando/come parallelizzare e acquisire una certa comprensione al riguardo. Come sarebbe stato parallelo in modo che la velocità aumentasse con i nuclei invece di diminuire?

import Data.Map (Map) 
import qualified Data.Map as M 
import System.Directory 
import Control.Applicative 
import Data.Vector (Vector) 
import qualified Data.Vector as V 
import qualified Data.Text as T 
import qualified Data.Text.IO as TI 
import Data.Text (Text) 
import System.FilePath ((</>)) 
import Control.Parallel.Strategies 
import qualified Data.Set as S 
import Data.Set (Set) 
import GHC.Conc (pseq, numCapabilities) 
import Data.List (foldl') 

mapReduce stratm m stratr r xs = let 
    mapped = parMap stratm m xs 
    reduced = r mapped `using` stratr 
    in mapped `pseq` reduced 

type Histogram = Map Text Int 

rootDir = "/home/masse/Documents/text_conversion/" 

finnishStop = ["minä", "sinä", "hän", "kuitenkin", "jälkeen", "mukaanlukien", "koska", "mutta", "jos", "kuitenkin", "kun", "kunnes", "sanoo", "sanoi", "sanoa", "miksi", "vielä", "sinun"] 
englishStop = ["a","able","about","across","after","all","almost","also","am","among","an","and","any","are","as","at","be","because","been","but","by","can","cannot","could","dear","did","do","does","either","else","ever","every","for","from","get","got","had","has","have","he","her","hers","him","his","how","however","i","if","in","into","is","it","its","just","least","let","like","likely","may","me","might","most","must","my","neither","no","nor","not","of","off","often","on","only","or","other","our","own","rather","said","say","says","she","should","since","so","some","than","that","the","their","them","then","there","these","they","this","tis","to","too","twas","us","wants","was","we","were","what","when","where","which","while","who","whom","why","will","with","would","yet","you","your"] 
isStopWord :: Text -> Bool 
isStopWord x = x `elem` (finnishStop ++ englishStop) 

textFiles :: IO [FilePath] 
textFiles = map (rootDir </>) . filter (not . meta) <$> getDirectoryContents rootDir 
    where meta "." = True 
     meta ".." = True 
     meta _ = False 

histogram :: Text -> Histogram 
histogram = foldr (\k -> M.insertWith' (+) k 1) M.empty . filter (not . isStopWord) . T.words 

wordList = do 
    files <- mapM TI.readFile =<< textFiles 
    return $ mapReduce rseq histogram rseq reduce files 
    where 
    reduce = M.unions 

main = do 
    list <- wordList 
    print $ M.size list 

Per quanto riguarda i file di testo, che sto utilizzando file PDF convertiti in file di testo, quindi non posso fornire loro, ma per lo scopo, quasi ogni libro/libri di Progetto Gutenberg dovrebbero fare.

Edit: importazioni aggiunti a sceneggiatura

Answer 1

In pratica, ottenere i combinatori paralleli per scalare bene può essere difficile. Altri hanno menzionato la necessità di rendere il codice più rigido per garantire che si tratti effettivamente di che esegue il lavoro in parallelo, il che è sicuramente importante.

Due cose che possono realmente uccidere le prestazioni sono un sacco di attraversamento di memoria e garbage collection. Anche se non stai producendo un sacco di spazzatura, molti traversamenti di memoria dello mettono più pressione sulla cache della CPU e alla fine il tuo bus di memoria diventa il collo della bottiglia. La tua funzione isStopWord esegue molto di confronti di stringhe e deve attraversare una lista collegata piuttosto lunga per farlo. È possibile risparmiare un sacco di lavoro utilizzando il tipo integrato Set o, ancora meglio, il tipo HashSet dal pacchetto unordered-containers (poiché i confronti ripetuti con stringa possono essere costosi, soprattutto se condividono prefissi dei comuni).

import   Data.HashSet    (HashSet) 
import qualified Data.HashSet    as S 

... 

finnishStop :: [Text] 
finnishStop = ["minä", "sinä", "hän", "kuitenkin", "jälkeen", "mukaanlukien", "koska", "mutta", "jos", "kuitenkin", "kun", "kunnes", "sanoo", "sanoi", "sanoa", "miksi", "vielä", "sinun"] 
englishStop :: [Text] 
englishStop = ["a","able","about","across","after","all","almost","also","am","among","an","and","any","are","as","at","be","because","been","but","by","can","cannot","could","dear","did","do","does","either","else","ever","every","for","from","get","got","had","has","have","he","her","hers","him","his","how","however","i","if","in","into","is","it","its","just","least","let","like","likely","may","me","might","most","must","my","neither","no","nor","not","of","off","often","on","only","or","other","our","own","rather","said","say","says","she","should","since","so","some","than","that","the","their","them","then","there","these","they","this","tis","to","too","twas","us","wants","was","we","were","what","when","where","which","while","who","whom","why","will","with","would","yet","you","your"] 

stopWord :: HashSet Text 
stopWord = S.fromList (finnishStop ++ englishStop) 

isStopWord :: Text -> Bool 
isStopWord x = x `S.member` stopWord 

Sostituire la funzione isStopWord con questa versione rende molto di più e scale molto meglio (anche se sicuramente non 1-1). Potresti anche considerare utilizzando HashMap (dallo stesso pacchetto) anziché Map per gli stessi motivi, ma non ho ottenuto un cambiamento evidente da ciò.

Un'altra opzione consiste nell'aumentare le dimensioni di heap predefinite per prendere parte della pressione dello fuori dal GC e per dare più spazio per spostare le cose. Assegnando al codice compilato una dimensione heap predefinita di 1 GB (-H1G flag), ottengo un saldo GC di circa il 50% su 4 core, mentre ottengo solo il ~ 25% senza (esegue anche ~ 30% più veloce).

Con queste due modifiche, il tempo di esecuzione medio su quattro core (sulla mia macchina) scende da ~ 10,5 a ~ 3,5 s. Probabilmente, c'è un margine di miglioramento basato sulle statistiche GC (impiega ancora il 58% del tempo a fare lavori produttivi), ma fare decisamente meglio potrebbe richiedere una modifica molto più drastica allo dell'algoritmo.

Answer 2

Penso Daniel capito bene - l'Data.Map e liste sono un pigro strutture di dati; dovresti usare sia foldl 'e insertWith' per garantire che il lavoro per ogni blocco venga fatto con entusiasmo --- altrimenti tutto il lavoro è ritardato nella parte sequenziale (riduci).

Inoltre, non è ovvio che creare una scintilla per ogni file sia la giusta granularità, in particolare se le dimensioni dei file differiscono sostanzialmente. Se così fosse, sarebbe preferibile concatenare gli elenchi di parole e dividerli in blocchi di dimensioni uguali (vedi parListChunk combinator).

Mentre ci si trova, vorrei anche osservare alcune insidie ​​nell'utilizzo di IO pigro (readFile) per aprire molti file (il sistema di runtime potrebbe rimanere senza handle di file perché li trattiene troppo a lungo).