lockに魅了された人たち

Nobuyuki Kubota @nobu_k

ABA問題が起こらないlock-freeリストのポータブルなC++実装が欲しいです。今だったらどうやって作るのが現実的かな。boostのatomicなものに依存したい・・・。

くまぎ @kumagi

@nobu_k lock free listですか！順序関係を強制しない物でしょうか？STL的に使いたいと言い出すと双方向リストになると思うんですが。どのようなセマンティクスが欲しいか詳しく聞きたいです。

Nobuyuki Kubota @nobu_k

@kumagi FIFOであればOKな感じです！入れたものが順不同に帰ってきてもOKなレベルｗ

くまぎ @kumagi

@nobu_k それでもfifoじゃなくてlistってことはerase(const T&)やinsert(const iter&)が欲しいのでしょうか？

Nobuyuki Kubota @nobu_k

@kumagi いやー単にFIFOなキューが欲しかっただけなんですが、lock-freeなキューを実装するなら中身はリストになるなーという思い込みからリストって書いただけですｗ

くまぎ @kumagi

lock-free queueは欲しい状況に応じてカスタムパターンが数百どころのオーダーじゃないので、そこが欲しいパターンに合わせてカスタムできたら最強ですね。

くまぎ @kumagi

@nobu_k ぐぬぬ…。普通のqueueの実装として知ってるのはamino, intel tbb, boost::lockfreeですね。速度比較などはしたことないですが、boostのやつがtbbより速いという記述を見かけたりしました。

Nobuyuki Kubota @nobu_k

@kumagi おおboostやりますなー。あんまり外部ライブラリに依存できない感じなので、ちょっと実装を参考にしてみます！

くまぎ @kumagi

http://twitter.com/#!/kumagi_bot/status/23010522366476289 以前呟いたこれを見返して、あぁプラガブルにするの無理そう。と思い直す。実際実装無理なパターンありそう。

くまぎ @kumagi

ABA避けのあるqueueって、queueならカウンタ付きポインタにするよりはhazard ptrにして利用中のものが再利用されないように回避するほうが安心で確実。

kuenishi @kuenishi

今こそロックフリーの技術を理解すべきときだと思ったけどErlangでも別にいいか

くまぎ @kumagi

@kuenishi 何を学んだらロックフリーの技術を学んだ事になるんでしょうか…。art of mppの6章の「ロックフリー普遍構造」が未読なのですが…orz

Nobuyuki Kubota @nobu_k

@kumagi ありすぎるｗｗｗｗ＞未読

kuenishi @kuenishi

まあしかし、多少マルチスレッドにしても落ちないコードが書けるようになっただけでも成長だな。

kuenishi @kuenishi

.@kumagi ロックフリーの世界をよく理解していないのでアレなんですが、pthread_mutex_tを使わずにマルチスレッドで動作するプログラムが書けるようになったらっていうくらいを想像しています。

くまぎ @kumagi

mutexで排他していたカウンタに対しアトミック加算命令を使うように修正したからlock freeになった、というのはよく有る勘違いで、スケーラビリティの観点に於いてはほとんど差が無いらしい。CPUのキャッシュコヒーレンスの仕組みを知ってれば大体見当付きますよね。

Norihisa Fujita, ぽん @fjnli

@kumagi mutexによる排他制御のコストってどれぐらいなんでしょうか。

くまぎ @kumagi

あ、確かにロックフリーにはなったけどスケーラビリティは一切伸びない、のだな。カウンタをスケーラブルにするには結構な工夫が必要で知ってる限りはSNZI以外はblocking

くまぎ @kumagi

@fjnli lockはlock-prefix付きのxchgで獲得値が0になれば良いはずです。lock-prefixつき命令は前後にメモリバリアをはる事になり、競争が少ない場合はコストの半分ほどがメモリバリアに起因するようです。競争が有る場合はコア間の闘争なのでよくわかりません。

Norihisa Fujita, ぽん @fjnli

@kumagi mutexの場合、待機しているスレッドを叩き起すためにカーネルが介入すると思うのですが、そのあたりのコストが気になります。

くまぎ @kumagi

@fjnli あー、僕が話してたのはuser spaceなmutexですね。Solarisの場合は待機に入った順にqueueにつっこんで、ロック開放時はそこからdequeするだけでlock xchgの発行すらさせないので競争時のコストはそんなに無さそうです。

Norihisa Fujita, ぽん @fjnli

@kumagi なるほど。user spaceで完結する(futexとか?)ならば、差はなさそうです。

くまぎ @kumagi

@fjnli カーネルが介入した場合はキャッシュが汚れる事のほうが深刻な問題で、IPCが回復するのに数百万クロック要するとかそんな噂を聞いたことがあります。

Norihisa Fujita, ぽん @fjnli

@kumagi ほええ…。cacheなにそれおいしいのなコード書いててすいません…

くまぎ @kumagi

cache awareって一体どうすればいいんだろうな…。cacheline awareがギリギリだろう。FlexSCのような新兵器以外で何か手法があるのでしょうか…。