読者です 読者をやめる 読者になる 読者になる

ふと思いついて書いた。後悔はしていない。

ネタ

昨日、マルチスレッドなプログラムのコードを読んでたんです。マルチスレッド。
そしたらなんかロックがめちゃくちゃ競合しててパフォーマンスが出ないんです。
で、変更履歴よく見たらなんか全メソッドを一つのmutexでロックして、マルチスレッドに対応した、とか書いてあるんです。
もうね、アホかと。馬鹿かと。
お前らな、単一mutexで囲うだけの対応如きでマルチスレッド対応とか言ってんじゃねーよ、ボケが。
単一mutexだよ、単一mutex。
なんかthreadを作りまくってる箇所もあるし。多重ループの内側でthread生成か。おめでてーな。
よーしデータを細分化してガンガン別スレッドで処理しちゃうぞー、とかやってるの。もう見てらんない。
お前らな、Fork/Joinフレームワークのスレッドプール実装やるからそれ使えと。
マルチスレッドってのはな、もっと殺伐としてるべきなんだよ。
Work-stealing dequeを持ったスレッド同士がいつタスクをstealしてもおかしくない、
盗むか盗まれるか、そんな雰囲気がいいんじゃねーか。Lock-freeじゃない奴は、すっこんでろ。
で、ようやくdata raceの箇所を見つけたかと思ったら、コメントに、gccの最適化でバグるのでvolatileを付ける、とか書いてるんです。
そこでまたぶち切れですよ。
あのな、volatileなんてC++のマルチスレッドプログラムじゃ意味ねーんだよ。ボケが。
得意げな顔して何が、最適化でバグる、だ。
お前は本当にメモリモデルを理解してるのかと問いたい。問い詰めたい。小1時間問い詰めたい
バグってるのはお前のコードのほうちゃうんかと。
マルチスレッド通の俺から言わせてもらえば今、マルチスレッドプログラミングでの最新流行はやっぱり、
non seq_cst atomics、これだね。
非seq_cstなatomic変数 + seq_cst fence。これが通の作り方。
non seq_cst atomicsってのはatomic変数へのアクセスにmemory_order_seq_cstを指定しない。そん代わりオーバーヘッドが少なめ。これ。
で、それを補完する明示的なmemory_order_seq_cstメモリフェンス。これ最強。
しかしこれをやると次からHans Boehm先生にマークされる*1という危険も伴う、諸刃の剣。
素人でなくてもお薦め出来ない。
まあお前らド素人は、毎日 Good morning all! とでもつぶやいてなさいってこった。

*1:Boehm先生はdata raceによる絶望からプログラマを救うため、seq_cst以外のatomic変数を全て消し去りたいと願っているのです。

私立C++女学園 マルチスレッド科

ネタ

ここは私立C++女学園。
由緒あるこの学園も、時代の流れに押され大きな変革の時を迎えていた。新たに学園に設けられることとなった「マルチスレッド科」。物語はここから始まる……

登場人物

