ICFPC 2014

総じておだやかに楽しかった。

https://github.com/shinh/icfpc2014

1日目

初日、21時から問題を読む。んー普通だなーと思いつつとりあえず寝る。

起きて Lambda-man の AI を書きはじめる。普通だと思ったけど、 Lisp マシンってこういうふうな感じなんだなぁ、と、知らなかったので普通に勉強になった。とりあえず思った通りに動くものを作ろうということで、アセンブラを Ruby 上の DSL として書く。オペランドの数と型のチェックと、ラベルの解決をするくらいのやつ。

なんとなく何ができるかわかったところで、これはアセンブラ直書きは大変だし変更に弱い…ってことで、そのアセンブラの上に高級言語を作る必要を感じる。素直に Lisp でもいいけど、あまり Lisp 書き慣れてないので、 Ruby 上の DSL をもう1レイヤ重ねることにした。あとは beflisp の知見を生かして、 LLVM bitcode からの変換ってのも考えたんだけど、そういうのがしたければ複数人がいないとな、て感じ。

きちんと理解する時間がもったいなかったので、 Lisp マシンぽいところなのか、難しそうな命令は無視して、 store 命令を使いまくって、普通にローカル変数をいじりまくるような作りにした。こういうのは書き慣れてるので、割とするっと書ける。引数用に用意された frame だけではローカル変数を置けないなーと思ったので、全ての関数は引数と local 変数を置けるもっと広い frame を作ってから、実際の実装に関数 call する、ってことにした。関数呼び出しのオーバーヘッドが大きくなるけど、関数をあまり呼ばない作りにすれば問題ない。コードサイズの制限はゆるいし、命令キャッシュとか無いわけで、 Ruby のレイヤで関数作ってやれば、 template みたいな感じでコードサイズが大きくなる方向でコードの再利用はできるし。

で、できた DSL で、とりあえず時間とともに移動方向を順番に変えるような AI を作ってみた。これは書きにくいなーということで、 AI を書きながら、色々書きやすくしたりした。まぁそれほど良いものでは無いけど、これで最終日まで戦えるかな、って程度にはなった。

各地点への最短距離を調べるコードを DSL 上で書く。配布されてた3つのマップはクリアできるようになった。よく死ぬのが微妙なんで、敵をある程度避けるようにした。直線上で向きあう動きと、2マスだったかそのくらい接近するのを避けるようにする。

最短距離を調べるコードは getXY とか setXY 的な処理をしまくっていたので、デカいマップで不安だった。これは無理かなぁと思いつつデカいマップで試してみると、当然ダメ。

しょうがないので、最短距離調べるアプローチより弱くなるだろうな…と思いつつ、スコア源に引かれる重力モデルを実装してみる。これでもデカいマップはきつかったけど、速度的にはかなり良くなってたので、見る範囲をしぼったりして対処。しかしやはり弱くなる。

ていうかヘンなところにひっかかったりする。なるべく1ターン前のところに戻るのはイヤがるようにしたりすると、まぁまぁ動くようになる。しかしやはり弱くなったように感じる。

あと1時間くらいでライトニング終わるなーというところで、あ、自分からの近距離だけの map に対してだけ最短距離調べるようにして、それとのハイブリッドにしたらいいんじゃね、と気付いて実装したらかなり良くなった。ただこの時のコードには、左端と上端にいる時に動作が不審になるバグがあったと最終日に気付いた。

この Lambda-man の DSL は Ruby のコードと DSL ぽい部分が混じりまくって (Ruby のループの中で DSL の whileP とかいうループが回ったりしている) 見た目がすごいことになってるのだけど、割と私一人が書くぶんには大丈夫程度のものが、割とスルっと書けたので満足することにした。

うーん ghost の AI も書くのかーとなるとシミュレータも書かないとだなー盛り沢山だなぁ、シミュレータの言語は何にしようかなぁ、と寝る。

2日目

