データベースを使って何かする際に、ダミーデータが超大量に欲しくなることがあるのでembulkのinput-pluginを作ってみた。githubのリンク 何もない環境からなら $ wget https://bintray.com/artifact/download/embulk/maven/embulk-0.2.1.jar -O embulk.jar …
気が向いたら書くと言ってしまったので忘れないうちに書く。 飢餓状態とは スレッドAが操作xを試みる スレッドBが操作yを試みる スレッドCが操作zを試みる という状況の時に、このアルゴリズムがLock-Freeである場合。すなわちスケジューラがどうスケジュー…
http://www.slideshare.net/kumagi/lock-free-safe?next_slideshow=1とか過去に自分で書いておきながら、その当時の自分の認識が甘かった事もあるのでここに一度書き出しておく。 Lock-Freeは「ロックを使わない事」ではない STMの事をもってしてLock-Freeと…
http://lttng.org/urcu|Userspace RCU という大変クールなプロジェクトがあります。「RCU（リードコピーアップデート）をユーザースペースで行うもの」という事で、そこだけ聞くとなんのこっちゃという感じ。 リードコピーアップデートって何よ リードコピー…
有名な話かと思ったら意外と知られていなかったのでメモ。 FILOを使ってFIFOを作るとも言います。StackでQueue作れてもQueueでStackを作る方法が思いつかないので誰か教えて下さい。もしくはこういう学問があったら紹介して頂けると嬉しいです。簡単な説明と…
ちょっとマニアックなデータ構造を紹介その名もmax queue、使い勝手はほとんどFIFOなqueueと一緒で、enqueue()もdequeue()もO(1)だけどそれに加えて「入ってるデータのうち最大の値」もO(1)の計算量で算出するという代物。 兄弟分で最小の物を返すmin queue…
マルチスレッドなどの環境下で時間経過によって勝手に変化する複数の変数を読みたい場面は多くあります。 しかしCPUは一度に一つしか値を読み書きできないので、簡単には出来ません。何故なら読んでるそばから値が変動してでたらめな値を読むかも知れないか…
この記事はカーネルVM Advent Calendarの12/21日分の記事です。前日分はid:rti7743さんのなのは完売 とある関数の電脳戦 (じょうほうせん とある関数のバトルプログラム) - お前の血は何色だ!! 4です。 Karesansuiって？ ものすごく大雑把に言うとEC2のオー…
@overlastさんのお誘いにより招待講演という形でDSIRNLP勉強会で発表をしました。IRともNLPとも関係のない話ですが、冬のLock-free祭りという題目でお腹いっぱい話せました。 発表資料はこちら 冬のLock free祭り safe View more presentations from Kumazak…
前回ノンブロッキングなSTMに付いて説明したのですが、トランザクション中での読み出しに関してはあまりに適当な説明しかしていなかったです。 そこをもう少しまともに説明しようと思います。 読み出しトランザクション? 複数の箇所の読み出しをatomicに行う…
LevelDBが公開されて少し経ちました。 全体ではLog Structured Merge Treeという物を実装しているようですが詳しいところは知りません。実装を少し読んだのですが内部で使われているSkipListにいくつも思い切った設計がありました。(参考)togetter「LevelDB…
STMはソフトウェアトランザクショナルメモリの略です。 ↓とりあえずwikipedia http://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%95%E3%83%88%E3%82%A6%E3%82%A7%E3%82%A2%E3%83%88%E3%83%A9%E3%83%B3%E3%82%B6%E3%82%AF%E3%82%B7%E3%83%A7%E3%83%8A%E3%83%AB%E…
高速化の為にローカルにキャッシュを設けたい、でもメモリを無駄遣いする気はない、といった場合にLRU(Least Recentry Used)キャッシュを使うのはよくあるパターンです。 pythonでLRUキャッシュをさがすといくつか選択肢が見つかります。 $ pip search lru p…
HibariというErlangによる分散KVSがあるようです http://hibari.github.com/hibari-doc/hibari-app-developer-guide.ja.html 流行りのEventualConsistencyではなく、高い一貫性を守りつつスケールするという代物です。 インストールする http://hibari.githu…
Microsoft Academic Searchみなさん使ってますよね！ Microsoft Academic Researchではありません。 研究する上で知らないわけにはいかない情報をまとめて知ることが出来るお役立ち検索サイトです。 http://academic.research.microsoft.com/ こんなトップペ…
pypyという大変coolなプロジェクトが有ります。「PythonそのものによるPython処理系」という、一見よくわからない取り組みですが驚く事にJITコンパイルを搭載しています。 お陰でC実装のPythonよりも高速に実行できるという驚きの処理系です。動かすには htt…
perfという大変優秀なプロファイラがあります。どう優秀かというと ・gprofと違い、-pgなど付けなくとも既存のバイナリに対して実行できます ・バイナリに対して実行できるという事はあらゆる言語の実行を観察できます sudo apt-get install linux-tools ま…
「スレッド間で共有する変数のアクセス権制御を 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を実現…
