-
- いいね！0
SKS rep
@repeatedly
. @kumagi_bot @nobu_k ってことは今のconccurent向けのデータ構造を提供しているライブラリで木の実装って全部STMでおすか？
2011-01-23 22:52:29
Nobuyuki Kubota
@nobu_k
@repeatedly STM以前に、そもそも広く使われてる並列木の実装あんのかな・・・。大体順序がいらないからhash使ってたりして、純粋に木を遣ってるやつはあんまりなさそうな気がするけどどうなんでしょう。俺も知りたい。skip listなやつは結構あるけど。
2011-01-23 22:54:18
kumagi
@kumagi_bot
@nobu_k 研究レベルだとSTMでもHTMでもすぐにこれみよがしに赤黒木のスケーラビリティを持ち出してくるんですけどね…。実用レベルのものは見たことないです。haskellのようにSTMが浸透してきている場所ならあるかもしれません。
2011-01-23 22:59:18
Hideyuki Tanaka
@tanakh
Haskellがいけてるのは、型システムで副作用のある動作を排除できること。Clojureがいけてるのは、共有リソースに対してトランザくショナルアクセスしか提供していないところ。
2011-01-23 23:02:41
SKS rep
@repeatedly
しかしSingle Giant LockでScaleしない状態ってかなりシビアだな．細かな粒度のLockも限界があるのは確かというか作りたいアプリケーションによっては厳しい…
2011-01-23 22:54:53
kumagi
@kumagi_bot
@repeatedly 今のところ細粒度ロックの木は見たことないです。何で木の実装が無理かっていう話はケンブリッジ大学の博士論文みたいなところで語ってた気がします。javaのutil.concurrentパッケージにもskip listしかないし…。
2011-01-23 22:57:18
kumagi
@kumagi_bot
@repeatedly Single Giant Lockってスケールしない共有方法のお手本みたいな例なのでシビアでもなんでもないと思います。
2011-01-23 22:57:50
Nobuyuki Kubota
@nobu_k
@repeatedly むしろそれでスケールする状況がない気がする。スケールしなくても良いところで荒くロック取ってるんじゃないのかな。俺はそう。かといって細かくロック取り始めるとオワタ感がすごいことに。ずいむー。だったらSTMでｒｙってなっちゃう人が俺。
2011-01-23 23:00:01
SKS rep
@repeatedly
. @nobu_k @kumagi_bot ああいや，アプリ毎に分割してイベント的にやればそれなりに動くんじゃないかなぁと勝手に思ってました．CRuby with EventMachineとかNode.js的な．
2011-01-23 23:02:30
kumagi
@kumagi_bot
実際赤黒木のSTM実装が欲しい場面って"パフォーマンスは二の次"かつ"メモリは節約したい"かつ"スケールして欲しい"ぐらいしか想像がつかないのでニッチな分野だと思う。
2011-01-23 23:02:53
kumagi
@kumagi_bot
@repeatedly 早い話が「他に木の探索してるスレッドが居る最中で木を回転させたら探索空間をかってに変更しちゃって見つかるものも見つからなくなるじゃんね。回転させないように各節にカウンタ付ける？ご冗談を」みたいな内容でした。
2011-01-23 23:14:58
kumagi
@kumagi_bot
@repeatedly 木の回転後も探索空間が保証されるようにポインタをマーキングしてどうのこうの…ってのを一時期考えてたのですが、保証の為にかかるコストが凄まじいことになるのでダメそうだなぁと捨てました
2011-01-23 23:15:59
SKS rep
@repeatedly
なるほど．粒度を大きくすれば回転のための保証コストは下がるけどパフォーマンスが出ない．粒度を小さくすると今度は回転のための保証コストが馬鹿にならなくなるのか…
2011-01-23 23:23:10
kumagi
@kumagi_bot
Lock freeなtreeといえばD言語でも有名なあのandrei先生による論文があったな。要約すると「めったに書き換えない二分木ならRCUで実装すれば最強じゃね？GC無しだと寿命管理の為にカウンタ付けることになってスケールしないだろうけど変に苦労するよりはずっと時間の節約だ」
2011-01-23 23:31:45