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

BloomFilterというアルゴリズムがあるらしいけれど、今度暇な時に腰を据えて勉強しよう。 とか思ってる方へ。これは気合いを入れて勉強するほどのアルゴリズムでは無くてとても単純な考え方です。という説明をするために作ったスライドです。 単純で効率的な…

僕が卒業研究で行った内容でした。SkipGraphView more presentations from Kumazaki Hiroki.パフォーマンスが出ていないので後日再試を行います。

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

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

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