Efektywne strategie równoległe

Question

Próbuję obrócić głowę wokół równoległych strategii. Myślę, że rozumiem, co robi każdy z kombinatorów, ale za każdym razem, gdy próbuję używać ich z więcej niż jednym rdzeniem, program znacznie spowalnia.

Na przykład jakiś czas temu próbowałem obliczyć histogramy (i od nich unikalne słowa) z ~ 700 dokumentów. Pomyślałem, że używanie ziarnistości na poziomie pliku byłoby w porządku. Z -N4 otrzymuję saldo 1,70. Jednak z -N1 działa on o połowę krócej niż w przypadku -N4. Nie jestem pewien, co to jest naprawdę, ale chciałbym wiedzieć, jak zdecydować, gdzie/kiedy/jak zrównoleglić i uzyskać pewne zrozumienie na ten temat. Jak by to było zrównoleglone, aby prędkość rosła z rdzeniami, zamiast zmniejszać?

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 

chodzi o pliki tekstowe, używam pdfs konwertowane do plików tekstowych, więc nie mogę zapewnić im, ale do tego celu, niemal każda książka/książki z Gutenberg projektu powinien robić.

Edit: Dodano import do skryptu

Answer 1

W praktyce uzyskanie równoległych kombajnów do odpowiedniej skali może być trudne. Inni wspomnieli, że twój kod jest bardziej rygorystyczny, aby upewnić się, że faktycznie wykonujesz pracę równolegle, co jest zdecydowanie ważne.

Dwie rzeczy, które naprawdę mogą zabić wydajność, to duża ilość konwersji pamięci i śmieci. Nawet jeśli nie produkuje się dużo śmieci, wiele przejazdów pamięciowych powoduje większy nacisk na pamięć podręczną procesora, a ostatecznie autobus pamięciowy staje się szyjką butelki. Twoja funkcja isStopWord wykonuje wiele porównań ciągów i musi przechodzić przez raczej długą, połączoną listę, aby to zrobić. Możesz zaoszczędzić dużo pracy, używając wbudowanego typu Set lub, jeszcze lepiej, typu HashSet z pakietu unordered-containers (ponieważ wielokrotne porównywanie ciągów znaków może być kosztowne, szczególnie jeśli mają one wspólne przedrostki commons).

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 

Wymiana swoją funkcję isStopWord z tą wersją sprawuje się dużo lepiej i skaluje się znacznie lepiej (choć na pewno nie 1-1). Możesz także rozważyć użycie przy użyciu HashMap (z tego samego pakietu) zamiast Map z tych samych powodów, , ale nie otrzymałem zauważalnej zmiany.

Inną opcją jest zwiększenie domyślnego rozmiaru sterty w celu usunięcia niektórych wartości ciśnienia z GC i nadania mu więcej miejsca do przemieszczania obiektów. Podając skompilowany kod domyślny rozmiar sterty 1GB (-H1G flag), otrzymuję bilans GC wynoszący około 50% na 4 rdzeniach, podczas gdy ja dostaję tylko ~ 25% bez (działa również szybciej ~ 30% ).

Przy tych dwóch zmianach średni czas pracy na czterech rdzeniach (na moim komputerze) wynosi spada z ~ 10,5 s do ~ 3,5 s. Możliwe, że jest miejsce na ulepszenie w oparciu o statystyki GC (nadal spędza tylko 58% czasu na produktywnej pracy), , ale robienie znacznie lepszych może wymagać o wiele bardziej drastycznych zmian w stosunku do twojego algorytmu o .

Answer 2

myślę Daniel miał rację - w Data.Map i listy są leniwe struktury danych; powinieneś użyć obu foldl 'i insertWith', aby zapewnić pracę dla każdej porcji jest wykonywana z niecierpliwością - w przeciwnym razie cała praca jest opóźniona do części sekwencyjnej (zmniejszenie).

Nie jest również oczywiste, że tworzenie iskry dla każdego pliku jest odpowiednią ziarnistością, szczególnie jeśli rozmiary plików znacznie się różnią. Jeśli tak jest, lepiej byłoby połączyć listy słów i podzielić je na partie o równej wielkości (zobacz parolistChunk combinator).

Będąc przy tym, chciałbym również przyjrzeć się pułapkom używania leniwego IO (readFile) do otwierania wielu plików (w systemie runtime może brakować uchwytów plików, ponieważ zatrzymuje się na nich zbyt długo).