marisa-trie に SSE2, SSSE3 を使ってみた

概要

marisa-trie の次期バージョンを開発すべく，昨年末から効率的な BitVector を目指して試行錯誤をしています．その成果として，内部データ構造を変更しなくても，SSE2, SSSE3 を使うことで，marisa-trie を高速化できることを発見しました．

高速化の内容を簡単にまとめると，SSSE3 を使った popcount の高速化と，SSE2 を使った分岐の排除です．内部データ構造は変更していないため，キャッシュミスがボトルネックになるような状況では，それほど効果がありません．

具体的な内容については，後日，解説記事を書こうと思っています．今回は，結果だけを示します．ちなみに，ソースコードはまだ公開できていません．

実験設定

実験環境

実験に用いた CPU は Core2 Duo と Core i7 です．

• Core i7 3720QM 2.6GHz (up to 3.6GHz)
  • Mac OSX + clang
• Core2 Duo U9600 1.6GHz
  • Ubuntu + gcc

キー集合

実験に用いたキー集合は，日本語 Wikipedia のタイトル一覧です．

• jawiki-20121210-all-titles-in-ns0

Number of keys: 1342099
Total length: 28308027

時間の計測には marisa-trie 付属のツールを使いました．また，今回の改良は分岐予測が失敗するような状況で有効なことを確認するため，順序を変更していないファイル（ほぼ整列された状態）とランダムに並べ替えたファイルを用意しました．

実験結果（概要）

Core i7

Marisa を構成する Trie を 1 つにして，ほぼ辞書順に検索したときを除けば，検索速度が向上しました．SSE2, SSSE3, SSE4.2 と有効するにつれて，徐々に高速になるという理想的な結果になりました．

Core2 Duo

残念ながら，期待する結果は得られませんでした．ほぼ辞書順の検索では，むしろ遅くなっています．ランダム順にしても，ほとんど速くなっていません．理由としては，SSE 命令のコストが Core i7 と比べて高い可能性や，キャッシュのサイズが Core i7 より小さいためにキャッシュミスの影響が大きく出ている可能性などが考えられます．後は，使い方が悪いとか…？

まとめ

Core i7 では，SSE2, SSSE3 の導入により，marisa-trie を高速化できました．一方，Core2 Duo では悲惨な結果になりました．

後日，どこまで有効にするのかを configure で指定できるようにして公開する予定です．

実験結果（詳細）

build-sse2, build-ssse3, build-sse4.2 はそれぞれ SSE2, SSSE3, SSE4.2 を有効にした結果をしめしています．また，JAWIKI は並べ替えていないキー集合，JAWIKI-R はランダム順に並べ替えたキー集合を示しています．

Core i7

$ build/tools/marisa-benchmark JAWIKI

























































































































-




























































#tries       size    build   lookup  reverse   prefix  predict
                                      lookup   search   search
          [bytes]    [K/s]    [K/s]    [K/s]    [K/s]    [K/s]

























































































































-




























































     1   11588904  1111.36  2882.75  2516.25  2556.18  1460.69
     2    8467920   910.60  1680.17  1541.07  1566.20   715.59
     3    7841664   855.28  1479.67  1383.47  1392.99   605.73
     4    7633584   840.61  1427.77  1343.94  1345.53   579.77
     5    7548584   834.82  1409.87  1315.75  1328.34   566.02

























































































































-




























































$ build-sse2/tools/marisa-benchmark JAWIKI

























































































































-




























































#tries       size    build   lookup  reverse   prefix  predict
                                      lookup   search   search
          [bytes]    [K/s]    [K/s]    [K/s]    [K/s]    [K/s]

























































































































-




























































     1   11588904  1115.07  2647.81  2471.76  2549.07  1455.26
     2    8467920   913.94  1691.66  1622.42  1602.89   771.79
     3    7841664   860.51  1516.72  1468.76  1442.16   656.93
     4    7633584   857.00  1466.16  1419.32  1398.48   630.50
     5    7548584   850.48  1454.27  1386.69  1385.36   610.32

























































































