2日目にシミュレータを書く、ってのは割と恒例ではある。言語は GC が欲しいな、ってことで Go にした。 D 言語と悩んだけど、既に入ってた Go に軍配が上がった。 Go はまぁちょくちょく触れるけど、書きやすいよね。 Google 社員的にはノリにすごい慣れてるんだよな。 C++ でもこんな感じのコード書いてるよなあ、っていう。あ、 Chrome とかはだいぶ違うけど。

で、 ghost や lambda-man の処理系は、拍子抜けするくらい簡単に作れたのだけど、そこからがこれも恒例の、ゲームロジックの挙動が微妙に違う祭り。ひとつひとつ仕様の読解/理解ミスを正していく。これはいつも以上にドキュメントが量も多くて細かいところに不明なところが多くて大変だった。途中である程度あってりゃいい気もしてやめようかと思ったけど、まぁ信用できない部品を放置するのは ICFPC ではやばい、っていう経験則からがんばった。

最後はリファレンスインプリのバグまで再現して、あとまあ同時にイベントが起きた時のコーナーケースにミスはあるだろうけど、ってあたりまでやって、終了。しかし、途中で、リファレンスインプリのバグはご丁寧に修正されてしまったので、リファレンスインプリと不整合な結果を返すのは我慢して戦うことになってしまった…

次は ghost を書いてみる。今度は Lambda-man 用のアセンブラをちょっといじって ghost アセンブラを Ruby 上に作る。んーなんか 256 instruction くらいならこれでいいんじゃね、ってことで、それで良いことに。

どういうのがいいのかなぁと考える。素直に襲いかかるやつと、一箇所をひたすら防衛するやつ、とかを考えた。後者はいかにも弱そうなので、襲いかかるやつを作ってみた。適当に作ると、これが結構強い。 Lambda-man が虐殺されている様を見るに、あーこれは効率良く pill を集めるとかよりは、避けゲーかなーと思う。

ただ、適当に作った素直に襲いかかるやつは、最初のサンプルマップの初期位置にひっかかる。あたりまえである。というわけでランダム要素とかをちょっと入れてみる。だいぶ良くなるが、まだみんな同じ行動しがちで意味がない。他の AI の案が思いつかなかったので、もうちょっと散らすことにした。具体的には本家パックマンを参考に Lambda-man が向かってる先を目指す、っていうヒネりが無いやつ。

このへんで、はて一通り提出できる体裁はととのったが、はてどこに力を入れるべきか…と考えつつ寝る。

3日目

なにすっぺかなーと考えつつ、細かいバグとかをなおす。感覚としては、 Lambda-man にもっと高度なプログラム的に賢いことをさせるべきだ、ってのがあった。例えば ghost をシミュレーションして短期間の未来予測をするとか、グラフ構造を作って危険な道とか安全な道とか考えて動かすとか、そういうの。

ただこれは与えられてる clock cycle であるとか、自分のアルゴリズム知識的なことと、あとそもそも ghost は適当に襲いかかるだけでも Lambda-man には結構脅威、ってことから、なんかやってみるかなー別にいいか…ってのを繰り返してるうちに終了した。まぁやんなくて良かったんじゃないかなーと思ってるが、謎。

というわけで、なんか割と作りたい雰囲気のものができてしまっているので、細かい完成度上げに使った地味な一日になった。あと途中で昼寝した。 ICPFC 中に5回寝たのはたぶん新記録。

地味なんだけど、結構 AI の細かい作りこみみたいなの、わりと好きなようで、1日だけだと結構たのしい。

まず、 ghost 強すぎ…ってことで Lambda-man の回避装置をちょっとマシにしてみる。いまいち。ていうか Lambda-man 死ぬ時はだいたい挟まれてるのよね。未来予測とかグラフ作りをそれなりにやらないと、たぶん不幸な未来を避けるのは難しい。ていうかこれ普通に考えると運ゲーにならねー、でも賢い人はこの状況で Lambda-man 生かせるのかな…とか思う。

さて死ぬのは諦めた。しかし怯えてる ghost は得点が高いし、 fruit も得点が高いので、こいつらを優先的に喰うことにしよう、てなことをやる。このへんから一人イタチごっこがはじまる。

