検索時間が短くなりました

辞書に対してキャッシュを埋め込むことにより，検索時間の短縮に成功しました．

概要

基本的な考え方は，到達確率の高いノードについて，遷移に必要な情報をダイレクトマップ方式で保存しておくというものです．到達確率については，辞書を構築するときに計算する重みを利用しました．

キャッシュにヒットしたときは，rank() や select() が必要なくなるので，計算コストが小さくなります．また，本来なら別の領域にある情報をキャッシュにまとめたことにより，CPU キャッシュの利用効率も向上しています．

実験結果

以下，現状での実験結果です．

ノードの並びを重み順にしたとき，デフォルトの設定（Normal cache）では，辞書のサイズが 2% くらい大きくなるものの，検索時間を 10-20% くらい短縮できました．悪くないバランスだと思います．

さらにキャッシュを大きくして検索時間を短縮することも可能ですが，辞書のサイズに対する影響が大きすぎるので，トライの数を減らす方が妥当な選択肢になるようです．

Number of tries: 1 - 3
TAIL mode: Text mode
Node order: Descending weight order
Number of keys: 1174430
Total length: 24438317

























































































































-




























































#tries       size    build   lookup  reverse   prefix  predict
                                      lookup   search   search
          [bytes]     [ns]     [ns]     [ns]     [ns]     [ns]

























































































































-




























































Cache level: None (marisa-0.2.0-beta2)
     1   10074384   2486.3    945.1    860.0   1064.3   1524.1
     2    7355800   2997.2   1643.4   1515.6   1762.6   3303.7
     3    6806464   3116.4   1873.2   1720.0   1983.9   3984.9

























































































































-




























































Cache level: Tiny cache (new)
     1   10080536   2018.0    860.0    843.0    936.6   1422.0
     2    7365032   2435.2   1498.6   1498.6   1600.8   3244.1
     3    6818776   2562.9   1703.0   1685.9   1813.6   3857.2

























































































































-




























































Cache level: Small cache (new)
     1   10098968   2009.5    885.5    860.0    970.7   1456.0
     2    7386536   2426.7   1422.0   1464.5   1515.6   3107.9
     3    6840280   2554.4   1634.8   1660.4   1728.5   3755.0

























































































































-




























































Cache level: Normal cache (new)
     1   10172696   2018.0    834.4    851.5    919.6   1404.9
     2    7478696   2435.2   1302.8   1396.4   1404.9   2861.0
     3    6941656   2554.4   1490.1   1566.7   1592.3   3422.9

























































































































-




























































Cache level: Large cache (new)
     1   10467608   2035.0    800.4    851.5    877.0   1362.4
     2    7847336   2435.2   1200.6   1311.3   1294.2   2597.0
     3    7347160   2580.0   1336.8   1464.5   1430.5   3048.3

























































































































-




























































Cache level: Huge cache (new)
     1   11647256   2043.5    732.3    851.5    817.4   1311.3
     2    9321896   2469.3   1064.3   1268.7   1192.1   2333.0
     3    8969176   2597.0   1183.6   1362.4   1277.2   2682.2

























































































































-

ノードの並びをラベル順にしたときは，検索時間の差が顕著になります．埋め込むキャッシュのサイズが辞書のサイズに対して 0.1-0.2% と極小であっても，検索時間は大幅に短縮されます．一方で，キャッシュのサイズを大きくしても，さらなる検索時間の短縮はあまり見込めません．

Number of tries: 1 - 3
TAIL mode: Text mode
Node order: Ascending label order
Number of keys: 1174430
Total length: 24438317

























































































































-




























































#tries       size    build   lookup  reverse   prefix  predict
                                      lookup   search   search
          [bytes]     [ns]     [ns]     [ns]     [ns]     [ns]

























































































































-




























































Cache level: None (marisa-0.2.0-beta2)
     1   10074384   2341.6   2111.7    843.0   2247.9   2818.4
     2    7355800   2801.4   3167.5   1524.1   3269.7   4904.5
     3    6806464   2946.1   3533.6   1720.0   3635.8   5730.4

























































































































-




























































Cache level: Tiny cache (new)
     1   10080536   1873.2   1370.9    834.4   1439.0   2009.5
     2    7365032   2290.5   2247.9   1490.1   2367.1   4070.1
     3    6818776   2375.6   2562.9   1677.4   2716.2   4776.8

























































































































-




























































Cache level: Small cache (new)
     1   10098968   1864.7   1243.2    834.4   1319.8   1847.7
     2    7386536   2264.9   2069.1   1456.0   2171.3   3814.6
     3    6840280   2384.1   2358.6   1711.5   2477.8   4495.8

























































































































-




























































Cache level: Normal cache (new)
     1   10172696   1890.3   1047.3    834.4   1115.4   1668.9
     2    7478696   2256.4   1754.0   1379.4   1847.7   3346.3
     3    6941656   2392.7   1983.9   1558.2   2103.1   3950.9

























































































































-




























































Cache level: Large cache (new)
     1   10467608   1890.3    919.6    834.4   1004.7   1524.1
     2    7847336   2256.4   1490.1   1294.2   1600.8   2912.1
     3    7347160   2384.1   1677.4   1456.0   1779.6   3414.4

























































































































-




























































Cache level: Huge cache (new)
     1   11647256   1890.3    808.9    834.4    885.5   1422.0
     2    9321896   2273.4   1285.7   1226.1   1362.4   2545.9
     3    8969176   2401.2   1430.5   1345.3   1524.1   2937.6

























































































































-

おわりに

今のところ，試してみようと思っている内容が 1 つ残っていて，それが終わったら 0.2.0 の正式版にする予定です．むむむ…．