ビットリバース

C++ utility

割合汎用的な、整数のビットを前後反転する関数を作成してみた。
2の乗数サイズの任意の整数型のビット反転が可能。

// 反転例
bit_reverse(0x0000FFFF) => 0xFFFF0000

// 実装

// バイト単位での変換表
const unsigned char REV_BYTE[]={
  0,128,64,192,32,160,96,224,16,144, 80,208,48,176,112,240,8,136,72,200,
  40,168,104,232,24,152,88,216,56,184,120,248,4,132,68,196,36,164,100,228,
  20,148,84,212,52,180,116,244,12,140,76,204,44,172,108,236,28,156,92,220,
  60,188,124,252,2,130,66,194,34,162,98,226,18,146,82,210,50,178,114,242,
  10,138,74,202,42,170,106,234,26,154,90,218,58,186,122,250,6,134,70,198,
  38,166,102,230,22,150,86,214,54,182,118,246,14,142,78,206,46,174,110,238,
  30,158,94,222,62,190,126,254,1,129,65,193,33,161,97,225,17,145,81,209,
  49,177,113,241,9,137,73,201,41,169,105,233,25,153,89,217,57,185,121,249,
  5,133,69,197,37,165,101,229,21,149,85,213,53,181,117,245,13,141,77,205,
  45,173,109,237,29,157,93,221,61,189,125,253,3,131,67,195,35,163,99,227,
  19,147,83,211,51,179,115,243,11,139,75,203,43,171,107,235,27,155,91,219,
  59,187,123,251,7,135,71,199,39,167,103,231,23,151,87,215,55,183,119,247,
  15,143,79,207,47,175,111,239,31,159,95,223,63,191,127,255};

// リバースクラス
template <int BYTE_SIZE> 
struct bit_rev {
  static const int HALF_SIZE = BYTE_SIZE/2;
  static const int HALF_BITS = HALF_SIZE*8;
  
  // BYTE_SIZEが1以外なら、上位ビットと下位ビットに再帰的に処理を適用した後に、二つを入れ替える
  template <typename T>
  static T reverse(T n) {
    return 
      (bit_rev<HALF_SIZE>::reverse(n) << HALF_BITS) | 
      (bit_rev<HALF_SIZE>::reverse(n>>HALF_BITS));
  }  
};

// BYTE_SIZEが1ならテーブルを参照して、バイトを変換する
template <> struct bit_rev<1> {
  template <typename T>
  static T reverse(T n) {
    return REV_BYTE[n&0xFF];
  }
};

// インターフェース関数
template <typename T>
T bit_reverse(T n) {
  return bit_rev<sizeof(T)>::reverse(n);
}

サンプルコマンド:

/**
 * ファイル名: rev.cc
 * コンパイル: g++ -o rev rev.cc
 */
#include <iostream>

/*
 bit_reverse関数定義
 */

int main() {
  unsigned char n08 = 0x0F;
  unsigned short n16 = 0x009F;
  unsigned int n32 = 0x0000699F;
  unsigned long long n64 = 0x00000000666699FF;
  
  std::cout.setf(std::ios::hex, std::ios::basefield);
  std::cout.setf( std::ios::showbase );

  std::cout << "n08: " << (long long)n08 << " => " << (long long)bit_reverse(n08) << std::endl;
  std::cout << "n16: " << (long long)n16 << " => " << (long long)bit_reverse(n16) << std::endl;
  std::cout << "n32: " << (long long)n32 << " => " << (long long)bit_reverse(n32) << std::endl;
  std::cout << "n64: " << (long long)n64 << " => " << (long long)bit_reverse(n64) << std::endl;
  return 0;
}

実行結果:

$ ./rev
n08: 0xf => 0xf0
n16: 0x9f => 0xf900
n32: 0x699f => 0xf9960000
n64: 0x666699ff => 0xff99666600000000

自分の環境で軽く試した感じでは、ビット演算のみを使用して手書きで最適化したものと同等以上の速度が出ていた。

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

C++ library speed size

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