あ、私の ghost 、 Lambda-man に襲いかかりすぎるあまり、殺すのはいいんだけど得点渡しすぎてる…と思ったので、怯えモードの時は行くところの優先順位を逆転させてやる。逃げ AI 。

うーん ghost 食いにくくなったのかな、と power pill の隣に待機して、 ghost が近寄ってきたら power pill を食って ghost を食べる、ってのを実装する。いくらなんでも無限に待つとザコ AI 相手に power pill の隣でウロウロしてるだけで終わってしまうので、timeout なんかを実装してやりつつ。

あ、私の ghost 、待ちラムダーマンにやられて、標準 AI より得点渡してる…と気付いたので、 Lambda-man が power pill に近い時には怯えモードにしてやる。逃げる逃げる。

なんとなく Lambda-man の生存率が高くなってる。あたりまえだが怯えモードの時に画面の端までいってしまうので、 Lambda-man の power pill 隣待機作戦は、 ghost 喰うのには成功しないものの、その後しばらく安全に移動できるようになっちゃってるぽい。なるほどということで Lambda-man から遠い時は襲いかかるモードにする。

こういう感じの細かい調整をまぁいろいろ。 Lambda-man が一手で ghost を食える時は喰うとか、なるべくがんばって fruit は喰うであるとか、 ghost も最初の頃に入れたランダムな挙動が Lambda-man に近付いてる時とか逃げてる時に出す必要は無いなーとやめてみたりとか、そういうの。

感想

面白かった、と思う。評判があまり芳しくないぽいのはまぁわかる。問題に面白みは足りないと思う。まぁ L:tG とかと比べるのは酷。ただ、分量は多いので、こういうのは一人でやってると無理ゲー感はあるものの、楽しい。 ICFPC って、結構終わってから、誰かと組みたかったな…と思う年はあるのだけど、今回はそうではなかった。ま、そんなに成績は良くないだろうけど、あーなんか色々やったなー的な充実感があった。

あと今回結構、色んなところで(私が一人でやるという前提に立てば)正しい選択を結構できたのではないかな…という感はある。まぁ、このへんは毎年、あーがんばったなーと思いつつ、他の人の思いもよらない作戦に、あーこのくらいは思いつけるべきだった…って思ってるんだけど。まぁ、今回はそういう裏技が思いつきにくい、割と素直な問題だったと思うんだけど…

2D Lisp

beflisp.bef が 1次元 Lisp しかサポートしてないのはけしからん、と言われてその通りだなぁと思ったので、 lisp2d.c てのを書いて beflisp2d.bef を生成してみました。 bc2bef.cc は全くいじる必要がありませんでした。 Befunge コードが C 書くだけで作れるってのはラクチンですね…

で、こんなコードが動きます。2次元であることに面白い意味を持たせるアイデアが無かったので、単に 2D レイアウトできるようになっただけです。 Befunge 同様コードが交差できるのは少しオシャレ。気をつけないと括弧のつもりで使った v が文字列の一部になったりするので、書くのはかなり大変

