Эффективные параллельные стратегии

Question

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

Например, некоторое время назад я попытался вычислить гистограммы (и из них уникальные слова) из ~ 700 документов. Я думал, что использование гранулярности уровня файла будет в порядке. С -N4 Я получаю 1,70 баланса работы. Однако с -N1 он работает в полтора раза, чем с -N4. Я не уверен, что вопрос на самом деле, но я хотел бы знать, как решить, где/когда/как распараллелить и получить некоторое понимание на нем. Как это будет распараллеливаться, чтобы скорость увеличивалась с ядрами, а не уменьшалась?

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 

Что касается текстовых файлов, я использую PDFs преобразуются в текстовые файлы, так что я не могу представить их, но для этой цели, практически любую книгу/книги из проекта Гутенберг должны делать.

Редактировать: Добавлен импорт в скрипт

Answer 1

На практике получение параллельных комбинаторов для масштабирования может быть затруднено. Другие упомянули, делая ваш код более строгим, чтобы убедиться, что вы на самом деле , выполняете работу параллельно, что определенно важно.

Две вещи, которые могут действительно убить производительность, - это много обходной памяти и сборки мусора. Даже если вы не производите много мусора, много обходов памяти оказывают большее давление на кэш процессора, и в конечном итоге ваша шина памяти становится шеей бутылки. Ваша функция isStopWord выполняет множество сопоставлений строк и должна пересечь довольно длинный связанный список, чтобы сделать это. Вы можете сэкономить много работы, используя встроенный тип Set или, еще лучше, тип HashSet из пакета unordered-containers (так как повторная строка сравнение может быть дорогостоящим, особенно если они разделяют префиксы общего пользования).

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 

Замена вашей isStopWord функции этой версии работает намного лучше и масштабируется намного лучше (хотя определенно не 1-1). Вы также можете рассмотреть , используя HashMap (из того же пакета), а не Map по тем же причинам, , но я не получил заметного изменения от этого.

Другой вариант заключается в увеличении размера кучи по умолчанию, чтобы взять некоторое давление от GC и дать ему больше места для перемещения. Предоставляя скомпилированный код размером кучи по умолчанию 1GB (-H1G), я получаю баланс GC около 50% на 4 ядрах, тогда как я получаю только ~ 25% (он также работает ~ 30% быстрее).

С этими двумя изменениями средняя продолжительность работы на четырех ядрах (на моей машине) падает с ~ 10,5 до ~ 3,5 с. Можно утверждать, что есть место для улучшения, основанного на статистике GC (по-прежнему только тратит 58% времени на производственную работу), , но при значительно улучшении может потребоваться гораздо более резкое изменение вашего алгоритма до .

Answer 2

Я думаю, что Даниэль получил это право - Data.Map и списки ленивых структур данных; вы должны использовать как foldl ', так и insertWith', чтобы гарантировать, что работа для каждого фрагмента выполнена с нетерпением --- в противном случае вся работа задерживается на последовательную часть (уменьшает).

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

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