10

元の質問

STMは初めてです。Haskellでやりたいことの1つは、大きなデータと、その大きなデータの小さな部分の読み取りと書き込みを行う多数の軽量スレッドです。読み取りおよび書き込みの場所は、本質的にランダムで小さいと見なすことができます。STMはこれには最適のようですが、問題をどのように攻撃するかについていくつか質問があります。私はいくつかの可能なアプローチを見て、それぞれにいくつかの欠点があり、いくつかは明らかに愚かなようです。これらに関するいくつかのコメント、または代替案に関する他のアイデアをいただければ幸いです。

簡単にするために、大きなデータがData.Vector aであり、要素自体が小さいと仮定しましょう。

  1. データ全体を1つにTVar (Vector a)。STMは、個々の書き込みが共有データ全体に影響を与えている可能性があると考えているため、これにより膨大なデータのコピーが大量に発生すると思います。確かに、読み取りと書き込みが非常にローカライズされていること、および大きなデータ全体での一貫性が必要ないことをSTMが識別する場合、魔法は起こりませんか？

  2. 大量のTVar as、基本的に各要素に1つ、完全にローカライズされたSTMを提供しますが、基本的に全体を複製しますVector a。これはばかげているようです。

  3. TVar (Vector a)データのサブベクトルに対応する妥当な数のsが得られるように、データをセグメント化することによる1と2の間の妥協点。このソリューションは、セグメントの大きさなど、ヒューリスティックに大きく依存していると思います。

  4. メッセージング。各ワーカーは、STMを使用してデータの読み取りと書き込みを行う代わりに、データの読み取り要求またはデータのチャンクをSTMメカニズムなどのSTMメカニズムを介して書き込むメッセージを書き込みますTChan。特別なスレッドがこれらのメッセージを受信し、別のスレッドを介して要求されたデータを渡すTChanか、受信したデータを取得して共有データ構造に書き込みます。このソリューションは、ソリューション1〜3を悩ませている問題がないように見えますが、データの一貫性を維持するためにSTMの優れた機能を使用することを本質的に諦めているようにも見えます。むしろ、それは単なるメッセージパッシングです。確かに、メッセージパッシング部分はSTMで実装されていますが、私の本当の問題はメッセージパッシングで解決されます。STMはとても素晴らしいようです、メッセージパッシングはとても...まあ。

私はこれについて正しく考えていますか？誰かが何かヒントや他の提案がありますか？

私はSTMの経験がなく、上記の解決策をまだ試したことがないことを覚えておいてください。肘掛け椅子から降りますが、何かを試す前にこれらのことを考えておくとよい場合があります。

補遺： 5番目のアプローチはNathan Howellによるもので、を使用していますTArray。それは私が望むもののように聞こえますが、ドキュメントには次のように書かれています。

現在、Array ix（TVar e）として実装されていますが、将来、より効率的な実装に置き換えられる可能性があります（ただし、インターフェイスは同じままです）。

私はこれをTArray、より良い服を着た私のアプローチ2番だと解釈します。「より効率的な」実装について示唆しているドキュメントは、実際にはより優れたアプローチがあることを示唆しているため、興味深いものです。

VagifVerdiの回答のフォローアップ

Vagif Verdiの答えは非常に興味深いので、少し実験して試してみました。今はコードをスリム化する時間がないので、これに興味のある人は、必要不可欠なものだけでなく、コードについても我慢しなければなりません。Int「大きな共有データ」として10^8秒の可変ベクトルを使用し、複数のリーダー/ライターをネットワークソケットに取り込むスレッドに対応させることにしました。

コードは、共有されたデータの読み取りや書き込みさえも行わないことに注意してください。それは単にそこにあり、各スレッドはそれに保持しTVarます。

では、どうなりますか？プログラムを実行すると、すぐに約780 MBのRAMが必要になります。これは、予想されるとおりです（これは、おおよそ10 ^ 8Int秒に必要な量です）。ここで、netcatを使用していくつかのクライアントを接続し、少しのテキストを書き込むと、プログラムはそれを出力し、共有データには書き込まないことになっています。プロセスのCPU使用率は1秒以上100％に急上昇します。 ！！テキストが表示されるまでに顕著な遅延があります。明るい面では、メモリ使用量は一定のままです（Vagif Verdiの回答による）。ベクトルとを削除するとTVar、つまりすべてのSTMと共有データを削除すると、すべてが非常に高速で応答性が高く、クライアントが何かを書き込んだときにCPU使用率が目立つことはありません。