memory_order_seq_cstさん
学級委員長。どんなことも完璧にこなす優等生であり、先生や他の生徒からの信頼も厚い。ただ、あまりの完璧主義者ゆえに、何でも全て順番どおりにやらないと気が済まないところが、ある意味欠点でもある。
memory_order_releaseさんとmemory_order_acquireさん
シンクロナイズドスイミング部に所属する双子の姉妹。二人の息の合ったシンクロ演技には、部内に限らずファンが多い。学園内では、memory_order_seq_cstさんと人気を二分していると言ってよいだろう。
memory_order_acq_relさん
あまり目立たない生徒だが、実はmemory_order_releaseさんやmemory_order_acquireさんの姉である。才能に恵まれているにも関わらず、その存在感の薄さ故にC(ry先生からも忘れ去られてしまったこともある不遇の生徒。
memory_order_relaxedさん
一見すると普通の平凡な生徒。しかし彼女は、魔法の杖(fence)によって変身する魔法少女なのである。魔法の力で何でもできるはずなのだが、実際はよく変身に失敗してしまうドジっ娘属性の持ち主である。
memory_order_consumeさん
学園一の不良生徒。彼女のために校則すらも書き変えられたという逸話がある。夜な夜な公道レースに参加しているという噂もあり、彼女のスピードに魅了された者たちが死のレース(data race)によって次々と命を落としているらしい……
Java女学院のvolatileさん
C++女学園から少し離れたところにあるJava女学院のマルチスレッド科に所属する生徒。昔、とある問題に躓いたことをきっかけに猛勉強した結果、他の学校からも一目置かれるほどの才女となった。memory_order_seq_cstさんが慕い、目標としている相手が彼女である。そのせいか、二人の仕草はとてもよく似ている。
C++女学園のvolatileさん
よく間違われるのだが、彼女はマルチスレッド科の生徒ではない。勘違いで彼女宛に送られてくる手紙の多さに、いつも辟易としている毎日である。

メモリバリアを理解するために必要な3つのこと

programming multithreading

Togetter - 「メモリバリアとガチャピン先生」
上の話において、「メモリバリア」の意味するところをもう少し明確にすべきかなあと思ったので、簡単にまとめてみます。
「メモリバリア」が満たすべき性質は、以下の3つに分類することができます。

  1. atomicity
  2. release/acquire fence
  3. sequential consistency

これらの性質は、C++0xのmemory_orderと以下のように対応しています。

C++0x memory_order 持っている性質
memory_order_relaxed atomicity
memory_order_acquire, memory_order_release, memory_order_acq_rel atomicity + release/acquire fence
memory_order_seq_cst atomicity + release/acquire fence + sequential consistency

atomicity とは文字通り「不可分な」操作を保証するものですが、その影響は操作対象のオブジェクトに限定されます。つまり、あるatomic変数に対する memory_order_relaxed でのアクセスは、他の変数に対するアクセスの順序付けには何も影響しません。
一方 release/acquire fence では、release操作とacquire操作の対によってアクセスの順序付けを行ないます。この順序付けの効果は、releaseより前とacquireより後にある全ての変数に対して影響します。
そして、この release/acquire fence を用いても実装できない、「複数のatomic変数に対する書き込みの見た目の順序に依存するようなアルゴリズム」を実装するために必要なのが sequential consistency になります。
これら3つの性質について、x86アーキテクチャでの実現方法は以下のようになります。

単純なread, write read-modify-write
atomicity 対象の変数が正しくalignされていればよい lock-prefix付き命令を用いる
release/acquire fence 自動的に保証される 自動的に保証される
sequential consistency writeを XCHG または MOV+MFENCE にする lock-prefix付き命令を用いる

このように、CMPXCHGやXADDなどのread-modify-write命令では atomicity の実現のためだけでも lock-prefix が必要となりますが、その結果 sequential consistency までもオマケに付いてくることになるわけです。

ハザードポインタ版Lock-Free List

programming multithreading

前回の記事で時間切れのために書ききれなかった Lock-Free List について、サンプルコードをgithubに上げました。
yamasa/lockfree · GitHub
sortedlistmap.h がそれです。わかりやすくするため、Allocator対応などの細かい機能については省いています。決して手抜きではありません。;-)
Lock-Free List のアルゴリズムについてはkumagiさんの解説記事が非常にわかりやすいので、そちらをご覧ください。

lock-freeアルゴリズムにおけるメモリ回収

programming multithreading

これは C++ advent calendar の参加記事です。
もともとは「マルチコア時代のLock-free入門」の補遺として書くつもりだったのが、何だかんだで一年近くほったらかしになってしまっていたので、今回 advent calendar という締切りを課すことでようやく書くことができました。(笑)
前の発表で、lock-freeアルゴリズムを C++ で実装するには「タグ付きポインタ」や「Hazard pointer」を使いましょうと言いましたが、具体的な実装コードについてはあまり触れませんでした。そこで、実際に「タグ付きポインタ」と「Hazard pointer」を使い、代表的なlock-freeアルゴリズムである Lock-Free Queue を実装してみました。
yamasa/lockfree · GitHub
タグ付きポインタ版(queue_tagged.h)のほうはC++03とgcc拡張の範囲で実装していますが、Hazard pointer版(queue_hazard.h)のほうはC++0xの機能をバリバリに使っているので、おそらくgcc4.6でしかコンパイルできないと思います。ちょっと調子にのってしまいました。(笑)

「タグ付きポインタ」と「Hazard pointer」の違い

