10周年のSPコンテンツ!
3
Nobuyuki Kubota @nobu_k
ABA問題が起こらないlock-freeリストのポータブルなC++実装が欲しいです。今だったらどうやって作るのが現実的かな。boostのatomicなものに依存したい・・・。
汎用kumAGI @kumagi
@nobu_k lock free listですか!順序関係を強制しない物でしょうか?STL的に使いたいと言い出すと双方向リストになると思うんですが。どのようなセマンティクスが欲しいか詳しく聞きたいです。
Nobuyuki Kubota @nobu_k
@kumagi FIFOであればOKな感じです!入れたものが順不同に帰ってきてもOKなレベルw
汎用kumAGI @kumagi
@nobu_k それでもfifoじゃなくてlistってことはerase(const T&)やinsert(const iter&)が欲しいのでしょうか?
Nobuyuki Kubota @nobu_k
@kumagi いやー単にFIFOなキューが欲しかっただけなんですが、lock-freeなキューを実装するなら中身はリストになるなーという思い込みからリストって書いただけですw
汎用kumAGI @kumagi
lock-free queueは欲しい状況に応じてカスタムパターンが数百どころのオーダーじゃないので、そこが欲しいパターンに合わせてカスタムできたら最強ですね。
汎用kumAGI @kumagi
@nobu_k ぐぬぬ…。普通のqueueの実装として知ってるのはamino, intel tbb, boost::lockfreeですね。速度比較などはしたことないですが、boostのやつがtbbより速いという記述を見かけたりしました。
Nobuyuki Kubota @nobu_k
@kumagi おおboostやりますなー。あんまり外部ライブラリに依存できない感じなので、ちょっと実装を参考にしてみます!
汎用kumAGI @kumagi
http://twitter.com/#!/kumagi_bot/status/23010522366476289 以前呟いたこれを見返して、あぁプラガブルにするの無理そう。と思い直す。実際実装無理なパターンありそう。
汎用kumAGI @kumagi
ABA避けのあるqueueって、queueならカウンタ付きポインタにするよりはhazard ptrにして利用中のものが再利用されないように回避するほうが安心で確実。
Kota Uenishi (๑•̀ㅂ•́)و✧ @kuenishi
今こそロックフリーの技術を理解すべきときだと思ったけどErlangでも別にいいか
汎用kumAGI @kumagi
@kuenishi 何を学んだらロックフリーの技術を学んだ事になるんでしょうか…。art of mppの6章の「ロックフリー普遍構造」が未読なのですが…orz
Nobuyuki Kubota @nobu_k
@kumagi ありすぎるwwww>未読
Kota Uenishi (๑•̀ㅂ•́)و✧ @kuenishi
まあしかし、多少マルチスレッドにしても落ちないコードが書けるようになっただけでも成長だな。
Kota Uenishi (๑•̀ㅂ•́)و✧ @kuenishi
.@kumagi ロックフリーの世界をよく理解していないのでアレなんですが、pthread_mutex_tを使わずにマルチスレッドで動作するプログラムが書けるようになったらっていうくらいを想像しています。
汎用kumAGI @kumagi
mutexで排他していたカウンタに対しアトミック加算命令を使うように修正したからlock freeになった、というのはよく有る勘違いで、スケーラビリティの観点に於いてはほとんど差が無いらしい。CPUのキャッシュコヒーレンスの仕組みを知ってれば大体見当付きますよね。
Norihisa Fujita, ぽん @fjnli
@kumagi mutexによる排他制御のコストってどれぐらいなんでしょうか。
汎用kumAGI @kumagi
あ、確かにロックフリーにはなったけどスケーラビリティは一切伸びない、のだな。カウンタをスケーラブルにするには結構な工夫が必要で知ってる限りはSNZI以外はblocking
汎用kumAGI @kumagi
@fjnli lockはlock-prefix付きのxchgで獲得値が0になれば良いはずです。lock-prefixつき命令は前後にメモリバリアをはる事になり、競争が少ない場合はコストの半分ほどがメモリバリアに起因するようです。競争が有る場合はコア間の闘争なのでよくわかりません。
Norihisa Fujita, ぽん @fjnli
@kumagi mutexの場合、待機しているスレッドを叩き起すためにカーネルが介入すると思うのですが、そのあたりのコストが気になります。
汎用kumAGI @kumagi
@fjnli あー、僕が話してたのはuser spaceなmutexですね。Solarisの場合は待機に入った順にqueueにつっこんで、ロック開放時はそこからdequeするだけでlock xchgの発行すらさせないので競争時のコストはそんなに無さそうです。
Norihisa Fujita, ぽん @fjnli
@kumagi なるほど。user spaceで完結する(futexとか?)ならば、差はなさそうです。
汎用kumAGI @kumagi
@fjnli カーネルが介入した場合はキャッシュが汚れる事のほうが深刻な問題で、IPCが回復するのに数百万クロック要するとかそんな噂を聞いたことがあります。
Norihisa Fujita, ぽん @fjnli
@kumagi ほええ…。cacheなにそれおいしいのなコード書いててすいません…
汎用kumAGI @kumagi
cache awareって一体どうすればいいんだろうな…。cacheline awareがギリギリだろう。FlexSCのような新兵器以外で何か手法があるのでしょうか…。
残りを読む(21)

コメント

汎用kumAGI @kumagi 2011年2月17日
ちょっとデコレーション
ログインして広告を非表示にする
ログインして広告を非表示にする