lock-free mallocの簡易実装と考察

nakato @nakatwi

Streamflowの論文をざっと読む。確かにこれは速かろうて。少なくとも私には、CASの使用回数をこれより少なくできる気がしない。

nakato @nakatwi

@kumagi 以前教えていただいたメモリアロケータの話です。使ってるlock-freeな操作はLIFOだけみたいです。

くまぎ @kumagi

@nakatwi https://gist.github.com/972375 CAS1回でのLock-free Mallocを試作しました。freeは未テストですが。これだとページをOSに返却できないんですよねぃ…。目的を絞るならまだいいんですが…。

nakato @nakatwi

@kumagi Michael氏のallocatorはSuperBlockをヘッダとボディに分けて、ボディだけはOSに返却するようにしてましたね。うまいなぁと感心したものです。StreamflowはCASはほとんど別スレッドからのfree時だけで、こりゃ速いわ、と。

くまぎ @kumagi

@nakatwi スレッドローカルに返却する場合はCAS使わないんですか…！すごいですね。

nakato @nakatwi

最近のgccは__sync_bool_compare_and_swap なんてのが使えるんか…。便利になったもんだ。

やまさ @yamasa

@kumagi そのコード、アルゴリズムの元ネタとかあります？ いろいろツッコミどころが…

くまぎ @kumagi

@yamasa いや、深いこと考えずに書いたオリジナルです。

やまさ @yamasa

@kumagi allocate()の最初の、 page* next = (*ptr)->next; page* old_ptr = *ptr; if(old_ptr->next != next){continue;} の意図は？

やまさ @yamasa

@kumagi そこのif文は最適化によって消えちゃうので、意味が無いように見えます。

くまぎ @kumagi

@yamasa ぁー。おおう、localなptrに対してこういう一貫性の心配は不要ですね。

やまさ @yamasa

@kumagi で、この実装はget_newpage()でまとまった数のノードを一度に追加するという違いはあるものの、基本的には単純なlock-freeスタックであり、ABA問題に対処できていないようです。

くまぎ @kumagi

@yamasa これは確かに単純な実装ですが、カウンタを回す以外で対処する方法ってあるんでしょうか？

やまさ @yamasa

@kumagi タグ付ポインタを用いた方法は http://j.mp/koivnu の newNode, retireNode で、ハザードポインタを用いたものは http://j.mp/lKFGCi の QueueNodePoolAllocator で実装しています。

くまぎ @kumagi

@yamasa タグ付きポインタはタグが周回する危険を考えるとビット幅が狭い場合軽減しただけでしかなく、ハザードポインタは使う側が気を付けないといけないため、mallocのユーザにハザードポインタの利用を強いずに実現する方法がわかりません。

やまさ @yamasa

@kumagi まあ、これらの実装は実際にベンチマーク取ると意外と性能が出ません。本格的にやるなら、thread_localなキャッシュとglobalなプールとの2段構えのような手法が考えられますね。

くまぎ @kumagi

@yamasa あー、はい。論文での実装は目を通しました。

nakato @nakatwi

昨日の昔読んだTLBの話。2001年のTCP/IPスタックでの話でした。http://findarticles.com/p/articles/mi_qa3751/is_200103/ai_n8944849/pg_18/　PDF版は http://bit.ly/jqvepR

やまさ @yamasa

@kumagi タグは32bit以上あればまず大丈夫といって良いんじゃないですかね。あと、ハザードポインタに限らず、利用者側の協力が必要とされるのは、C++でlock-freeをやろうとする以上仕方ないことかと。

くまぎ @kumagi

@yamasa 32bitのタグということはDCASですか。mallocごときにハザードポインタ要求するのは避けたいので実質そちらになりますかねぃ…。

やまさ @yamasa

@kumagi どうしてもユーザー側にハザードポインタの利用を要求したくないのであれば、free()のところで実際にスタックに戻す前にハザードポインタのスキャンをする手がありますが……二度手間というか、効率が良くないかと。

くまぎ @kumagi

@yamasa 今やっと意味が分かりました。freeしかかってる時に既に他の奴がfreeしちゃうからABAるのだからそこで監視すれば良いってことですね。できそうではありますがTLSをこんな場所で使うのはあんまり気が進みませんね…。

やまさ @yamasa

@kumagi いや、ABAが起こるのはallocate()側です。そこのCASの直前で他のスレッドに割り込まれてallocate()2回→最初にallocate()されたオブジェクトを引数にfree()とされると、ABAになるのがわかるでしょうか。

やまさ @yamasa

@kumagi で、そのABAを回避するには、allocate途中のオブジェクトが別スレッドによって横取りされさらにfreeで戻されるという流れを止めなきゃならないので、free側で監視しようって話なわけです。

くまぎ @kumagi

@yamasa あー、なるほど。確かに。