ロックを使わず共有できるハッシュテーブル http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.100.7132&rep=rep1&type=pdf の論文のスライド資料を作りました。Hashmapは大きく分けてオープンアドレッシングとクローズドアドレッシングの2種類に分…

ロック無しで複数のスレッドから同時に操作できるLockfreeListについて資料を作りました。 この考え方をベースにLockfreeHashmapやLockfreeSkiplistなどが発展していくため、大事なアルゴリズムです。 パラパラめくるだけでも流れがわかりやすいよう配慮した…

コストが定義できるアイテム群に対して、最小コストのアイテムの取り出しと、任意のコストのアイテム挿入がそれぞれO(log n)という特徴を持ったデータ構造のLockfree版です。今回はソースコードもスライド中に書き込みました。Lockfree Priority QueueView m…

mutexを使わなくても共有できるデータ構造について。 Compare and Setという不可分な操作を直列化の拠り所として共有するデータ構造です。コア数が増えて来たときに高い並列性を期待出来るのではないかと思われます。