-




























































$ build-ssse3/tools/marisa-benchmark JAWIKI

























































































































-




























































#tries       size    build   lookup  reverse   prefix  predict
                                      lookup   search   search
          [bytes]    [K/s]    [K/s]    [K/s]    [K/s]    [K/s]

























































































































-




























































     1   11588904  1107.67  2825.64  2580.70  2502.41  1461.31
     2    8467920   928.89  1739.61  1651.30  1617.79   777.69
     3    7841664   879.37  1574.44  1494.17  1462.67   662.36
     4    7633584   860.85  1524.01  1462.72  1417.86   640.21
     5    7548584   860.16  1480.22  1401.10  1391.49   625.37

























































































































-




























































$ build-sse4.2/tools/marisa-benchmark JAWIKI

























































































































-




























































#tries       size    build   lookup  reverse   prefix  predict
                                      lookup   search   search
          [bytes]    [K/s]    [K/s]    [K/s]    [K/s]    [K/s]

























































































































-




























































     1   11588904  1096.24  2989.98  2701.46  2653.24  1521.17
     2    8467920   914.21  1811.82  1716.62  1700.28   796.52
     3    7841664   860.95  1623.84  1549.89  1530.46   683.62
     4    7633584   842.87  1574.15  1504.38  1484.84   654.85
     5    7548584   840.08  1541.84  1469.55  1459.71   641.65

























































































































-

$ build/tools/marisa-benchmark JAWIKI-R

























































































































-




























































#tries       size    build   lookup  reverse   prefix  predict
                                      lookup   search   search
          [bytes]    [K/s]    [K/s]    [K/s]    [K/s]    [K/s]

























































































































-




























































     1   11588904   757.97  1094.05  1213.85  1010.74   716.64
     2    8467920   667.02   764.25   836.45   714.56   435.07
     3    7841664   638.84   718.75   781.25   677.07   390.78
     4    7633584   630.51   697.24   763.74   656.89   364.93
     5    7548584   612.69   644.59   734.26   635.84   358.67

























































































































-




























































$ build-sse2/tools/marisa-benchmark JAWIKI-R

























































































































-




























































#tries       size    build   lookup  reverse   prefix  predict
                                      lookup   search   search
          [bytes]    [K/s]    [K/s]    [K/s]    [K/s]    [K/s]

























































































































-




























































     1   11588904   759.44  1115.48  1347.92  1047.85   738.68
     2    8467920   667.94   808.44   948.61   764.75   469.14
     3    7841664   638.58   767.31   886.19   722.24   426.97
     4    7633584   631.53   750.16   862.36   711.61   415.82
     5    7548584   627.80   740.60   845.79   699.79   407.02

























































































































-




























































$ build-ssse3/tools/marisa-benchmark JAWIKI-R

























































































































-




























































#tries       size    build   lookup  reverse   prefix  predict
                                      lookup   search   search
          [bytes]    [K/s]    [K/s]    [K/s]    [K/s]    [K/s]

























































































































-




























































     1   11588904   764.55  1190.61  1365.87  1079.28   761.06
     2    8467920   671.27   824.83   955.55   773.72   473.58
     3    7841664   637.15   778.40   889.39   729.81   432.21
     4    7633584   630.97   752.85   830.52   704.97   407.29
     5    7548584   619.43   756.01   864.67   705.01   413.25

























































































































-




























































$ build-sse4.2/tools/marisa-benchmark JAWIKI-R

























































































































-




























































#tries       size    build   lookup  reverse   prefix  predict
                                      lookup   search   search
          [bytes]    [K/s]    [K/s]    [K/s]    [K/s]    [K/s]

























































































































-




























































     1   11588904   726.62  1193.16  1377.19  1093.00   766.01
     2    8467920   643.23   840.79   976.13   792.30   486.24
     3    7841664   620.53   794.45   915.56   752.31   442.86
     4    7633584   613.26   777.39   891.38   732.72   430.42
     5    7548584   608.27   770.72   879.13   722.10   421.59

























































































