ベンチマーク

一応、ベンチマークも取ったので載せておく。
比較対象はg++のunordered_mapとGoogleのsparse_hash_map及びdense_hash_map。
ベンチマークプログラムにはHash Table Benchmarksに記載のものを使用させてもらった*1。
※ 実行環境は Ubuntu-11.11-64bit / Intel(R) Core(TM) i7 CPU L 620 @ 2.00GHz。

このベンチマーク結果を見る限りは、特別性能が悪い、ということはなさそう*2。

*1:ただし以下の追加・修正を施した。
　1: 検索処理時間の計測の追加
　2: もともとは文字列のベンチマークではキーの型const char*が使用されていたのをstd::stringに変更(関連)
　3: 処理時間にキー配列を生成する時間も含まれていたので、キー配列は最初にまとめて生成しておき、その後から計時を開始するように修正

*2:ベンチマークデータが結構恣意的(連番 or 乱数)なので、必ずしも実データで同様の性能がでるかは分からないけど・・・

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

C++

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

/**
 * ファイル名: str_map.cc
 * コンパイル: g++ -o str_map str_map.cc
 * gcc-4.6.1
 */
#include <string>
#include <cstring>
#include <tr1/unordered_map>
#include <iostream>

int main() {
  // ハッシュマップ作成
  std::tr1::unordered_map<const char*, int> cstr_map;  // const char*用
  std::tr1::unordered_map<std::string, int> str_map;   // std::string用
  
  // キーを用意
  char key1[] = "abc";
  char* key2 = new char[4];
  strcpy(key2, "abc");
  
  // キーの値とアドレスを出力
  std::cout << std::endl << "--" << std::endl;
  std::cout << "key1: '" << key1 << "' (addr: " << (long)(key1) << ")" << std::endl;
  std::cout << "key2: '" << key2 << "' (addr: " << (long)(key2) << ")" << std::endl;
  
  // key1を要素挿入
  cstr_map[key1] = 10;
  str_map[key1] = 10;

  // key1とkey2を検索
  std::cout << std::endl << "--" << std::endl;
  std::cout << "cstr_map: key1=" << cstr_map[key1] << ", key2=" << cstr_map[key2] << std::endl;
  std::cout << " str_map: key1=" << str_map[key1] << ", key2=" << str_map[key2] << std::endl;

  // key1の値を変えてみる
  key1[1] = '2';  // key1 = "a2c"

  // key1を検索
  std::cout << std::endl << "--" << std::endl;
  std::cout << "key1: '" << key1 << "' (addr: " << (long)(key1) << ")" << std::endl;
  std::cout << "cstr_map: key1=" << cstr_map[key1] << std::endl;
  std::cout << " str_map: key1=" << str_map[key1] << std::endl;    
  return 0;
}

実行結果:

--
key1: 'abc' (addr: 140736322707456)  # key1とkey2は同じ文字列だけど、アドレスは異なる
key2: 'abc' (addr: 30732528)

--
cstr_map: key1=10, key2=0   # key1のみヒット
 str_map: key1=10, key2=10  # key1とkey2の両方にヒット

--
key1: 'a2c' (addr: 140736035469872)
cstr_map: key1=10           # ヒット(ポインタ値が同じなため)
 str_map: key1=0            # ヒットしない(文字列が変わっているため)

分かってみれば、これはこれで自然な動作なので特に違和感もないけど、最近はC++がご無沙汰だったためか(文字列ではなくポインタ値として扱われていることに)すぐに気づかずに少しはまってしまった。

*1:もちろん const char* 用に自前で定義したハッシュ関数と比較関数をテンプレート引数に渡してあげれば特に問題はない(はず)

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

C++ utility

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

// type.fieldが、typeの先頭の何バイト目に配置されているかを求める
#define field_offset(type, field) \
  ((char*)&(((type*)NULL)->field) - (char*)NULL)

