Hatena::ブログ(Diary)

やた@はてな日記

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

2014-03-17

MacBook Pro のセットアップ

届いたので徐々にセットアップを進めています.

ソフトウェアアップデート

左上の Apple マークからソフトウェアアップデートを選んで,アップデート可能なものはすべてアップデートしました.

トラックパッドの設定

システム環境設定のトラックパッドを選んで,タップでクリックを有効にし,スクロールの方向も変更しました.

キーボードの設定

システム環境設定のトラックパッドを選んで,右下にある修飾キーで Caps Lock を Control に変更しました.また,入力ソースに日本語のことえりを追加し,カタカナと英字は無効化しました.

ショートカットは以下のようにカスタマイズしました.

  • Mission Control
    • 「左右の操作スペースに移動」を無効化します(三本指のスワイプで移動できます).
    • 誤爆しそうなので,ほかの「Control + 矢印」も無効にします.
    • ついでに「F11/F12」も無効にします.
  • Spotlight
    • どちらも無効化します.
  • 入力ソース
    • 「前の入力ソースを選択」は無効化します.
    • 「入力メニューの次のソースを選択」は Control + Space に変更します.

VMWare Fusion

ダウンロードしてインストールしました.

ゲスト OS としては Ubuntu 13.10 と OSX を入れる予定です.Ubuntu 14.04 が出れば, Ubuntu 13.10 は 14.04 に移行する予定です.