-

Core2 Duo

$ build/tools/marisa-benchmark JAWIKI

























































































































-




























































#tries       size    build   lookup  reverse   prefix  predict
                                      lookup   search   search
          [bytes]    [K/s]    [K/s]    [K/s]    [K/s]    [K/s]

























































































































-




























































     1   11588904   467.63  1303.01  1328.81  1167.04   784.85
     2    8467920   383.46   737.42   758.25   691.80   350.42
     3    7841664   365.69   645.24   664.41   612.83   291.13
     4    7633584   358.85   624.23   642.15   586.07   276.15
     5    7548584   355.99   612.83   633.07   581.00   269.50

























































































































-




























































$ build-sse2/tools/marisa-benchmark JAWIKI

























































































































-




























































#tries       size    build   lookup  reverse   prefix  predict
                                      lookup   search   search
          [bytes]    [K/s]    [K/s]    [K/s]    [K/s]    [K/s]

























































































































-




























































     1   11588904   467.63  1242.68  1220.09  1118.42   762.56
     2    8467920   384.56   717.70   733.39   681.27   353.18
     3    7841664   366.69   639.09   648.36   604.55   294.32
     4    7633584   359.81   601.84   627.15   583.52   280.77
     5    7548584   357.89   604.55   621.34   573.55   273.90

























































































































-




























































$ build-ssse3/tools/marisa-benchmark JAWIKI

























































































































-




























































#tries       size    build   lookup  reverse   prefix  predict
                                      lookup   search   search
          [bytes]    [K/s]    [K/s]    [K/s]    [K/s]    [K/s]

























































































































-




























































     1   11588904   467.63  1220.09  1177.28  1118.42   749.78
     2    8467920   384.56   710.11   706.37   674.42   346.80
     3    7841664   364.70   624.23   627.15   593.85   289.87
     4    7633584   360.78   601.84   618.48   578.49   276.15
     5    7548584   355.99   591.23   610.04   571.11   270.04

























































































































-

$ build/tools/marisa-benchmark JAWIKI-R

























































































































-




























































#tries       size    build   lookup  reverse   prefix  predict
                                      lookup   search   search
          [bytes]    [K/s]    [K/s]    [K/s]    [K/s]    [K/s]

























































































































-




























































     1   11588904   336.37   502.66   561.55   462.79   357.89
     2    8467920   295.62   342.37   382.36   320.31   206.16
     3    7841664   284.95   315.05   352.26   294.32   181.61
     4    7633584   281.36   306.42   340.63   288.62   174.30
     5    7548584   279.02   302.27   336.37   285.55   170.97

























































































































-




























































$ build-sse2/tools/marisa-benchmark JAWIKI-R

























































































































-




























































#tries       size    build   lookup  reverse   prefix  predict
                                      lookup   search   search
          [bytes]    [K/s]    [K/s]    [K/s]    [K/s]    [K/s]

























































































































-




























































     1   11588904   336.37   512.25   586.07   472.57   365.69
     2    8467920   295.62   350.42   393.58   328.14   211.69
     3    7841664   283.74   322.62   368.71   305.02   187.44
     4    7633584   280.77   312.84   355.99   293.68   179.67
     5    7548584   278.44   309.95   353.18   292.40   173.85

























































































































-




























































$ build-ssse3/tools/marisa-benchmark JAWIKI-R

























































































































-




























































#tries       size    build   lookup  reverse   prefix  predict
                                      lookup   search   search
          [bytes]    [K/s]    [K/s]    [K/s]    [K/s]    [K/s]

























































































































-




























































     1   11588904   337.21   512.25   581.00   467.63   362.73
     2    8467920   294.97   351.33   399.43   326.54   211.69
     3    7841664   283.74   323.40   367.70   302.96   186.40
     4    7633584   281.36   314.31   356.94   295.62   178.47
     5    7548584   277.29   309.95   352.26   291.13   176.13

























































































































-