// type.filedのアドレス(field_ptr)から、fieldのオフセット分マイナスし、typeのアドレスを求める
#define obj_ptr(type, field, field_ptr) \
  ((type*)((char*)field_ptr - field_offset(type, field)))

メモリアロケータを自作する際に、割当メモリ領域にタグ付けするのに利用できそうだと思い作成。

/* main.cc */
#include <iostream>

// タグ付きメモリチャンク
struct chunk {
  struct {            // タグ情報:
    const char* type; // - 型名
    int size;         // - サイズ
  } tag;
  void* buf;
};

// メモリ割り当て
inline void* mem_allocate(const char* type, int size) {
  chunk* c = (chunk*)new char[sizeof(chunk::tag)+size];

  // タグ情報を保存する
  c->tag.type = type;
  c->tag.size = size;

  std::cout << "[" << c->tag.type << "] allocate: " << c->tag.size << " bytes" << std::endl;

  // 割り当てアドレスを返す
  return &c->buf;
}

// メモリ解放
void mem_free(void* p) {
  // 解放するアドレス(chunk::buf)から、タグ情報(chunk)を取得する
  chunk* c = obj_ptr(chunk, buf, p);
  std::cout << "[" << c->tag.type << "] free: " << c->tag.size << " bytes" << std::endl;
  delete c;
}

struct abc {
  int a;
  char b;
  long c;
};

// main関数
int main() {
  void* ptrs[3];

  std::cout << "# allocate:" << std::endl;
  ptrs[0] = new (mem_allocate("int", sizeof(int))) int;
  ptrs[1] = new (mem_allocate("pointer", sizeof(void*))) void*;
  ptrs[2] = new (mem_allocate("struct", sizeof(abc))) abc;
  
  std::cout << std::endl;
  std::cout << "# free:" << std::endl;
  for(int i=2; i >=0; i--)
    mem_free(ptrs[i]);

  return 0;
}

$ g++ -o main main.cc
$ ./main
# allocate:
[int] allocate: 4 bytes
[pointer] allocate: 8 bytes
[struct] allocate: 16 bytes

# free:
[struct] free: 16 bytes
[pointer] free: 8 bytes
[int] free: 4 bytes

Sanmoku(0.0.5): 原型や読みの情報取得に対応

Java library

Sanmoku(0.0.4): 辞書データサイズ縮小のコメントにて要望があったのでSanmokuを形態素の原型や読みの情報取得に対応させてみた。
Sanmoku本体のインターフェースは以前の同様*1で、原型・読み・発音の取得を行うためのFeatureExクラス(sanmoku-feature-ex-x.x.x.jar)を新しく追加した。

使用例:

import net.reduls.sanmoku.Tagger;
import net.reduls.sanmoku.Morpheme;
import net.reduls.sanmoku.FeatureEx; // 追加

for(Morpheme m : Tagger.parse("...")) {  // 形態素解析
  FeatureEx fe = new FeatureEx(m);       // 解析結果の形態素インスタンスから、追加の素性データを取得

  // 結果表示
  System.out.println(m.surface+"\t"+m.feature+","+fe.baseform+","+fe.reading+","+fe.pronunciation);
}

$ export CLASSPATH=sanmoku-0.0.5.jar:sanmoku-feature-ex-0.0.1.jar
$ echo '招待制でリリースしました' | java net.reduls.sanmoku.bin.SanmokuFeatureEx
招待	名詞,サ変接続,*,*,*,*,招待,ショウタイ,ショータイ
制	名詞,接尾,一般,*,*,*,制,セイ,セイ
で	助詞,格助詞,一般,*,*,*,で,デ,デ
リリース	名詞,サ変接続,*,*,*,*,リリース,リリース,リリース
し	動詞,自立,*,*,サ変・スル,連用形,する,シ,シ
まし	助動詞,*,*,*,特殊・マス,連用形,ます,マシ,マシ
た	助動詞,*,*,*,特殊・タ,基本形,た,タ,タ
EOS

比較

以前の表にSanmoku-0.0.5(+ FeatureEx-0.0.1)を追加したもの。

