厳密には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() が…

memcachedプロトコルは典型的なkey-value storeプロトコルのデファクトスタンダードになりつつあります。 いろんな言語から簡単に呼び出せる環境が整備されており、大変便利です。 memcachedプロトコルの中で基本として使われるgetですが 複数のkeyを指定す…

RAMCloudというストレージシステムについて調べてみた 公式wiki http://fiz.stanford.edu:8081/display/ramcloud/Home 公式サイト http://www.stanford.edu/~ouster/cgi-bin/projects.php ソース[英語] http://www.stanford.edu/~ouster/cgi-bin/papers/ramc…

素のインストール済みのCentOS 5.3にmemcachedをインストールした場合そのままではサーバの外からmemcachedへ接続できない。CentOSではデフォルトでiptablesというファイヤウォールが作動しているためだ # /etc/init.d/iptablss stop してやればファイヤウォ…

正当に性能評価をするのであればlibmemcachedのmemslapという物がお勧めらしいがlibmemcachedのインストールよりも簡単そうな物が見付かったのでそちらから先に試してみる。 http://www.interdb.jp/techinfo/mcb/ ここで公開されているmcbという物。 mcb.cを…

memcachedはDanga Interactive社とやらで作られた外国産のソフトだけど repcachedはYASUI Masanobu氏とHIROSE Masaaki氏がmemcachedにレプリケーション機能を加えて拡張した物。 現時点での最新memcachedはバージョン1.4.1、最新repcached2.2はmemcachedの1.…

CentOS5.3にmemcachedを入れたメモ△必要なもの libevent libevent-devel2つともyumにてインストール。 エラーメッセージにlibevent-develに言及していなくて気づくのに時間がかかった。 ソースコードから入れていれば困らなかったんだろう。 $ yum install l…