haskell - Haskellでのロックフリープログラミング

Question

Haskellでロックフリープログラミングを行うことが可能かどうか誰かが知っていますか？適切な低レベルのプリミティブが利用可能かどうかの問題と、（利用可能な場合）純粋な機能コンテキストで機能する大規模システムを構築するためにこれらを使用することに関して機能する情報についての両方に興味があります。（私はこれまで純粋関数のコンテキストでロックフリープログラミングを行ったことがありません。）たとえば、私が理解しているように、Control.Concurrent.Chanチャネルは（私が理解しているように）ロックを使用するMVarの上に構築されています-- -原則として、内部でロックされていないバージョンのChanプリミティブをビルドできますか？どのくらいのパフォーマンスの向上を期待できますか？

また、私はTVarの存在に精通しているが、それらの内部実装を理解していないと言うべきです---ほとんどロックフリーであることを理解するように言われましたが、それらがそうであるかどうかはわかりません完全にロックフリー。したがって、TVarの内部実装に関する情報も役立ちます。

（このスレッドはいくつかの議論を提供しますが、もっと最新の/より包括的なものがあるかどうか疑問に思います。）

Answer 1

MVarはロックを使用するだけでなく、ロックの抽象化でもあります。そして、私が思い出したように、個々のSTMプリミティブは楽観的ですが、STM実装のさまざまな場所で使用されるロックがあります。便利な韻を覚えておいてください：「ブロックできる場合は、ロックに注意してください」。

実際のロックフリープログラミングでは、IORefを直接使用する必要がありますatomicModifyIORef。

編集：ブラックホールに関しては、実装はロックフリーであることを思い出しますが、詳細を保証することはできません。このメカニズムについては、「マルチコアHaskellのランタイムサポート」で説明されています：http ：//research.microsoft.com/en-us/um/people/simonpj/papers/parallel/multicore-ghc.pdf

しかし、SimonMarlowの2010HaskellImplementationsWorkshopの講演「SchedulingLazyEvaluationon Multicore」（http://haskell.org/haskellwiki/HaskellImplementorsWorkshop/2010 ）で説明されているように、その実装にはいくつかの調整が加えられたと思います。スライドは残念ながらオフラインですが、ビデオは引き続き機能します。

Answer 2

Haskellではロックフリープログラミングは簡単です。多くのスレッドで変更する必要のある共有データを作成する最も簡単な方法は、通常のhaskellタイプ（リスト、マップ、多分、必要なもの）から始めて、IORefに配置することです。これを実行すると、atomicModifyIORefを使用して、適切な場所で変更を実行できるようになります。これにより、すぐに実行できることが保証されます。

type MyDataStructure = [Int]
type ConcMyData = IORef MyDataStructure

main = do
    sharedData <- newIORef []
    ...
    atomicModifyIORef sharedData (\xs -> (1:xs,()))

これが機能する理由は、IORef内の結果を最終的に評価するthinkへのポインターが格納され、スレッドがIORefから読み取るたびに、サンクを取得し、必要なだけの構造を評価するためです。すべてのスレッドがこの同じサンクを読み取ることができるため、評価は1回だけになります（複数回評価された場合は、常に同じ結果になることが保証されているため、同時評価は問題ありません）。これは正しいと思いますが、訂正できてうれしいです。

これからの持ち帰りのメッセージは、この種の抽象化は純粋な言語でのみ簡単に実装でき、物事の価値は決して変わらないということです（もちろん、IORef、MVars、STMタイプなどのタイプの場合を除きます）。Haskellのデータ構造のコピーオンライトの性質は、変更された構造が元の構造と多くのデータを共有できる一方で、構造に新しいものだけを割り当てることができることを意味します。

これがどのように機能するかをうまく説明できたとは思いませんが、明日戻って答えを明確にします。

詳細については、MicrosoftResearchのSimonMarlow（および主要なGHC実装者の1人）によるHaskellでのマルチコアプログラミングの講演のスライドを参照してください。

Answer 3

stm 、特にそのTChanタイプを調べてください。