マルチコアテキストファイルの解析

StackOverflow https://stackoverflow.com/questions/7015

  •  08-06-2019
  •  | 
  •  

質問

クアッド コア マシンを持っており、4 つのコアすべてを利用してテキスト ファイルを解析するコードを作成したいと考えています。テキスト ファイルには基本的に 1 行に 1 つのレコードが含まれます。

マルチスレッドは私の得意分野ではないので、最適な方法でファイルを解析するために使用できる可能性のあるパターンを誰かが教えてくれないかと考えています。

私の最初の考えは、すべての行をある種のキューに読み取り、スレッドをスピンアップしてキューから行を取り出して処理することですが、それはキューがメモリ内に存在する必要があり、これらのファイルはかなり大きいため、私はその考えにはあまり乗り気ではありません。

次の考えは、行を読み取って解析するスレッドを割り当てる何らかのコントローラーを用意することですが、スレッドが処理速度よりも速く行を処理している場合にコントローラーが最終的にボトルネックになるかどうかはわかりません。それらを読んで割り当てます。

おそらくこれらの両方よりも別の簡単な解決策があることはわかっていますが、現時点ではそれがわかりません。

役に立ちましたか？

解決

私はあなたの当初のアイデアでいいと思います。キューが大きくなりすぎるのではないかと心配な場合は、キュー用のバッファゾーンを実装してください（つまり、100 行を超えるとファイルの読み取りが停止され、20 行を下回ると再び読み取りが開始されます。最適なバリアを見つけるには、いくつかのテストを行う必要があります)。アイテムを取り出すにはキューをロックする必要があるため、いずれのスレッドも潜在的に「リーダー スレッド」になれるようにします。また、「低バッファ領域」にヒットしたかどうかを確認して読み取りを再開できるようにします。これを実行している間、他のスレッドはキューの残りを読み取ることができます。

または、必要に応じて、1 つのリーダー スレッドに行を他の 3 つのリーダー スレッドに割り当てます。 プロセッサー スレッドを (独自のキューを介して) 実装し、 仕事を盗む戦略. 。私はこれをやったことがないので、それがどれほど難しいかわかりません。

他のヒント

マークの答えは、よりシンプルで洗練された解決策です。必要がないのに、なぜスレッド間通信を伴う複雑なプログラムを構築する必要があるのでしょうか?4 つのスレッドを生成します。各スレッドはファイルのサイズ/4 を計算して、開始点 (および終了点) を決定します。その後、各スレッドは完全に独立して動作できるようになります。

の のみ 読み取りを処理する特別なスレッドを追加する理由は、一部の行の処理に非常に長い時間がかかることが予想される場合です。 そして これらの行はファイルの 1 つの部分に集中していることが予想されます。スレッド間通信が必要ない場合に追加するのは、 とても悪い考え. 。予期しないボトルネックや同期バグが発生する可能性が大幅に高まります。

これにより、単一スレッドで読み取りを実行することのボトルネックが解消されます。

open file
for each thread n=0,1,2,3:
    seek to file offset 1/n*filesize
    scan to next complete line
    process all lines in your part of the file

私の経験は C# ではなく Java です。そのため、これらの解決策が当てはまらない場合は申し訳ありません。

私がすぐに思いつく解決策は、3 つのスレッドを実行するエグゼキューターを用意することです ( Executors.newFixedThreadPool, 、 言う）。入力ファイルから読み取られた各行/レコードに対して、実行プログラムでジョブを起動します (次を使用します)。 ExecutorService.submit）。エグゼキューターはリクエストをキューに入れ、3 つのスレッド間で割り当てます。

おそらく、より良い解決策が存在しますが、うまくいけば、それでうまくいきます。:-)

到着予定時刻:Wolfbyte の 2 番目のソリューションによく似ています。:-)

ETA2: System.Threading.ThreadPool .NET におけるアイデアと非常によく似ているように思えます。使ったことはありませんが、使ってみる価値はあるかもしれません！

ファイルを扱うときのボトルネックは通常、読み取りではなく処理にあるため、私は次のようにします。 生産者と消費者 パターン。ロックを回避するには、ロックフリーリストを調べます。C# を使用しているので、Julian Bucknall の記事を見てください。 ロックフリーリスト コード。

@lomaxx

@デレクとマーク:2つの回答を受け入れる方法があればいいのにと思います。ファイルをn個のセクションに分割すると、スレッドが「遅い」トランザクションのバッチに遭遇する可能性があるため、最終的にはWolfbyteのソリューションを使用する必要がありますが、各プロセスが異なるファイルを処理している場合は、同じ量の処理が必要であることが保証されている場合、ファイルをいくつかのチャンクに分割し、各チャンクをスレッドに割り当てて完了するというソリューションが本当に気に入りました。

心配ない。クラスター化された「遅い」トランザクションが問題になる場合は、キューイング ソリューションが最適です。平均トランザクションの速度に応じて、各ワーカーに一度に複数の行を割り当てることも検討することをお勧めします。これにより、同期のオーバーヘッドが削減されます。同様に、バッファ サイズの最適化が必要になる場合があります。もちろん、これらはどちらもプロファイリング後にのみ実行すべき最適化です。(同期がボトルネックでない場合は、同期について心配する必要はありません。)

解析するテキストが繰り返しの文字列とトークンで構成されている場合は、ファイルを複数のチャンクに分割し、チャンクごとに 1 つのスレッドでキーワード、「句読点」、ID 文字列、および値で構成されるトークンに事前解析することができます。文字列の比較と検索は非常にコストがかかる場合があり、これを複数のワーカー スレッドに渡すことで、文字列の検索と比較を行う必要がない場合、コードの純粋に論理的/セマンティックな部分を高速化できます。

事前に解析されたデータ チャンク (すべての文字列比較をすでに実行し、「トークン化」したもの) を、トークン化されたデータのセマンティクスと順序を実際に調べるコードの部分に渡すことができます。

また、ファイルのサイズが大量のメモリを占有することを懸念しているとも述べています。メモリ予算を削減するためにできることがいくつかあります。

ファイルをいくつかのチャンクに分割し、解析します。チャンクの処理が終了して次のチャンクに進む前にディスク上で停止しないように、一度に作業しているチャンク数と「先読み」用のチャンク数だけを読み込みます。

あるいは、大きなファイルをメモリにマップして「デマンド」でロードすることもできます。CPU よりも多くのスレッドがファイルの処理に取り組んでいる場合 (通常、スレッド = 1.5 ～ 2 倍の CPU がデマンド ページング アプリにとって適切な数です)、メモリ マップされたファイルの IO で停止しているスレッドは、メモリ マップされたファイルの IO が完了するまで OS から自動的に停止されます。メモリの準備が完了し、他のスレッドは処理を続行します。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top