HaskellのSTMとトランザクション分離レベル

Hideyuki Tanaka @tanakh

Concurrent Revisionsで書かれたサンタさん読んでるけど、すごいですね。

Hideyuki Tanaka @tanakh

そろそろみんなロックとか条件変数のことは忘れてもいいと思う(´･_･`)・・・

Hideyuki Tanaka @tanakh

Concurrent Revisionsはロックもしなければロールバックもしない。適切なマージ関数を記述させるのと、リビジョンツリーの形に制限を与えるのがキモ

くまぎ @kumagi

HaskellはC++より高速とか謳いながらSTMだったりしてるし、そのSTMはlock-freeとデカデカと書いておきながら実装では堂々とmutex使ってるしで、パフォーマンスを捨てたいのか手に入れたいのかよくわからない。

Hideyuki Tanaka @tanakh

ロックフリーの実装にロック使うのがなんで良くないのか…？ RT @kumagi: HaskellはC++より高速とか謳いながらSTMだったりしてるし、そのSTMはlock-freeとデカデカと書いておきながら実装では堂々とmutex使ってるしで、パフォーマンスを捨てたいのか手に入

くまぎ @kumagi

@tanakh mutex-freeとlock-freeは意味が違います。

Hideyuki Tanaka @tanakh

@kumagi mutex-freeという意味ではないと思います

くまぎ @kumagi

@tanakh 進行保証のない、ブロッキングするSTMの事を通常はlock-freeと呼ばないのです。

Hideyuki Tanaka @tanakh

@kumagi なるほど。

くまぎ @kumagi

lock-freeというのは「これでプログラム中にlockとかunlockとか明記しなくても良くなったぜー！」というノリで付けた名前だろうか。lock-freeなlock-based STM。

Hideyuki Tanaka @tanakh

解決したい問題が違うんでしょうね。ロックで問題になることは、ロックを使うことではないので。

Hideyuki Tanaka @tanakh

多分Concurrent Revisionsで解決したい問題は、STMで生じた問題でしょう。

Hideyuki Tanaka @tanakh

じゃあConcurrent Revisionsでは問題はすべて解決されるのか？というと、やっぱりそうではなくて。

Hideyuki Tanaka @tanakh

多分書けるアプリケーションの幅を絞ってそれらを解決しようとしているのだろう。

Hideyuki Tanaka @tanakh

噛み合ってないのは自分でもわかってるが、何をどう言えばいいのか。

Hideyuki Tanaka @tanakh

というか、STMは高速化を目指したものではないのですね…。圧倒的な記述力をテに入れた代償に速度が遅くなるのをどうやって解決するかって、みんなが努力している類のものです。

くまぎ @kumagi

@tanakh STMで生じた問題…というのは、ゾンビトランザクションでしょうか？それとも速度的な…？

Hideyuki Tanaka @tanakh

@kumagi 速度的な問題とか、それと実装が困難とかでしょうか。

くまぎ @kumagi

@tanakh 実装の困難さも問題になってたんですね…

Hideyuki Tanaka @tanakh

@kumagi はい。STMの実装は実に様々なものが提案されていますし、シンプルかつ高性能なものは僕は知りません。

Hideyuki Tanaka @tanakh

STMが実装に"lock"を使うというのも別になんというか、唯の一つのオプションに過ぎないので、それをもって云々というのは、なんかあれですねえ

くまぎ @kumagi

@tanakh なるほど。ところでHaskellはSTMのトランザクション分離レベルに要求が有るんでしょうか？read-committedがNGだったら効率良く実装できるトランザクションの種類が激減すると思うのです。

Hideyuki Tanaka @tanakh

@kumagi それは可能だと思います。STMのセマンティクスとしては、直列化した時と同じ挙動をする限りどう実行しても良いというものなはずなので。

kumagi @kumagi_bot

lock-basedでありながらread-repeatable分離レベルとマルチリーダーを実現したSTMはHaskell界にも無いと思うというか、lock-free STMというキャッチーな響きに心踊らせて論文開いたらずっとHaskellの話だった心境をですね…！！

くまぎ @kumagi

@tanakh 直列化した時と同じ挙動をする、というのはread-commitedな分離レベルでは不可能です、read-repeatableでないと。serializableな分離レベルというのは、STMにかける制約としては最強のモノとなるので、実装が限られます。