さて、今回実装したタグ付きポインタ版とHazard pointer版のそれぞれの Lock-Free Queue には、単にC++0x対応の有無だけではない大きな違いがあります。それはキューの要素として扱える型の制限です。
タグ付きポインタ版では、キューの要素は trivially copyable な型でなければなりません。 trivially copyable を簡単に説明すると、memcpy相当の操作だけでコピーできてデストラクタでは何も行なわないような型のことです。詳しくはC++0x仕様書やこちらの記事などを参照してください。
何故 trivially copyable でなければならないかというと、タグ付きポインタ版のほうの dequeue 操作では、valueを読み出そうとしてるNodeが他スレッドによって回収・再利用されたのを「検知」することはできても、回収そのものを「保留させる」ことはできないからです。よって、「data race覚悟でvalueをコピーし、直後のCASで失敗したらやり直す」という手段を取らざるを得ません。そのため、非 trivially copyable なクラスだと、他スレッドが書き換え途中の状態を見てしまい、不正なアドレスにアクセスしてしまったりする事故が起きてしまう可能性があるのです。
一方のHazard pointer版では、 dequeue 操作でのNodeの回収・再利用を「保留させる」ことができます。そのため、同時に複数のスレッドがキューの要素へアクセスすることは無いことが保証できるので、ムーブ代入なども自由に利用することが可能になるのです。
このように、同じようなlock-freeアルゴリズムであっても、メモリ回収に用いる手法の違いによって性質が大きく変わってしまうことがあるのです。

ピーターソンのアルゴリズムとメモリバリア

programming multithreading


とkumagiさんが言っていたので、ちょっとしたコードを張り付けてみます。

これは wikipedia:ピーターソンのアルゴリズム の実装例で、2つのスレッドが排他制御しながら1つのカウンタをカウントアップしていくというものです。正しく排他制御できているなら、最後に "difference = 0" と出力されるはずです。
しかし実際は、このプログラムにはメモリバリアの記述が不足しているため、マルチコアな環境では "difference = 0" とはなりません。
興味深いのは、変数flag0, flag1, turnのそれぞれを別々のキャッシュラインに置くために __attribute__*1 変数が同じキャッシュラインに置かれているかどうかで動作が変わる、一つの例として紹介してみました。

詰めメモリバリア

ところで、前述のコードはどこにメモリバリアが足りていないのでしょうか? マルチコアでも正しく動作させるために、どのような記述を加えればよいか考えてみてください。
名付けて「詰めメモリバリア」。5分で1級の問題です。:-)

*1:aligned(64))) と指定しているのですが、これを外すとdifferenceの値が激減するのです。((手元のCore 2 Duo機では 4528637 → 26 のような感じになりました。

Ajaxページへのパーマリンクを#!なしで実現する

programming webapps

TwitterやFacebookのURLには、なぜ#!が含まれるのか (SEOとAjaxのおいしい関係) - kazuhoのメモ置き場
Ajaxを多用しつつパーマリンクも提供しているサイトのURLは、「#!ほげほげ」のような形式になっていることがよくあります。上の記事に書かれているように、これにはちゃんと理由があるわけなんですが、やっぱり「#!なんてのが含まれるURLは格好悪い」と感じる人も多いようです。
そこで、「#!ほげほげ」なんてURLを使わなくてもAjaxの画面遷移を実現する、Session HistoryというHTML5の機能を紹介します。
Session history demo
ChromeSafariで上のページにアクセスし、地図をドラッグしてみてください。地図を動かすたびにURLが変化しているのに気づくでしょう。そこでブラウザの戻るや進むキーを押すと、地図の移動履歴を辿ることもできます。また、URLをコピペして別ウインドウで開き、同じ場所の地図が表示されることも確認してみてください。
このように、JavaScriptからブラウザの履歴やURLを操作する仕組みがSession Historyです。上のデモページでは?以降だけを変化させましたが、実際はsame origin policyに従っている限りどんなURLにも変化させることが可能です。たとえば、以下の「今ココなう!Webアプリ」でもSession Historyを使用しています。
http://imakoko-iphone.appspot.com/m/
Session Historyを使えば、#!のような格好悪いURLを用いなくてもパーマリンク可能なAjaxページが作れるようになるはずです。Session HistoryはFirefoxでもバージョン4から使えるようになりますし、iOS4やAndroid2.2のブラウザでも利用可能です。
参考: history.pushState、history.replaceState - 素人がプログラミングを勉強していたブログ