Hatena::ブログ(Diary)

やた@はてな日記

2018-10-16 Blogger に移行 このエントリーのブックマークコメント

はてなダイアリーが終了してしまうので,とりあえず Blogger に移行することにしました.

https://s-yata.blogspot.com/

2015-12-06

風邪でダウン

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

いろいろと予定が狂ってしまいました.

2015-12-03 雨模様

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

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

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

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

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

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

2015-12-01

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_io_win_map() 内部の除算

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% くらい短縮できるケースもあるんじゃないかと思っていたので残念です.コストが上手いこと隠蔽されているのか,あるいは試算が間違っていただけなのかは不明です.

2015-11-30

Darts-clone Q&A

Q: What is the limit number of string in darts clone?

A double-array uses an array and its size must be less than 2^29 (=536M). The array size is greater than the number of keys. So, the maximum number of keys is less than 2^29.

The actual limit depends on keys and values. In general, the array size is proportional to #keys and longer keys require a larger array. Additionally, the number of distinct values affects the array size. If there are few distinct values, the array size will be small.

You can estimate the actual limit by using a part of your keys.

The following are examples (`keys`: the number of keys, `size`: the array size):

Word keys (the average length is 13 bytes).

## Unique values.
$ mkdarts -t ~/corpus/1gm.zero.1m 1gm.zero.1m.darts
keys: 1000000
total: 12740688
Making double-array: 100% |*******************************************|
size: 1861632
total_size: 7446528
## All values are zero.
$ mkdarts ~/corpus/1gm.uniq.1m 1gm.uniq.1m.darts
keys: 1000000
total: 12740688
Making double-array: 100% |*******************************************|
size: 4885248
total_size: 19540992

URL keys (the average length is 53 bytes).

## Unique values.
$ mkdarts ~/corpus/urls.uniq.1m urls.uniq.1m.darts
keys: 1000000
total: 53166751
Making double-array: 100% |*******************************************|
size: 18637312
total_size: 74549248
## All values are zero.
$ mkdarts -t ~/corpus/urls.zero.1m urls.zero.1m.darts
keys: 1000000
total: 53166751
Making double-array: 100% |*******************************************|
size: 11225344
total_size: 44901376

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.

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

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]]]]