Hatena::ブログ(Diary)

くまメモ このページをアンテナに追加 RSSフィード Twitter

2010-04-25

LockfreeListについて

| 01:41 |

ロック無しで複数のスレッドから同時に操作できるLockfreeListについて資料を作りました。

この考え方をベースにLockfreeHashmapやLockfreeSkiplistなどが発展していくため、大事なアルゴリズムです。

パラパラめくるだけでも流れがわかりやすいよう配慮したつもりですがいかがでしょうか?

ABA問題やGCに付いても少し言及しています。

Cでのソースコードは完成し次第追記します。

interdbinterdb 2010/04/29 14:13 こんにちは、
私と似たようなことに興味をもっていらっしゃいますね。
私のhatenaとそこから辿れるWEBサイトに概要とCソースがありますので、興味があればどうぞ。

ちなみにmemcachedの改造もやってみましたが、hashのロック細粒化では性能はあがらなかったですね。フリーリストはLRUのために双方向リストにしないとならないのでLock-freeはあきらめました(アルゴリズム自体は存在するけど、それでパフォーマンスがあがるとも思えないので)。

kumagikumagi 2010/05/02 19:05 初めまして。『「データ構造とアルゴリズム」再入門』は興味深く読ませて頂いてます。

memcachedの改造まで行うとは流石ですね。ロック細粒化については是非CPUコア数を増減させて追試を行ってみたいところです。

改造と言えば
http://jdybnis.github.com/memcached/
にて、skip listによるmemcachedの改造が行われており、範囲検索を可能にした割にはなかなかパフォーマンスが出ており感心しました。こちらもどのようにしてLRUを実現した(orするつもり)なのかは知りませんが。

また、このLockfreeListを元にしたオープンアドレスハッシュ(センチネルノードを挟む事でresizeをLockfree化するもの)の仕組みにかなり感激したのですが、パフォーマンスの考察についてもう少しサイト上で掘り下げて頂けると感無量です。