Lock-freeデータ構造で使用されるABA避けカウンタについて

くまぎ @kumagi

boost.atomicは64bit幅の時に上位16bitにカウンタを埋め込むっていうのが賛否あるみたいだけれど、反対意見の人はそのbit数まで必要なメモリを使うんでしょうか。48ビットあれば262テラバイトまで行けるはず…。

やまさ @yamasa

@kumagi 私はカウンタが16bitである点が気になりますね。たとえば3000クロックに1の割合でカウントアップされると仮定すると、16bitカウンタが一周するのに196Mサイクル、2GHzのCPUだと100ms弱です。

やまさ @yamasa

@kumagi 高ロードアベレージ状況なら、コンテキストスイッチしてる間にカウンタが一周してしまっていてもおかしくないわけで、どうも私は気に入りませんね。

くまぎ @kumagi

@yamasa 100msに一巡するにしてもカウンタごとABAる確率ってやっぱり天文学的でしょうしそれが嫌ならハザードポインタなどなどで回避したほうが…

やまさ @yamasa

@kumagi カウンタが一巡してしまう時間が十分ありえるほど短ければ、ABAになる確率はずっと高くなりますよ。

やまさ @yamasa

@kumagi まあ、私はカウンタ付ポインタが嫌いでハザードポインタ萌えなので、そっちを使ったほうが良いというのには大賛成ですｗ

くまぎ @kumagi

@yamasa 時間は相対的なもので、カウンタの一巡に4億カウント必要だろうとすごく速いCPUなら100msで済んでしまうこともあり得るわけで、bit幅と実時間を指標にするとあまりあてにならないかもと思うのです。で、数学的に算出するなら充分天文学的だろうな、と…。

くまぎ @kumagi

@yamasa はい、ハザードポインタ未だ一度もまともな実装作ったことないですがいずれ呼吸のように実装したいです。

やまさ @yamasa

@kumagi いやいや、「実際のマシン上で一巡してしまう可能性があるか」は重要ですよ。4億カウントが100msで一巡してしまうようなCPUなら32bitですら不足してるわけだから64bit必要だ、みたいな感じです。

やまさ @yamasa

@kumagi 実際にカウンタが一巡して同じ値になってしまう確率はいろいろ仮定が必要なので簡単には求まりませんが、単純に65536分の1としても十分大きな値だと思いますが。

くまぎ @kumagi

@yamasa うーん、65536分の1よりは遥かに低そうに思うのです。起こりうるスケジュールを全て列挙した場合、事故るパターンの少なさは凄まじくピンポイントな気がします。

くまぎ @kumagi

@yamasa これは納得しました。OSのプリエンプションは割と実時間的ですしねぃ…。

やまさ @yamasa

@kumagi CASの直前でコンテキストスイッチが発生したとしましょう。コンテキストスイッチから戻ってきたときにカウンタの値がどれだけ進んでいるかは、コンテキストスイッチからの復帰時間の確率分布とカウンタの増加ペースから概算できます。

やまさ @yamasa

@kumagi 復帰時間の確率分布はとりあえず今回は0ms～300msの一様分布としてみましょう。で、カウンタは100msで一周するペースだと仮定します。そうすると、一回のコンテキストスイッチの間に最大３周してしまう可能性があるわけですね。

やまさ @yamasa

@kumagi で、このような仮定をした場合は復帰時のカウンタ値はどの値でも一様の確率になりますから、65536分の1ってことになります。まあ、最初の一様分布って仮定はちょっと無理がありますが、それでも天文学的っていうほど低い確率にはならないと思いますよ。

やまさ @yamasa

@kumagi 数時間から数日間ぶん回して1回起きるか起きないかってくらいの確率でも、用途によっては十分危険と言えるでしょう。

くまぎ @kumagi

@yamasa うーん、300msでカウンタが一周するという感触がちょっと無いです。そんなに早く周りますかねぃ…？だとすると確かに危なそうな気がします。

くまぎ @kumagi

@yamasa 一週間ぶん回して落ちるのなら充分欠陥と呼べると思います。

やまさ @yamasa

@kumagi 単純な掛け算の問題ですよ。 http://t.co/kiI2X4ZA 3000クロックに1回ってのはちょっと高頻度すぎる見積もりですが、3万クロックに1回でも1秒弱です。2GHzのCPUってのはそのくらい速いんですよ。

くまぎ @kumagi

@yamasa OSがフェアなスケジューリングをしてる前提で考えると、200msよりはずっと細かい頻度でコンテキストスイッチが為されるはずですが、それで200msに1回しか自分に廻ってこないとなると結構な数のスレッドですね。スイッチの粒度によっては少なくてもいいのか…。

やまさ @yamasa

@kumagi スケジューリングの単位はちょっと前まで10ms単位ってのが多かったですね。そのときロードアベレージ20なら、200ms戻ってきません。

やまさ @yamasa

@kumagi まあ、ここら辺の議論はよく紛糾するもんですよ。16bitのカウンタってのは相当悲観的な見積もりをしたときに１周するかもしれないぎりぎりのラインですから。16bitでも大丈夫だという人も結構居ます。