ロックとモジュラリティ、メモリ管理と型安全性

Hideyuki Tanaka @tanakh

あっー、100ブクマ超えとる。Concurrent Revisions知名度上がって欲しい： モダン並列・並行プログラミング ～ Concurrent Revisions による実装と現実 ～ http://t.co/Vd4H7aS5 via @preferred_jp

KOYAMA Youichi @koyama41

@tanakh 面白いスライドでした。しかしオロカな私は32ページの「まちがい(2)」のどこが当然バグなのかわかりませんでした… ロック順番があやしいのでデッドロックはしそうですけど、「順番は今は不問」なんですよねえ？

Hideyuki Tanaka @tanakh

@koyama41 そこはちゃんとソートしてロックするコードを書くとページに収まらなくなるので省略してただけでした。すいません。あと、先のページで獲得すべきロックは最初にまとめて取らなければ、デッドロックする可能性があるという説明になっているので、こういう処理はバグだという話です

KOYAMA Youichi @koyama41

@tanakh ん、じゃあ直前のページにある「順番は今は不問」というのは、どういう意味だったんでしょうか。デッドロックの問題はとりあえず脇においといてもバグがあるという話をしようとしてるのかと思ったのですが

Hideyuki Tanaka @tanakh

@hararan_2010 なるほど、やはり曖昧な例がありますね…

Hideyuki Tanaka @tanakh

@koyama41 ロックの順番ちゃんとやるのを端折ってるだけで、まちがい（２）の方のバグもデッドロックの可能性の話です。あとIsolationが破られてます。

KOYAMA Youichi @koyama41

@tanakh うーん、ロックの順番をスライドの都合上てきとうにしてるだけならばデッドロックバグの例になってないような気がしますが、どういうことを言いたかったんでしょうか？

Hideyuki Tanaka @tanakh

@koyama41 bとaを逆にした呼び出しが同時に走ると、このままではデッドロックする可能性があると思うのですがどうでしょう？

KOYAMA Youichi @koyama41

@func_hs 速度を基準にするんだったら二分探索に限定しない方が面白そう。つまりぶっちゃけバカサーチでも速ければ勝ち。でもバカサーチで勝てるような規模の入力にはしないでしょうから、結果として二分探索ぐらいはやらないといけなくなる、という寸法で。

KOYAMA Youichi @koyama41

@tanakh それはそのとおりですね。ただ、「順番は不問」という言葉からは、何を端折ってて何をここでの問題として取り上げたいのかがよくわからなかったのです。

Hideyuki Tanaka @tanakh

@koyama41 なるほど。ちょっと書き方が悪かったですね。

KOYAMA Youichi @koyama41

@tanakh あと、 Isolation が破られているというのはどういう場合でしょうか？まちがい(2)の方のページの話ですよね？ （まちがい(1)はデッドロックさえ起きなければ安全そうなので）

Hideyuki Tanaka @tanakh

@koyama41 はい。（２）の方のつもりでした。しかしよく考えたら破られてないような気がしてきました。この場合は引き出せなかったら状態が変わっていないので。

KOYAMA Youichi @koyama41

@tanakh ああ、やっぱりそのへんでしたか。 withdraw が破壊的に引き出しっぱなしだったら困るなーと思いつつ、もしそうならそもそもまちがい(1)のコードもひどいもんだからそういう話じゃないよなあ、と思ったのでした

Hideyuki Tanaka @tanakh

ロックの話もメモリ管理の話もそうだけど、あれは気をつけなきゃ死ぬぞって類の物ではなくて、本質的にソフトウェアの抽象性を破るものだとちゃんと理解しないといけない。前者はモジュラリティ、後者は型安全性。そこが解ってないと、僕はロック忘れなんてしませんから、ていう話になってしまう。残念

Hideyuki Tanaka @tanakh

今度は別のDeterministic Parallelismも紹介したい。Concurrent Revisionsはどうなるかわからんけど、Implicit Parallelismは（ちゃんと性能を出すには）難しすぎると思うので、だんだん廃れてくると思うし。

KOYAMA Youichi @koyama41

@tanakh メモリ管理では型安全の話以外にGCの有無でもモジュラリティに差がでます。Cだと例えばstatic領域を指すポインタを返すstrerror()に対しstrerror_rというバッファを渡すAPIが泥縄式に追加されましたが、最初からGCがあれば避けられたはず。

鯉江 @koie

@koyama41 @tanakh メモリ管理をＧＣというひとつ下のレイヤに押しつけたのと同じように、ロックもロックマネージャの管理下でするってことにすればデッドロック検出できるので、ぜんぜん問題ないってことにはならない？

SKS rep @repeatedly

@koie それがSTMとかなのでは？

KOYAMA Youichi @koyama41

@koie メモリ管理をGCという下のレイヤに押し付けたことはプログラミングスタイル自体を変えました。同様に、ロックを下のレイヤにおしつける場合、単にロックマネージャを作ってデッドロックを検出させるのではなく、プログラミングスタイル自体を変えるような機構が必要だと思います。

鯉江 @koie

@repeatedly STMは最後のcommitでいっきに書き換えるのに対して、ロックだとデッドロックしたときにロールバックするという違いになるとおもいますが、コーディングスタイルはおんなじになりそうですね。

SKS rep @repeatedly

@koie デッドロックを検出したらロールバック，というロックの実装を知らないんですが，そういうライブラリってあるんですかね？

鯉江 @koie

@repeatedly いやいや、ここは妄想です。ロックが必要な変数を参照･書き換えるところに処理系がrwlockするコードを挿入してくれて、デッドロック通知をうけたら前の値に書き戻しながら戻っていく、みたいな。

Hideyuki Tanaka @tanakh

@koie @koyama41 それはデッドロックは解消できても、ライブロックになりやすそうで、それはどうにもならなそうな気がしますけどどうでしょう。あとそれだとデッドロックの問題しか解消しないと思います。

SKS rep @repeatedly

@koie Intelがそういうのの静的解析をしているという噂は聞いたことありますが，デッドロックはデッドロックなので，起きたらもう終わりですね．やるならロック機構をシミュレートする必要があるとは思いますが，それならcomposableなSTMの方が楽そうです．