CASがあればCAS依存のデータ構造が実装出来る第二弾です。 今度はLockfreeの中でも簡単なデータ構造なスタックです。 前回の疑似コードは微妙だったのでもうちょっとpythonらしい文法に直しました。 import memcache // python-memcached使用 import string …

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

キーバリューストアはフラットな名前空間でキーとバリューの1:1ペアを保持するだけの簡単なデータ構造しか提供しませんが使う側の工夫で好きな構造を作って有効利用できるはずです。そこで擬似コードを書いてみました。memcachedプロトコルの上でFIFOを実現…

厳密にはLinkedListSetです。 Timothy L. Harrisの論文「A Pragmatic Implementation of Non-Blocking Linked-Lists」より。 前回の日記で紹介したものと同一のアルゴリズムを、今度はスライドではなくソースコードとコメントで説明します。LockfreeListによ…