(defun fizzbuzz ^        (fizzbuzz 1) @
  ^ zzuB ( 0 (5 n                       dom)
  i                      ^
  f             v        ^                 q
  (                                        eq ^
            ^ fi)        ^                 v  m
            e                                 o
            q            l                 f  d
                         i                 i
            n       (mod n 15) 0) Fizzbuzz v  n

            1       q                         3
            0       e                         v
            1   (if v
            v                                 0
                t                             v
            n   n
            i   i                             F
            l   r                             i
                p        ^                    z
            (if v        ^                    z
                         1
                                              n

                                              v
                         n                    v
                                              v
                         +                    v
                         v           zzubzzif )

追記

TODO の後者の方はやった。3倍はやくなりました。前者の方はとりあえずレジスタって概念を導入してみて、少しだけはやくなりました。次で使う場合はレジスタっていうか Befunge のスタックに残しておけるんで、そういうことをすれば少しだけ速くなるはずですが、そんなとこはボトルネックでは無い気もするのでもういいやという結論に

beflisp.bef と LLVM Befunge backend

https://github.com/shinh/beflisp

Lisp インタプリタを作りました。今度は Befunge で。

https://github.com/shinh/beflisp/blob/master/beflisp.bef

コードを見ればわかりますが、手書きは諦めました。 前回の sed と違って Befunge は数値演算は素直に提供してくれてるので、アドレス計算なんかをするプリミティブが提供しやすいです。ただ、 Befunge-93 は文字列とか関数コールという概念が無いので、手動でフロー管理するのは地獄でしょうね…

ということで、 C で lisp を書いて、それを clang で LLVM bitcode に変換してから、トランスレータで Befunge に変換、という構成になっています。

実装

トランスレータは任意の C コードを Befunge に変換できるようなレベルには全然達していません。例えば型は全部 32bit 決め打ちです。内部実装知ってないとどういう C コードなら通るかとかわかりにくいでしょうし、内部実装知ってる私にもあまりわかってません。ていうかなんで動いてるんだろうっていう感じ。全体的に投げ槍な実装なんで。

LLVM bitcode からトランスレートされた Befunge コードってのは、あたりまえですが割とデバッグが大変です。しょうがないので小さな C プログラムを一つずつ動くようにしていく感じでやりました。あとデバッグしやすいように元に bitcode を実行しない領域に置いてあります。

大変だったのはまずブランチとかですかね。立体的にコード配置するのはデタラメに大変に決まってるので直線的に実行したいので。スタックトップが真ならスタックの2番目を採用、偽なら3番目を採用、ってことができるプリミティブを作ってそれをあちこちで使う感じにしました。ブランチといえば当然 PHI もダルいったらありゃしない。

LLVM のバックエンドの書く作法を調べるのが面倒だし、 LLVM のバックエンド用の共通基盤が Befunge みたいな素頓狂な実行モデルにうまいこと適合するとは思いがたかったので、 bitcode 読んでからは全自力です。レジスタアロケーションだけやってもらえたりするとラクに生成されたコードを小さくできるんですが…

機能としては前回の sed と同じはずです。前回のテストコードは全部パスしてますし、 FizzBuzz on Lisp on Lisp on Befunge も動いています。すごく遅くて、半分で 1 時間とかかかってますけど。

TODO

レジスタアロケーションをやるってのと、ブランチの高速化、ってのがあります。このふたつやればもう少し実用的な速度になるんでないかなぁと。

というのは、前者は、現状 SSA の結果は全部スタックに残していっていて、スタックがまあまあ遠いところにあるんでアクセスにかかる命令数が多いということがあり。

後者はもっとひどい話で、現状どこかで jmp や call があると、必ずプログラムの一番先頭まで戻ってから次に実行する場所を線型探索してます。そうでなくてちゃんと差分だけ動くようにすれば、近くへの jmp とかが劇的に速くなるかと思います。

あとは free が実装されてないってのがひどいんですけど、当然のことながら実装するとすごく遅くなっちゃうと思われるので、だるいかなあと。

まとめ

Befunge はまともな言語

sedlisp.sed

https://github.com/shinh/sedlisp

Lisp インタプリタを書きました。 sed で。

https://github.com/shinh/sedlisp/blob/master/sedlisp.sed

README に書いた通り、それなりにややこしいプログラムも動く気がします。具体的には eval.l として、 eval の無いところで eval を実装しました。で、その上で FizzBuzz なんかが動きます。これはつまり S 式のパースは省略した Lisp のインタプリタと言って良いので、 sed で書かれた Lisp の上で Lisp が動いて、その上で FizzBuzz が動いてることになります。ちなみにもう一段かますことはできませんでした。 Ruby で書いた実装でも動かないので、 eval.l がとりあえず循環できない作りになってしまってるみたいですが、デバッグできないので何が間違ってるのかよくわかってません… (追記: id:Irori さんがなおしてくれました! FizzBuzz on Lisp on Lisp on Lisp on sed が動く!)

正直疲れたんで s/// 以外の sed script 書くのやめようかと思いますね…なんか途中から ruby で等価なプログラムを書いてテストしはじめたのですが、 ruby の実装は 1 時間もかかってないのに対して、 sed の方は 40 時間くらいはかかってるんでないかなーと思います。

あとは実装について

加減乗除

加算減算は何度か書いたのでやるだけ作業です。動作の説明は

http://shinh.skr.jp/slide/mederu/048.html

などにあります。

乗除はめんどくさいので Lisp で組み込み関数として書きました。 neg? という関数だけ sed で実装して、割り算の実装に使っています。

次に実行する場所

関数しか無ければ、中から実行すればいいので、最左にある、その中に括弧の無い括弧の組を実行すれば良いです。正規表現で書くと ([^()]*)

大変なのは special form というやつです。 if とか defun とかは、中を先に実行しちゃまずくて、外から実行していく感じになります。これは最左の括弧の組を一旦 @ に変換しておいて、 @ より左に special form があれば、そっちを先に実行、という方式でやりました。

 (+ 2 (if t (+ 3 4) 5))

みたいな式があると、 (if t (+ 3 4) 5) だけを取り出す必要があるわけですが、これも正規表現ってやつはご存知の通りネストした括弧の組を取り出すとかできないので、かなりめんどくさいです。

具体的には (if の中の括弧の組を @ で取り出していって、 (if の中に括弧が無くなれば @ を復元、というようにやりました。

この方式では defmacro の実装はありえないくらいめんどくさいことになります。当然実装してません。

スタック

次に実行する場所を切り出せたら、切り出した以外の場所をスタックに保存しておかなければなりません。これは以前にもやったことがあって、切り出した部分を @ に置換しておいて、その @ を含んだ式をスタックに置いておきました。

さっきの if 文なら

 (+ 2 @)

のようなものがスタックに積まれて、 (if ...) の評価が終わると結果を @ と置換して実行を続けます。

sed にはスタックなどという便利なものは無いんで、ホールドスペースの末尾に一行ずつ書いていくことにしました。

define と defun

define で変数を定義すると、ホールドスペースの先頭の変数を置く空間に書きます。

 (define foo 42)

は

 ;foo;42;

などと定義されます。

変数の展開は、変数一覧をパターンスペースに持ってきてから、正規表現の後方参照でやります。

 s/^\([^\n]*[ ()]\)\?\(\S\+\)\([ ()\n].*\n;\2;\([^;]*\)\)/\1\4\3/

というような感じで…と言ってもなんのこっちゃわからんかもしれませんが、

$ echo '(func foo)@;foo;42;' | sed 's/^\([^@]*[ ()]\)\?\(\S\+\)\([ ()@].*@;\2;\([^;]*\)\)/\1\4\3/'

などとすると foo が 42 に置換されるので、そういうもんです。 (\n は @ に置換しておきました)

defun は単に define と lambda のシンタクスシュガーです。

quote と lambda

このコードの全域で値の区切りとして空白を使っているので、 quote や lambda にある空白は厄介、というかそのままでは全く取り扱えないです。あと括弧も残ってると絶望的です。

しょうがないので、内部的に括弧と空白を別な文字に置換して取り扱ってます。 (quote (4 5)) は [4,5] に、 {lambda_{n_m}_{+_n_m}}$ に置換してあります。 lambda の末尾についている $ は、 lambda を関数適用する時に lambda が引数として渡されたりすると大変なことになるので、ターミネータが必要だと気付いて足したものです。

lambda の適用は、特に引数の処理はだいたい変数の展開と同じです。

print 関数はこのへんをそのまま出力するので、

 (print (lambda (n m) (+ n m)))

などとすると内部表現が見られます。

まとめ

他にもいろいろハックでごまかしてる部分などがあって、大変でした。 evalify した sort とかよくうごいてるなーという感じ。

失敗ロック例いくつか

なにかあまりスレッドとか得意でない人のコードを見ていて、いくつかダメな予感がするパターンがあるよね、ってことで適当に集めてみました。どれもこれも小さな例にすると、こんなミスしねーよ、って感じなんですけど、複雑なコードの中にあると結構ミスるもんかな、と。私自身マルチスレッドはたいへん苦手で、実際私がやらかしたケースもいくつか。

ひとつめ: ロック順序逆転

// そこらじゅうで確保されてるグローバルなロック
pthread_mutex_t g_mu = PTHREAD_MUTEX_INITIALIZER;

// このクラスを使うところは全域 g_mu でロックされてるとします
class C {
public:
  C() {
    pthread_mutex_init(&mu_, NULL);
  }
  void doSlowOperation() {
    pthread_mutex_lock(&mu_);
    // この処理は重いから先にロックを解放しておこう!
    pthread_mutex_unlock(&g_mu);
    // Slow operation.
    pthread_mutex_lock(&g_mu);
    pthread_mutex_unlock(&mu_);
  }
private:
  pthread_mutex_t mu_;
};

使っている例: https://github.com/shinh/test/blob/master/badlock1.cc

このコードは thread A が出口付近で g_mu を取ろうとする時に、他のスレッドが入口付近で mu_ を確保しにいくと、デッドロックします。

教訓としては、複数ロックがネストする時はとりあえずデッドロックを心配すると良い気がします。ネストする場合は、二つのロックを取る順序は必ず同じ順序で取るようにするべき。ロック1とロック2がある時に、ロック1,2両方取られている時間と、ロック1だけが取られている時間と、ロック2だけが取られている時間があると、まぁだいたいやばいです。

まぁ、この場合は本当に g_mu を外さにゃいかんのかをまず考えた方がいい気がします。あちこちで確保されてるロックが一つだけ、って状態は性能に問題が出るまでは割と安心な状態です。

ふたつめ: 同じ変数に別のロックを使う

// そこらじゅうで確保されてるグローバルなロック
pthread_mutex_t g_mu = PTHREAD_MUTEX_INITIALIZER;

// このクラスを使うところは全域 g_mu でロックされてるとします
public:
  C() {
    pthread_mutex_init(&mu_, NULL);
  }
  void doSlowOperation() {
    // この処理は重いから先にロックを解放しておこう
    // ひとつめではデッドロックしてしまったから先に外しておく
    pthread_mutex_unlock(&g_mu);
    pthread_mutex_lock(&mu_);
    for (int i = 0; i < 5; i++)
      vals_.push_back(i);
    pthread_mutex_unlock(&mu_);
    pthread_mutex_lock(&g_mu);
  }
  void doFastOperation() {
    // g_mu が取られてるから大丈夫!
    vals_.push_back(42);
  }
private:
  pthread_mutex_t mu_;
  std::vector<int> vals_;
};

使っている例: https://github.com/shinh/test/blob/master/badlock2.cc

doSlowOperation を見る限り、 vals_ は mu_ で守られてるべきっぽいですが、 doFastOperation では g_mu に頼ってます。普通に race condition があるので、この場合普通にクラッシュしました。

教訓としては、なにかロックしてるから大丈夫、ではなくて、適切なロックを使ってるかどうかを常に意識すると良いです。どのロックに守られてるか、ってのは C++ の所有権並に重要なことだと思うんで、 mutex をメンバに持たせる時は、その mutex がどの変数をガードするかどうかをコメントするようにするとやや良い気がします。

みっつめ: ロック順序逆転してない?

class C {
public:
  explicit C(int val) : val_(val) {
    pthread_mutex_init(&mu_, NULL);
  }
  int add(C* c) {
    // 必ず mu_ => c->mu_ の順序でロックするよ!
    pthread_mutex_lock(&mu_);
    pthread_mutex_lock(&c->mu_);
    int r = val_ + c->val_;
    pthread_mutex_unlock(&c->mu_);
    pthread_mutex_unlock(&mu_);
    return r;
  }
private:
  pthread_mutex_t mu_;
  int val_;
};

使っている例: https://github.com/shinh/test/blob/master/badlock3.cc

C::add はぱっと見首尾一貫した順序を守ってるように見えるんですが、 this と引数 c が逆転すればひとつめの例と同じで、ロック順序が逆転しているのでデッドロックします。

具体的には、 c1->add(c2) と c2->add(c1) があったとして、前者が c1 のロックを取る→後者が c2 のロックを取る、という順序で起きると次のロックはどちらも取れません。

これはこのクラスの使い方によっては、問題無い場合もあります。必ず一定の法則に従って add のレシーバと引数を選んでいれば大丈夫で、たぶん、

assert(c1 != c2);
c1 < c2 ? c1->add(c2) : c2->add(c1);

とかしていれば大丈夫…な気がします。自信がないですが。

がまぁ素直になんとかした方がいいと思います。パフォーマンスに問題が無ければ mu_ を static にしてしまうのがラクチンです。

よっつめ: 狭義のレースは無いのだけど

class C {
public:
  explicit C() {
    pthread_mutex_init(&mu_, NULL);
  }
  void setVals(std::vector<int> vals) {
    pthread_mutex_lock(&mu_);
    vals_ = vals;
    pthread_mutex_unlock(&mu_);
    // Update the cache.
    setSum(calcSum());
  }
  int getSum() {
    pthread_mutex_lock(&mu_);
    int sum = sum_;
    pthread_mutex_unlock(&mu_);
    return sum;
  }
  void setSum(int sum) {
    pthread_mutex_lock(&mu_);
    sum_ = sum;
    pthread_mutex_unlock(&mu_);
  }
  void check() {
    pthread_mutex_lock(&mu_);
    int sum = 0;
    for (size_t i = 0; i < vals_.size(); i++)
      sum += vals_[i];
    assert(sum == sum_);
    pthread_mutex_unlock(&mu_);
  }
private:
  int calcSum() {
    pthread_mutex_lock(&mu_);
    int sum = 0;
    for (size_t i = 0; i < vals_.size(); i++)
      sum += vals_[i];
    pthread_mutex_unlock(&mu_);
    return sum;
  }
  pthread_mutex_t mu_;
  std::vector<int> vals_;
  int sum_;
};

使っている例: https://github.com/shinh/test/blob/master/badlock4.cc

vector を持っていて、その合計値がよく欲しくなるので、合計値をキャッシュとして持っておく、というような想定で書かれたコードです。ロックが一つしか無くて、 vals_ も sum_ も mu_ にしっかりガードされてるので安心…ではないです。

たしかに vals_ や sum_ に同時アクセスするケースは無いのですが、 sum_ が vals_ の合計でない値になってしまう場合があります。というのは setVals が calcSum や setSum でいちいちロックを外してしまっているので、例えば、 calcSum が 30 という結果を返す→ setVals が別スレッドで呼ばれて sum_ が 50 にアップデートされる→元のスレッドに戻って sum_ に 30 を代入する、のような。

この手のレースはなんと呼ぶのか知らないのですが、一つの変数へのアクセスはちゃんとガードされてるので、 thread sanitizer なんかの race detector にかからず、 annotation をしっかり書いても見つけてくれないはずです。 QuickCheck なんかがこういうのを探してくれる、って話だったような。

この手の、メンバ変数 A が○○なら B は必ずこれを満たさなければならない…みたいな条件があるクラスはマルチスレッドでなくてもあまり嬉しくないですね。パフォーマンスに問題なければそもそもキャッシュしたくないわけですが、まぁこの例ではパフォーマンスに問題があったから calcSum を private に移してキャッシュすることにしたんだなぁ、という流れが透けて見える感じです。 check みたいな関数を用意してやたら呼びまくるのは安心感があっていい方法ではあると思います。

ちなみに修正例:

class C {
public:
  explicit C() : sum_(0) {
    pthread_mutex_init(&mu_, NULL);
  }
  void setVals(std::vector<int> vals) {
    pthread_mutex_lock(&mu_);
    vals_ = vals;
    // Update the cache.
    sum_ = calcSumLocked();
    pthread_mutex_unlock(&mu_);
  }
  int getSum() {
    pthread_mutex_lock(&mu_);
    int sum = sum_;
    pthread_mutex_unlock(&mu_);
    return sum;
  }
  void check() {
    pthread_mutex_lock(&mu_);
    int sum = 0;
    for (size_t i = 0; i < vals_.size(); i++)
      sum += vals_[i];
    assert(sum == sum_);
    pthread_mutex_unlock(&mu_);
  }
private:
  int calcSumLocked() {
    int sum = 0;
    for (size_t i = 0; i < vals_.size(); i++)
      sum += vals_[i];
    return sum;
  }
  pthread_mutex_t mu_;
  std::vector<int> vals_;
  int sum_;
};

こういう hogehogeLocked みたいなのは、こういうクラスだとよく必要になる気がします。

いつつめ: rwlock

最後ふたつは mutex よりは使用頻度が低いもので。

class C {
public:
  C() : val_(3) {
    pthread_rwlockattr_t attr;
    pthread_rwlockattr_init(&attr);
    pthread_rwlockattr_setkind_np(
        &attr, PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP);
    pthread_rwlock_init(&mu_, &attr);
    pthread_rwlockattr_destroy(&attr);
  }
  int calcSomething() {
    pthread_rwlock_rdlock(&mu_);
    // getVal の中で同じロックを取るけど、 reader lock だから大丈夫!
    int r = 42 + getVal();
    pthread_rwlock_unlock(&mu_);
    return r;
  }
  int getVal() {
    pthread_rwlock_rdlock(&mu_);
    int r = val_;
    pthread_rwlock_unlock(&mu_);
    return r;
  }
  void setVal(int val) {
    pthread_rwlock_wrlock(&mu_);
    val_ = val;
    pthread_rwlock_unlock(&mu_);
  }
private:
  pthread_rwlock_t mu_;
  int val_;
};

使っている例: https://github.com/shinh/test/blob/master/badlock5.cc

以前書いた話 です。 calcSomething の中でヘルパ関数 getVal を呼んでいるのは、 glibc のデフォルトの pthread_rwlock_t なら大丈夫なんですが、この場合 writer starvation を回避する rwlockattr をつけてるのでデッドロックしてしまいます。また、 pthread の実装によってはデフォルトのでデッドロックするそうです。

writer starvation とは、 reader がたくさんいて、一つのロックに常に複数の reader lock を reader が取ってしまっていて、全然 writer がロックを取れない状況を言うそうです。これを回避するために、 writer が待ってる時は新規 reader を受け付けない、という処置がされているロックがあって、まぁこれつけないとパフォーマンス上使いものにならんケースが多いようです。

ただ、このタイプの rwlock を使うと、 thread 1 が calcSomething の reader lock を取る→ thread 2 が setVal の writer lock を待ちはじめる→ thread 1 が getVal の reader lock を取ろうとするが、 writer が待ってるので取れない、という形のデッドロックになります。

教訓としては必要がなければ rwlock をそもそも使わない、ってのがあるかと思います。あとまぁ普通に reader lock だろうと nest させてると良くないなっていう。普通のロックに変えれませんし。

あと

condition variable のダメケースを作ろうかと思ったんですけど、あんま短くていい感じのが作れなかったので省略。一般に lock の外で cond_signal すると cond_wait で拾えないケースがある…ってやつが短く書けない。順序によっては普通に大丈夫なんですよね…

あと別解

存在を忘れかけてたんですけど、 Haskell, Falcon, Lua を消して Scheme, Clojure, Common Lisp を足そうとしたバージョンがあったんですが、 ideone の Scheme が Gauche じゃなくて Guile だったので萎えたバージョン:

http://shinh.skr.jp/obf/polyadd2.txt

こっちの方向性で assembly を加えて 13 にする予定だったんですけど、挫折しました。