効率的な並列戦略

Question

私はパラレル戦略の周りに頭を抱えようとしています。私はコンビネータのそれぞれが何をしているのか理解していると思いますが、1つ以上のコアでそれらを使用しようとするたびに、プログラムはかなり遅くなります。

たとえば、私はヒストグラムを計算しようとしました。私は、ファイルレベルの細分性を使用すると大丈夫だろうと思った。 -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 

テキストファイルに関しては、私が使用しているPDFが、私はそれらを提供することができないので、ファイルをテキストに変換が、目的のために、ほぼすべての書籍/プロジェクトグーテンベルクから書籍が行う必要があります。

編集：スクリプト

Answer 1

実際には、並列コンバイナをうまくスケールすることは困難です。 他の人は、実際には の作業を並行して行うことを確実にするためにコードを厳密にすることについて言及していますが、これは間違いなく重要です。

実際にパフォーマンスを低下させる可能性があるのは、メモリトラバーサルと、 ガベージコレクションです。たとえあなたがたくさんのゴミを生産していなくても、多くの メモリトラバーサルがCPUキャッシュに多くの負担をかけることになり、最終的にメモリバスがボトルネックになります（ ）。 isStopWord関数は、文字列比較の多くを実行し、そのために長いリンクリストをトラバースする必要があります。 組み込みのSetタイプを使用すると、 HashSetタイプのパッケージを使用することで、多くの作業を省くことができます（繰り返し文字列 は、特にコモン接頭辞を共有する場合に比較が高価になる可能性があるため）。このバージョンでは、あなたのisStopWord機能を交換

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 

は より良いを実行し、（1-1間違いではないが）はるかに良いをスケーリングします。同様の理由で、 と同じ理由でMapではなく、HashMap（同じパッケージのもの）を使用することも考えられますが、私はそうしても目立った変更はありませんでした。

もう1つの方法は、デフォルトのヒープサイズを大きくして、GCの負荷を軽減し、より多くのスペースを移動させることです。 コンパイル済みコードに1GB（-H1Gフラグ）のデフォルトヒープサイズを指定すると、4コアで約125％のGCバランスが得られますが、私はわずか25％しか得られません（それは〜30％ より速く実行されます）。

この2つの変更では、私のマシン上の4つのコアの平均実行時間は、〜10.5秒から〜3.5秒に低下します（ ）。間違いなく、 に基づいて改善の余地があります（まだ生産的な作業をしている時間の58％を費やしています）、 しかし、大幅に改善するとアルゴリズムが大幅に変更される可能性があります。

Answer 2

私はダニエルは右のそれを得たと思うに追加しました輸入 - Data.Mapとリストが怠惰なデータ構造です。各チャンクの作業が確実に行われるようにfoldl 'と insertWith'の両方を使用する必要があります。そうしないと、すべての作業が順次部分（遅延）に遅れます。

また、各ファイルのスパークを作成することは、特にファイルサイズが大幅に異なる場合は、正確な粒度であることは明らかではありません。これが当てはまる場合は、単語リストを連結し、偶数サイズのチャンクで分割することが望ましいでしょう（parListChunkコンビネータ参照）。

また、遅延IO（readFile）を使用して多数のファイルを開くという落とし穴を見ていきます（ランタイムシステムはファイルハンドルが長すぎるためファイルハンドルが不足する可能性があります）。