15

私は並行戦略に頭を悩ませようとしています。それぞれのコンビネータが何をするかは理解できたと思いますが、それらを複数のコアで使用しようとするたびに、プログラムの速度が大幅に低下します。

たとえば、しばらく前に、〜 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

テキストファイルに関しては、私はテキストファイルに変換されたpdfを使用しているので提供できませんが、目的のためには、プロジェクトgutenbergのほとんどすべての本/本が必要です.

編集：スクリプトにインポートを追加

4

2 に答える 2

4

実際には、並列コンビネータを適切にスケーリングするのは難しい場合があります。他の人は、コードをより厳密にして、実際に並行して作業を行っていることを確認することに言及していますが、これは間違いなく重要です。

パフォーマンスを著しく低下させる 2 つの要因は、大量のメモリ トラバーサルとガベージ コレクションです。大量のガベージを生成していない場合でも、大量のメモリ トラバーサルが CPU キャッシュにさらに負荷をかけ、最終的にメモリ バスがボトルネックになります。あなたの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

もう 1 つのオプションは、デフォルトのヒープ サイズを増やして GC の負担を軽減し、物事を移動する余地を増やすことです。コンパイルされたコードに 1GB のデフォルトのヒープ サイズ ( -H1Gflag) を指定すると、4 コアで約 50% の GC バランスが得られますが、コアなしでは最大 25% しか得られません (実行速度も最大 30% 速くなります)。

これら 2 つの変更により、(私のマシンの) 4 つのコアでの平均実行時間は ~10.5 秒から ~3.5 秒に低下します。間違いなく、GC 統計に基づいて改善の余地があります (まだ 58% の時間しか生産的な作業に費やされていません)。

于 2013-01-31T16:34:10.453 に答える
4

ダニエルは正しかったと思います。Data.Map とリストは遅延データ構造です。foldl'とinsertWith'の両方を使用して、各チャンクの作業が熱心に行われるようにする必要があります --- そうしないと、すべての作業が順次部分に遅れます (削減)。

また、特にファイル サイズが大幅に異なる場合、各ファイルに対してスパークを作成することが適切な粒度であることは明らかではありません。その場合は、単語リストを連結し、均等なサイズのチャンクに分割することをお勧めします (parListChunk コンビネータを参照)。

同時に、遅延 IO (readFile) を使用して多くのファイルを開く際の落とし穴についても説明します (ランタイム システムはファイル ハンドルを長時間保持するため、ファイル ハンドルを使い果たす可能性があります)。

于 2013-01-31T14:02:31.630 に答える