読者です 読者をやめる 読者になる 読者になる

マルチプロセスで使用可能なロックフリーキュー

タイトルの通り、マルチプロセスで使用可能なロックフリーのFIFOキューを実装したので、その簡単な紹介。 作成物 github: ipc-msgque (0.0.4) ロックフリーなFIFOキュー 再入可能 かつ SIGKILLに対して安全*1 C++ 共有メモリ(mmap)を使用 マルチプロセス(and…

複数プロセスで共有しているmutexのロック中にSIGKILLを投げたらどうなるか

C++

結論: デッドロックになってしまう 自動的にロックを解放してくれたりはしないみたい。 以下、試した内容のメモ書き。 環境 $ cat /proc/version Linux version 3.0.0-23-generic (buildd@komainu) (gcc version 4.6.1 (Ubuntu/Linaro 4.6.1-9ubuntu3) ) #38…

簡易スタック型VM(バイトコードインタプリタ)でのフィボナッチ数計算速度

今年はlisp系のプログラミング言語(及びその処理系)を作ってみようと考えていて、かつ(少なくとも)当面の間はスタック型VMを基盤として実装していくことになると思われるので、まずは単純なスタックマシンのバイトコードインタプリタで、どの程度の処理速度…

ビットリバース

割合汎用的な、整数のビットを前後反転する関数を作成してみた。 2の乗数サイズの任意の整数型のビット反転が可能。 // 反転例 bit_reverse(0x0000FFFF) => 0xFFFF0000 // 実装 // バイト単位での変換表 const unsigned char REV_BYTE[]={ 0,128,64,192,32,1…

cc-dict: ハッシュテーブル

ハッシュテーブルを実装してみた。 ・cc-dict-0.0.3 チェイン法を用いたハッシュテーブルで、リンクリスト(チェイン)のノードを割り当てる際に自前のアロケータを使っている点以外は、特に変わったところもないと思う。 ベンチマーク 一応、ベンチマークも取…

std::tr1::unordered_mapのキーの型をconst char*にした場合の挙動

C++

g++(及びその他)のunordered_mapで文字列をキーにしたい場合の注意書き。 unordered_mapのようにconst char*を指定すると、キーが文字列ではなくポインタ(整数値)として解釈されてしまう*1。 以下、その際の挙動の確認用のコード: /** * ファイル名: str_map…

フィールドのポインタから、オブジェクト全体のポインタを取得するためのマクロ

構造体やクラスのインスタンスの特定のフィールドのアドレス(ポインタ)だけ分かっている場合に、そこからオブジェクト全体のポインタを取得したい場合に使うマクロ。 やっていることは単にフィールドのアドレスから、そのフィールドの(クラスor構造体の)先頭…

UNF-0.0.4: サイズ削減

今日は久しぶりにUNF(ユニコード正規化ライブラリ)に手を加えていた。 大きな変更点は、正規化用変換テーブルを実現していたTRIEをDAWGにしたこと。 もともとは正規分解と互換分解用に、内容がほぼ等しいTRIEを別々に持っていたので、それを一つDAWGにして共…

SA-IS: C++版

以前にcommon lispで実装したSA-ISアルゴリズムを、C++でも実装したのでその計時結果など。 ソースコード(github): sais-0.0.1 計時 対象データには以下のサイズのテキストファイル群を使用。 $ ls sa.txt.* -rw-r--r-- 1 user user 10000 2010-12-23 19:25 …

マルチキークイックソートとstd::sortの比較

以前にCommon Lispで実装したマルチキークイックソートをC++で書き直して、STLのstd::sortと速度を比較してみた。 使用データ Wikipediaの記事タイトル約500万行を使用。 データ作成方法などはここを参照。 $ wc -l wiki.title.500 5340378 wiki.title.500 $…

DAWG2(2.5): DAWG構築時のハッシュ値用の領域節約

前回にソート済みファイルからDAWGを構築する際には、個々のノードのハッシュ値をO(1)で(簡単に)算出可能にするために、ノードにハッシュ値用のフィールドを持たせていた。 ;;;; 再掲 ;; DAWGのノード用の構造体 (defstruct node (label 0 :type octet) (sib…

UNF : Unicode正規化ライブラリ

UNFという名前*1で、C++でUnicode正規化を行うライブラリを実装 (ver 0.0.1)。 ついでに、それを利用したRuby拡張ライブラリも作成。C++やRubyで使える、軽くて高速なUnicode正規化ライブラリは、一年以上前から欲しい(作りたい)と思っていたので、作り終え…

ham: 文字NグラムとバイトNグラム

ham(0.0.2)。 Nグラムベースのベイジアンフィルタ。 必要な分だけ実装してサクッと終わらせたかったけど、いくつか試したことが出てきたのでもう少し続ける。 UTF-8以外の文字コード hamは0.0.1ではUTF-8にのみ対応し、その文字Nグラム(N〜Mグラム)*1を素性…

ham: 分類性能評価的なもの

hamの分類性能評価的なもの。 そんなに本格的なことは行わない。 hamでは、基本的に『Practical Common Lisp』にて説明されているスパムフィルタリングの方法(ベイジアンフィルタの一種)をそのまま使わせてもらっている。 このベイジアンフィルタによる分類…

ham: ベイジアンフィルタ

手軽に使える二値分類器*1が急遽必要になったので、ベイジアンフィルタを用いたものを実装。 ham-0.0.1 素性にはNグラムを採用。 対応文字コードはUTF-8のみ。 多分実用程度には高速。 分類性能評価的なことはこれから行う予定。 それらしいデータを用意しな…

Nグラム

Nグラムを取り出すC++のクラスを作成したのでメモ。 UTF-8のみ対応。 /* * ファイル名: ngram.hh */ #ifndef TOKENIZER_NGRAM_HH #define TOKENIZER_NGRAM_HH #include <algorithm> #include <vector> #include <cstring> namespace Tokenizer { class Ngram { public: Ngram(unsigned mi</cstring></vector></algorithm>…

デーモン化

任意のコマンドをデーモンプロセスとして実行するようなコマンドが欲しかったので実装してみた。 /*** * ファイル名: daemonize.c * コンパイル: gcc -o daemonize daemonize * * 概要: * 引数で渡したコマンドをデーモンプロセスとして実行する。 * * 使い…

DAWG(4-3): MPHFライブラリ

前回までで最小完全ハッシュ関数(MPHF)の実装方法(の一つ)が分かったので、C++から使いやすくするためにライブラリ(と云う程の規模ではないけど)としてまとめておいた。 ・mphf-0.0.1実装の大枠は、前回のcommon lisp版のものと同様なので略*1。 ハッシュ関…

DAWG(3): ID付けの方法変更とDoarからの変換

DAWGのキーに一意なIDをマッピングするために、前回考えた方法は、サイズ的に効率的に実装するのが無理そうなことが分かったので、別の方法に変更することに。 IDへのマッピング 方法概要。 DAWGはIDのことを考慮せずに普通に構築する キーのIDは、完全最小…

Micterの単語分割部の高速化を試してみた結果

tkngさんが作成したMicterという単語分割器の分割部を高速化できるような気がしたので試してみた。 そのメモ。試した結果のソース一式はmimicという名前でgithubに保存しておくことにする*1。 結果 まず、結果から*2。 # 分割対象のテキスト(のサイズ) $ ls …

DoubleArray + AC法

AC法(エイホ-コラシック法)というものを知ったのでDoubleArrayで試してみた。 概要 入力テキストから、辞書(= 文字列セット)に登録されている文字列を効率的に検索するための方法らしい*1。 詳細は、Wikipediaの『エイホ-コラシック法』の項目を参照。 自分…

基本となるDoubleArrayの実装

各種アルゴリズムを試す際のベースとなるような(シンプルな)DoubleArrayが欲しくなったので作成した。 構成など 多分、DoubleArrayとしては一番単純な構成*1。 ※ 以下で云う"ノード"は、"ノードのインデックス"の略のような意味合い 静的構築 各キーを改行区…

LOUDS++(8): trie - 検索速度向上

試したいことが出てきたので、少し延長して八回目。 目的 今回の目的は六回目で作成したtrieをベースとし、検索速度を向上させること。 結果 最初に結果から載せる。 入力データや計測方法等は七回目のそれらに準拠。 データサイズ検索所要時間(秒) louds-tr…

LOUDS++(7): trie - 比較

七回目。多分最後。これまで作ってきたものを他のtrie実装と比較する。 比較対象 louds-trie: LOUDS++によるtrieの実装。五回目を参照 louds-trie-tail: LOUDS++によるtrie(TAIL配列/圧縮有)の実装。六回目を参照 doar-0.0.12: DoubleArray(TAIL配列/圧縮有)…

LOUDS++(6): trie改良試作(TAIL配列版)

前回に作成したLOUDS(LOUDS++)を用いたtrieの改良を試みる。 改良案 前回のtrie実装は、まだまだ全然最適化されていないので、改良すべき(or できるであろう)箇所は結構沢山ある。 案として、例えば... bit-vectorの実装方法 ... 他の実装方法の方が効率的(…

LOUDS++(5): trie

四回目まででLOUDS(LOUDS++)の実装方法は分かったので、今回は応用編。 LOUDSを用いてtrieを実装する(というかtrieを実装したソースコードを載せる)。 作るもの 実際に作成するのは以下の二つのコマンド。 mklouds-trie: ソート済みテキストファイルから、LO…

ソート済みファイルをトライ木に見立ててレベル順(幅優先)探索を行う

以下のような内容のファイルがあるとする。 # ファイル名: sample.txt ※ この部分はファイルに含まれない ab abc abef 1 1248 126 13579 これは次のような構造を持つトライ木として考えることができる。※'_ROOT_'は仮想的なスーパールート 今回は、上のよう…

URLエンコード/デコード : C++ : メモリ管理手動

以前に作成したC++によるURLエンコード/デコード関数は、変換先の文字列を格納するためにstd::stringクラスを使っていた。 std::stringを使えば、クラス側がメモリ管理を適切に行ってくれるので楽(バグも生じにくい)なのだが、その分オーバヘッドもある。 UR…

文字列変換C++関数自動生成

仕事柄(かどうかは分からないが)switch分岐を多用したCやC++の文字列(群?)変換関数を書く機会がたまにある。 例えば最近では、Shift_JISの全角文字(カタカナ+記号)を半角文字に変換するCの関数を作成した(このRuby拡張ライブラリの中で使われている関数)。 …

URLエンコード/デコード(比較にC++とclojure追加)

昨日の続き。 比較対象にC++とclojureを追加し、Javaのコードも若干変更した。下の三つが、それぞれのベンチマーク用のコード。(ベンチマーク用データは、前回と同様のものを使用する) 参照: mmap_t /** C++ **/ //////////////////////////// // ファイル名…

Visual C++2005のstd::setとstdext::hash_setの速度

今日試しに使ってみたら、VC++2005のstd::setとstdext::hash_setがやけに遅かった。doarのWindows対応も一通り終ったので、VC++の上記クラスと検索速度を比較してみたのだが、結果は以下のようになった。 doar# 1.875 sec ※ 数値は、32587100要素(325871*100…

DoubleArray動的追加版計時(Mersenne Twister利用)

前に少しDoubleArrayの動的追加時(のx-check関数で空き領域を探す際)に乱数を使えば処理速度を大幅に改善できるのでは、というようなことを書いた。 この方法だとメモリ使用量は結構増える(まだ正確には把握していない)が、確かに処理速度は大きく向上する。…

DoubleArrayプロジェクト

SourceForgeにDoubleArrayのC++ライブラリ用のプロジェクトを作成した。 名前は、DOubleARrayでDoar。 とりあえず現状のソース*1とごく簡単なドキュメントが載せてある。まだまだ安定版には遠いけど...。 10月中には、主要な開発は終わらせたい...。 *1:動的…

高速行読込クラス

ベンチマークを取る時には、対象となる部分以外に掛かる処理時間を極力抑えたい。 標準のファイル入力クラスであるifstreamは、結構便利でそこそこ高速ではあるのだが、大量の行を読み込む場合、少なくはないオーバヘッドが出てしまう。 なので、今回は、ベ…

DoubleArray: ソート済みデータからの構築

近況 ここしばらくは、ひたすらC++でDoubleArrayの実装に取り組んでいる。もともとは、シンプルなものを一つ作って終わりにしようかと考えていたのだが、検索・挿入効率とかメモリ使用量(ファイルサイズ)とか大きい(千万程度)のキーセットに対して効率的な実…

JSONデコード: C++: 高速化準備(専用のallocator作成)

C++

以前作成したC++のJSONパーサの高速化試行。 C++のデフォルトのnewは、小さいサイズのメモリを大量に割り当てるのが遅いということは有名(?)なので、JSONパーサ用に、専用のallocatorクラスを作成することにした。今回作成したallocatorクラスのテンプレート…

JSONデコード: C++: 高速化

以前作成したC++のJSONパーサをもっと速くできないかと思い、いろいろ試してみた。結構速くなったので、以前のものとの比較、変更点概要、ソースコードを載せておくことにする。 以前のJSONパーサとの比較 以前のJSONパーサや比較条件などに関しては、以前の…

JSONデコード: C++

数日前にcommon lispでJSONパーサを実装したが、そのC++版を書いてみた。実装的には、common lisp版とほとんど変わらないが、サロゲート・ペアに対応したり、エンコード関数も(おまけ程度)に作成したり、と若干以前よりは高機能になっている。ソースコードは…

mmap用のクラス

mmapは便利なので(C++を使うときは)割合よく利用する。 ただ、初期化が面倒で毎回リファレンスなどを調べるはめになるので、クラス(struct)としてまとめておくことにする。 ↓ // mmap_t.h #include <sys/stat.h> #include <sys/mman.h> #include <fcntl.h> #include <unistd.h> struct mmap_t{ mmap_t(co</unistd.h></fcntl.h></sys/mman.h></sys/stat.h>…

リストの逆転

最近は少し忙しいので、気分転換を兼ねて簡単な関数を実装する。リストの破壊的なリバース。 以下、ソース。 参照: nlet (defun list-reverse! (lst) (nlet self ((lst lst) head) (if (endp lst) head (self #1=(cdr lst) (progn (setf #1# head) lst))))) …