　 辞書データサイズ(IPADIC) 最小所要メモリ(-Xmx) 起動(≒辞書ロード)時間*2 10MBテキストの解析時間
Igo-0.4.3 40MB 73MB 0.058秒 2.729秒
Gomoku-0.0.4 8.2MB 23MB 0.371秒 2.621秒
Sanmoku-0.0.4 4.8MB 2MB 0.057秒 5.807秒
Sanmoku-0.0.5(+ FeatureEx-0.0.1) 10MB 11MB 0.098秒 6.814秒

読み等の情報を取得した場合、性能は全体的に劣化しているけど、これくらいなら十分許容範囲内のような気がする。

*1:内部的にはMorphemeクラスが形態素IDを保持するように修正されている

*2:JVM自体の起動時間は除いた数値

UNF-0.0.4: サイズ削減

C++ size library

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

# unf-0.0.3
$ ls -lh unf-0.0.3/bin/unf
-rwxrwxr-x 1 user user 596K 2011-11-19 17:54 unf-0.0.3/bin/unf  # 596KB

# unf-0.0.4
$ ls -lh unf-0.0.4/bin/unf
-rwxrwxr-x 1 user user 411K 2011-11-19 20:20 unf-0.0.4/bin/unf  # 411KB

処理速度も、ごく僅かだけど新しいバージョンの方が速くなっているように見える。

# 17MBのテキストデータの正規化時間

# unf-0.0.3
$ unf-0.0.3/bin/unf-time < 17MB.txt 
= read: 
  == 172090 lines
  == average(line length): 99 byte
= time: 
  == NFD :  0.203354 sec
  == NFC :  0.109814 sec
  == NFKD:  0.215196 sec
  == NFKC:  0.137385 sec
DONE

# unf-0.0.4
$ unf-0.0.4/bin/unf-time < 17MB.txt 
= read: 
  == 172090 lines
  == average(line length): 99 byte
= time: 
  == NFD :  0.199866 sec
  == NFC :  0.104912 sec
  == NFKD:  0.206675 sec
  == NFKC:  0.137277 sec
DONE

Sanmoku(0.0.4): 辞書データサイズ縮小

Java library

この一週間でSanmokuの辞書データサイズの縮小をいろいろ試していたので、その結果を載せておく。
現時点でのバージョンは 0.0.4。

やったこと

試した主なこと。

データ 内容 サイズ
(Gomoku-0.0.4 => Sanmoku-0.0.4)
連接コストデータ
(matrix.bin)		 類似品詞の連接コストを併合*1 + コスト値を14bitで保持 3.5MB => 2.2MB
形態素辞書引きインデックス
(surface-id.bin)		 2バイト文字(UTF-16)DAWGから、1バイト文字(UTF-8)DAWGに変更。
かつIPADICに合わせてノードレイアウトを最適化		 2.7MB => 1.5MB
形態素データ
(morpheme.bin,id-morphems-map.bin)		 4バイト(品詞情報:2バイト、単語コスト:2バイト)から2バイトに 1.8MB => 1.0MB

比較

IgoとGomokuとSanmokuの比較。

　 辞書データサイズ(IPADIC) 最小所要メモリ(-Xmx) 起動(≒辞書ロード)時間*2 10MBテキストの解析時間
Igo-0.4.3 40MB 73MB 0.058秒 2.729秒
Gomoku-0.0.4 8.2MB 23MB 0.371秒 2.621秒
Sanmoku-0.0.4 4.8MB 2MB 0.057秒 5.807秒

Sanmokuは所要メモリや辞書ロード時間が短いが、辞書データを圧縮するためにビット演算や間接参照等を多用しているため、解析速度は他に比べて二倍以上遅くなっている。
Igoは辞書データサイズ自体は大きいが、mmap(java.nio.MappedByteBuffer)を利用しているため、ロード時間は高速となっている。

*1:このためSanmokuは、若干(Gomokuに比べ1%にも満たない程度だが)解析精度が落ちている。

*2:JVM自体の起動時間は除いた数値