したがって、共有データが実際に複製されていないことを確認するのは非常に良いことですが（これを完全に検証するには、実際に共有データに書き込む必要があると思いますが）、コヒーレント状態の維持には非常に大きなパフォーマンスの低下が伴います。私にとって、私の質問は残ります。STMの優れた点を維持しながら、この問題を適切に攻撃するにはどうすればよいでしょうか。

いくつかの非常に興味深い点を提起してくれたVagifVerdiに感謝します。

4

3 に答える 3

6

STMは魔法ではありません。巨人が1人いる場合TVarは、常に1つを除くすべてのスレッドをブロックする必要があります。これは「粗視化ロック」に相当し、使いやすいというメリットがありますが、STMの要点は粗視化ロックの使用を余儀なくされないことです。このアプローチでは、事実上、一度に1つのスレッドしか書き込むことができません。同じことが「メッセージパッシング」システムにも当てはまります。1つのスレッドがスケーラビリティを制限するボトルネックです。

sの配列を使用することに大きな問題はないと思いTVarます。また、アプローチ2を「ばかげている」と説明する理由もわかりません。これはまさにSTMが行うために発明されたものです。

編集：STMの動機のいくつかについて議論するために、利害関係者にこのビデオ、または少なくともその冒頭を見るように勧めます。それは数年前のものであり、Transactional Boostingに関するものは実際には関係ありませんが、Herlihyは素晴らしく、あなたのものでなくても領域を面白くすることに成功したコンピューター科学者の1人です。

于 2012-03-10T11:27:27.223 に答える
3

まず第一にVector、不変のデータ構造です。を「変更」するときはいつでもVector、それのまったく新しいコピーを作成します。つまり、各変更にはO（n）時間かかります（nはベクトルの長さです）。

第二に、Haskellの値は不変です。を変更するたびTVarに、古い値が新しい値に置き換えられます。

必要なのは、効率的な更新をサポートする純粋に機能的なデータ構造だと思います。2つの例：

  • Data.Map：Key-Valueディクショナリ。これはstd::mapC++のようなものです。

  • Data.Sequence：可変配列に似ていますが、より優れています。

これらのデータ構造の1つを「変更」するときはいつでも、実際には、古い値の一部を内部的に指す新しい値を作成しています。

いくつかのガイドライン：

  • 単一の値のみを変更する場合は、それでatomicModifyIORef十分な場合があります。アトミック更新以外に、より高度な同期が必要な場合はSTM、より適切な選択です。

  • 可変変数を操作するときは、怠惰に注意してください。共有状態を変更するときは、必ず強制してください。これは、を使用して実行できますseq。より便利な方法は、バングパターンを使用することです。例：

    !x <- atomically $ do
    x <- readTVar shared_state
    writeTVar shared_state (changeSomething x)
    return x

    xこれにより、トランザクションの完了後に強制的に評価されます。変数（IORef、、、STRefなどTVar）が何度も変更されたが、強制されなかった場合、サンクはメモリに蓄積されます。結果のサンクを評価すると、スタックオーバーフローが発生する可能性もあります。

プログラムを超並列にする必要がある場合（つまり、複数のコア/ CPUが同時に変数にアクセスする必要がある場合）、プロセッサ間で計算が重複する可能性があるため、このような単一の値の更新は効率が低下する可能性があります。ただし、コアの数が少ない場合、重複は非常にまれです。

于 2012-03-10T12:45:18.980 に答える
1

Haskellには可変配列/ベクトルのいくつかの実装があります。したがって、最も単純なアプローチTVar（Vector a）を使用して、オーバーヘッドのコピーについてあまり心配する必要はありません（可変配列にはコピーはありません）。

これがそのようなライブラリの1つです：http：//hackage.haskell.org/package/vector-0.9.1

于 2012-03-03T19:16:46.613 に答える