引き続きCASベースのLock-Free Listアルゴリズムの実装。
論文は"Lock-Free Linked Lists and Skip Lists" Mikhail Fomitchev, Eric Ruppert。
先日の
"A Pragmatic Implementation of Non-Blocking Linked-Lists"と比較すると:
先日の実装は、競合するとリストの先頭まで戻るが、本日の実装は、一つ手前までしか戻らないので、総合的にみて効率がよい(と論文には書かれている)。
というわけで、Lock-Freeだからといって一概に効率的なわけではない。
因みにLazy Listは競合すると他のスレッドの動作が止まるが、Lockの粒度が小さいので全体に与える影響が小さく、一概に非効率的とも言えない。
