「スレッド間で共有する変数のアクセス権制御を C++ コンパイラで強制する方法」 http://developer.cybozu.co.jp/kazuho/2009/06/c-c79a.htmlをupgrade_lockを利用して実装してみます。 これはmutexと保護対象オブジェクトを密結合させたオブジェクトを作る…

Boostに以前からread-writeロックは実装されていたようですがバグがあったとかで最近の物ではupgrade_lock, upgrade_to_unique_lockにさし変わっています。ただのロックと比べてパフォーマンスが出やすい上に素性の良い設計だと思うので紹介してみようと思い…

ではLock-free Stackについて図とプログラムを交えながら説明します。C++ではなくCを使います。 これは複数スレッドからロックによる排他無しで共有できるスタックで、外部には node* top; void push(const T*, node** top); bool pop(T*, node** top); を提…

海外の文献を読み漁っていると気づくのですが 2003年を境にこの文脈で使われる言葉の定義が変わります。 ↑2003年ごろまでの構図 ↑現在の構図。*1 non-blocking = obstruction-free という理解でもおおよそ間違いではないとは思いますが 論文を読むに当たって…

この記事は カーネル／VM Advent Calendar http://atnd.org/events/10701 のために書かれました。これまで複数回に渡ってlock-freeデータ構造を紹介して来ましたが そもそもの前提を話していなかったり目的も不明だったりと不備だった点があったので 根元か…

googleにより公開されているgoogle mockが使いやすかったので使い方紹介。http://code.google.com/p/googlemock/ から落としてペペっと入れましょう。使いたいシーンとしては、充分モジュール化されたオブジェクト指向プログラム中で int main(){ A a; B b; …

配列内のデータの平均・分散を算出するには通常以下のようなプログラムを書く double avg = 0.0; for(size_t i=0; i

id:viverさんの作ってるmsgpackライブラリを使っていてのtips 既に実装されている機能などを知らずに僕が再発明してる可能性もあります。

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

trivialだけど同症状で困ってる数少ない方向け C++の有名ライブラリboostには静的リンクするものと動的リンクするものがあります。program_optionsはプログラム起動時に与えられた引数のparseを一手に引き受けて、ヘルプ作成までやってくれる優れものですが…

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によ…

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

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

id:viverさんが素早く対応してくれました。感謝！ http://twitter.com/frsyuki/status/12216710338 http://twitter.com/frsyuki/status/12216785692 githubのdownloadsボタンから、0.32をダウンロードしましょう。 % ./bootstrap % ./configure --disable-ti…

以前から注目していたid:viverさんのライブラリがリリースとのことです 並列イベント駆動I/Oフレームワーク「mpio」リリース http://d.hatena.ne.jp/viver/20100412 マルチスレッド＋ネットワーク なプログラム環境を整える手間が大幅に省けるようです。早速…

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

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

gcc上でcompare and swapをしたいときのメモCentOS5.4上でyumによりインストールされるgccは標準で4.1。 この環境下でcompare and swapを実行する方法は不明。 # yum install gcc44 としてgccのバージョン4.4を使用すれば __sync_bool_compare_and_swap() が…