風邪でダウン

土曜日の夜から妙に体がダルいと思っていたのですが，朝起きた段階で頭痛，午後には鼻水とくしゃみが追加されて，実に風邪らしい風邪を引いてダウンしていました．やったことと言えば，宅配便を受け取ったことくらいです．
いろいろと予定が狂ってしまいました．

grn_ts: シーケンシャルアクセス向けの改善

Groonga

以下のようなクエリを試すと，実行時間が想定より長くなることがわかりました．

select Table --filter 'TextCol == "A"'

少し調査すると，フィルタリング以外，具体的にはカラムから値を取り出すのに時間がかかっていることがわかりました．次に，ソースコードを確認したところ，値をひとつ取り出す毎にアトミック命令で参照カウントをインクリメント・デクリメントしていて，それが大きなコストになっていそうなことに気づきました．

そこで，次の値が直前の値と同じセグメントに配置されているときは，参照カウントのデクリメント・インクリメントを省略できるように，ちょっとしたキャッシュ機能を導入してみました．その結果， 1,000 万レコードに対するフィルタリングで 0.2 〜 0.4 秒短縮することができました．

改善前の実行時間が 0.5 〜 0.7 秒くらいなので，それなりに大きな改善になっています．ただし，長くて 12 bytes までの Text しか格納されていない状況で，差がはっきり出るような設定です．

grn_io_win_map() 内部の除算

Groonga

grn_ts で Text カラムにアクセスするときは grn_ja_ref() を使っています．そして，その内部で呼び出される関数の一つが grn_io_win_map() です．より具体的には， 8 bytes 以上の値にアクセスするときに呼び出されます．

気になったのは， grn_io_win_map() の内部で除算が使われていることです．除算は 1 回の演算で 10-20 cycles くらい消費してしまうので，できれば使いたくありません． grn_io_win_map() だと除数が 2 の冪になることがほとんどであり，ビットシフトで置き換えできるケースが大半です．

そういうわけで，除数が 2 の冪になるときはビットシフトを使うようなパッチを作成してみたのですが，性能に有意な差は確認できませんでした．という残念な Issue が以下になります．試算では 5% くらい短縮できるケースもあるんじゃないかと思っていたので残念です．コストが上手いこと隠蔽されているのか，あるいは試算が間違っていただけなのかは不明です．

Darts-clone Q&A

Q: Darts-clone uses 8 bits to store a label and 1 bit to store a flag (has_leaf). The array size limit is really 2^29?

Darts-clone uses 21 bits to represent a relative offset. The remaining 1 bit is used to extend the limit. If the bit is 1, an offset value (represented by 21 bits) is shifted left by 8. As the result, the limit is 2^29.

Q: The structure seems to be a trie. A DAWG is just used in intermediate steps?

DoubleArrayImpl can represent not only a trie but also a DAWG.

Darts-clone stores values as a part of DAWG. If there are no duplicate values, there are no merge-able subtrees.

Darts-clone uses unique IDs as values if values are not specified. In this case, there are no duplicate values and Darts-clone directly builds a trie (not a DAWG) from a keyset because it is faster.

Otherwise, Darts-clone builds a DAWG and then builds a double-array from it.

grn_ts: フィルタの式を省略できるようになりました

Groonga

Groonga ブログに書くほどでもない細かい内容はこちらに書いていくことにしました．

grn_ts は --filter の先頭に '?' を付けることで有効になるわけですが， '?' に続けてフィルタの式を指定する必要がありました．

今回の修正では， --filter '?' だけで grn_ts を有効化できるようにしました．実際にフィルタの適用も省略するようになりましたが，そもそも式が定数の true であれば評価などをスキップするように実装していたため，速度への影響はほとんどありません．

$ groonga /tmp/groonga/db
> select Table --filter '?true' --output_columns '_id' --limit 1
[[0,1448888003.34893,0.0627093315124512],[[[10000000],[["_id","UInt32"]],[1]]]]
> select Table --filter '?' --output_columns '_id' --limit 1
[[0,1448887983.34983,0.0628361701965332],[[[10000000],[["_id","UInt32"]],[1]]]]

Marisa-trie Q&A

Q: How can I know IDs when I create a keyset? Or should I reread the whole dictionary after build()?

As you mentioned, "reread all the keys"-approach is the answer. IDs are allocated in construction and depend on the constructed tree structure. It is difficult to guess IDs before construction.

Please note that If you use an option MARISA_LABEL_ORDER, IDs will change.