レコード付き動的ダブル配列

研究

ブロック管理の詳細を、ダブル配列の世界的権威の某氏に昨日伺ったので実装し直し。400行近くなってしまった。デバッグ中。体調微妙なので深刻なバグを作り込んでないか心配。

[追記] ブロックの連結リストが壊れるバグを修正してデバッグ完了。ランダム順追加でも50秒程度(辞書順だと20秒)とかなり高速にバイナリのダブル配列を構築できるようになった。動的ダブル配列の実装もこれで一段落か。370行。後二三日最適化したら、予定していた用途に使ってみよう・・・

[追記] 遷移節点集合や，ブロック内未使用要素リストをソートしないようにして高速化。343行。float の値を格納できるようにして，予定した用途に使ってみたら、ハッシュベースのトライを使う場合に比べて，実行速度は約2倍となった。これだけ速ければまあ満足だ。苦労したかいがあったというところ。ダブル配列万歳。

[追記] ところで，値をダブル配列に保存するのは値の型によってはやや面倒だ．値の保存方法としては，

  1. base に保存 (ブロック管理の場合，256 要素単位で配列管理するので，\0 で遷移した先の base を使う)．
  2. 外部配列に保存 (↑の base 値を外部配列のインデクスとして利用)
  3. TAIL を実装している場合，TAIL にシリアライズ (2 とメモリの確保を除いて実質的に同じ)．

があるのだけど，2,3 は値の型やサイズを選ばない反面，外部配列への余分なアクセスが生じるため，検索速度の観点からは不利 (キーの数が多く，かつ検査するキーの平均の長さが小さい場合は影響大)．しかし 1 の場合，base の型 (int) と同じサイズ以下の値しか保存できないため，1 (int, float, short など) を使える型には 1 を，そうでない型 (char*, double) には 2 を使うのが望ましい．1 では，検索関数が値とエラーの両方を同じ型で返す場合 (今回採用)，検索失敗時の返り値を成功時の返り値の値域外にする必要がある．今までは float を仮数部の精度を 1 bit 犠牲にして非負整数に変換していたが，丸め誤差の影響が無視できなくなって来たので，検索失敗時には NaN (に対応する int) を返すようにした．344 行．

しかし，コンパイラに gcc を使っていると，型変換に reinterpret_cast とかを使う場合 (type punning), コンパイルオプションに -fno-strict-aliasing を入れておかないと -O2 とかで不適切な最適化が行われてしまう (cf. strict aliasing rule 参照)．回避するには共用体を使えば良いが，プログラムが長くなるし，共用体の初期化で (-Weffc++ だと) warning が出たりと嫌な感じだ．

[追記] しばらく 

// pointer cast; remember to set -fno-strict-aliasing with gcc -On (n>=2)
template <class P>
static inline P pointer_cast (void* p) { return static_cast <P> (p); }

のように書いていが，これだと type punning / strict aliasing の Warning が出ないため -fno-strict-aliasing し忘れる危険がある上、プログラム全体に -fno-strict-aliasing するとダブル配列を組み込むプログラム側で，速度が1割程度落ちてしまうことがあったので，

template <typename T>
struct node {
  union { int base; T value; };
  int check;
  node () : base (0), check (0) {};
  node (const int base_, const int check_) 
    : base (base_), check (check_) {};
};

みたいな感じにした．テンプレートクラスの中のメンバ関数で無名共用体を使うと gcc が -Wall で共用体のメンバに対して unused variable とか Warning を出すのは何故なのかなぁ．無名共用体，スマートで便利なのに．