marisa-trie に SSE2, SSSE3 を使ってみた（続き）

概要

前回の記事を書いた後，有効にする命令セットをいろいろと試してみたところ，gcc と clang では傾向が異なることが分かりました．

gcc では SSE4.1 を有効にすると速くなりましたが，clang では SSE4.1 を有効にしてもほとんど変化しませんでした．
また，全体的に clang より gcc の方が速くなりました．

実験環境

実験に用いた CPU は Core2 Duo と Core i7 です．
ただし，Core i7 の方は前回の実験に用いたものと異なっているので注意してください．

• Core2 Duo U9600 1.6GHz
  • 64-bit Ubuntu + gcc 4.6 or clang 3.1
• Core i7 2640M 2.8GHz (up to 3.5GHz)
  • 64-bit Ubuntu + gcc 4.6 or clang 3.1

キー集合

キー集合は前回と同じで，日本語 Wikipedia のタイトル一覧です．

• jawiki-20121210-all-titles-in-ns0
  • Number of keys: 1342099
  • Total length: 28308027

計測方法も前回と同じで，marisa-trie 付属のツールである marisa-benchmark を使いました．

実験結果

命令セットの制限は，SSE2 まで, SSE3 まで, SSSE3 まで, SSE4.1 まで, SSE4.2 までの 5 種類を試しました．
ただし，SSE2 までと SSE3 までではほとんど違いがなかったため，SSE3 までに制限したときの結果は省略しています．

Core2 Duo U9600 1.6GHz + gcc 4.6

## 並べ替えなし


























































































































-




























































#tries       size    build   lookup  reverse   prefix  predict

                                      lookup   search   search

          [bytes]    [K/s]    [K/s]    [K/s]    [K/s]    [K/s]


























































































































-




























































     1   11588904   451.89  1303.01  1315.78  1177.28   771.32

     2    8467920   376.99   725.46   749.78   681.27   345.01

     3    7841664   358.85   636.07   645.24   596.49   286.77


























































































































-




























































     1   11588904   461.20  1242.68  1220.09  1109.17   766.91 (enable-sse2)

     2    8467920   378.06   721.56   729.40   674.42   351.33

     3    7841664   358.85   633.07   645.24   601.84   294.32


























































































































-




























































     1   11588904   459.62  1231.28  1177.28  1118.42   745.61 (enable-ssse3)

     2    8467920   378.06   710.11   710.11   671.05   343.25

     3    7841664   358.85   630.09   627.15   596.49   288.62


























































































































-




























































     1   11588904   459.62  1278.19  1290.48  1147.09   780.29 (enable-sse4.1)

     2    8467920   379.12   737.42   762.56   699.01   359.81

     3    7841664   359.81   651.50   677.83   618.48   300.92


























































































































-

## ランダム順


























































































































-




























































#tries       size    build   lookup  reverse   prefix  predict

                                      lookup   search   search

          [bytes]    [K/s]    [K/s]    [K/s]    [K/s]    [K/s]


























































































































-




























































     1   11588904   326.54   489.82   541.17   450.37   347.69

     2    8467920   289.87   333.86   370.75   312.84   201.82

     3    7841664   280.19   306.42   340.63   287.39   177.53


























































































































-




























































     1   11588904   329.75   502.66   571.11   461.20   357.89 (enable-sse2)

     2    8467920   289.87   345.90   392.43   322.62   209.05

     3    7841664   279.60   318.79   360.78   298.24   184.35


























































































































-




























































     1   11588904   330.57   495.24   559.21   453.41   353.18 (enable-ssse3)

     2    8467920   289.87   339.77   383.46   318.03   203.97

     3    7841664   279.02   315.79   355.05   296.27   181.86


























































































































-




























































     1   11588904   329.75   504.55   581.00   462.79   357.89 (enable-sse4.1)

     2    8467920   290.50   347.69   399.43   325.75   210.03

     3    7841664   279.60   318.03   366.69   296.92   184.86


























































































































-

Core2 Duo U9600 1.6GHz + clang 3.1

## 並べ替えなし


























































































































-




























































#tries       size    build   lookup  reverse   prefix  predict

                                      lookup   search   search

          [bytes]    [K/s]    [K/s]    [K/s]    [K/s]    [K/s]


























































































































-




























































     1   11588904   500.78  1187.70  1082.34  1040.39   591.23

     2    8467920   420.72   691.80   671.05   627.15   298.91

     3    7841664   401.83   610.04   593.85   561.55   253.23


























































































































-




























































     1   11588904   504.55  1156.98  1109.17  1024.50   586.07 (enable-sse2)

     2    8467920   419.41   706.37   706.37   645.24   312.12

     3    7841664   401.83   627.15   624.23   578.49   265.24


























































































































-




























































     1   11588904   502.66  1177.28  1147.09  1024.50   596.49 (enable-ssse3)

     2    8467920   420.72   713.88   721.56   651.50   316.53

     3    7841664   403.03   633.07   624.23   586.07   270.04


























































































































-




























































     1   11588904   504.55  1177.28  1137.37  1032.38   591.23 (enable-sse4.1)

     2    8467920   419.41   713.88   713.88   654.68   315.79

     3    7841664   401.83   630.09   636.07   583.52   266.82


























































































































-

## ランダム順


























































































































-




























































#tries       size    build   lookup  reverse   prefix  predict

                                      lookup   search   search

          [bytes]    [K/s]    [K/s]    [K/s]    [K/s]    [K/s]


























































































































-




























































     1   11588904   360.78   475.92   506.45   437.17   307.12

     2    8467920   323.40   328.14   354.12   306.42   187.18

     3    7841664   312.84   302.96   326.54   284.34   165.49


























































































































-




























































     1   11588904   361.75   486.27   545.57   447.37   304.33 (enable-sse2)

     2    8467920   323.40   339.77   380.20   312.12   191.18

     3    7841664   312.12   314.31   351.33   294.97   170.53


























































































































-




























































     1   11588904   360.78   489.82   556.89   451.89   308.53 (enable-ssse3)

     2    8467920   323.40   345.01   389.01   323.40   194.79

     3    7841664   312.84   318.79   356.94   299.58   174.98


























































































































-




























































     1   11588904   359.81   491.61   556.89   450.37   315.05 (enable-sse4.1)

     2    8467920   322.62   344.13   387.89   321.08   196.21

     3    7841664   309.24   315.79   355.99   297.58   174.75


























































































































-

Core i7 2640M 2.8GHz (up to 3.5GHz) + gcc 4.6

## 並べ替えなし


























































































































-




























































#tries       size    build   lookup  reverse   prefix  predict

                                      lookup   search   search

          [bytes]    [K/s]    [K/s]    [K/s]    [K/s]    [K/s]


























































































































-




























































     1   11588904  1100.08  2917.61  2631.57  2532.26  1742.99

     2    8467920   882.96  1636.71  1578.94  1507.98   762.56

     3    7841664   838.81  1443.12  1412.74  1342.10   636.07


























































































































-




























































     1   11588904  1100.08  2631.57  2440.18  2313.96  1677.62 (enable-sse2)

     2    8467920   888.81  1578.94  1507.98  1427.76   775.78

     3    7841664   838.81  1412.74  1369.49  1290.48   651.50


























































































































-




























































     1   11588904  1091.14  2631.57  2396.61  2274.74  1656.91 (enable-ssse3)

     2    8467920   882.96  1560.58  1474.83  1412.74   749.78

     3    7841664   838.81  1383.61  1328.81  1266.13   639.09


























































































































-




























































     1   11588904  1118.42  2738.98  2580.96  2354.56  1720.64 (enable-sse4.1)

     2    8467920   906.82  1636.71  1578.94  1474.83   798.87

     3    7841664   860.32  1458.80  1412.74  1328.81   671.05


























































































































-




























































     1   11588904  1118.42  2796.04  2684.20  2440.18  1765.92 (enable-sse4.2)

     2    8467920   912.99  1677.62  1636.71  1560.58   818.35

     3    7841664   860.32  1507.98  1474.83  1398.02   684.74


























































































































-

## ランダム順


























































































































-




























































#tries       size    build   lookup  reverse   prefix  predict

                                      lookup   search   search

          [bytes]    [K/s]    [K/s]    [K/s]    [K/s]    [K/s]


























































































































-




























































     1   11588904   775.78  1040.39  1198.30   965.54   745.61

     2    8467920   674.42   737.42   838.81   691.80   438.59

     3    7841664   645.24   677.83   780.29   642.15   391.28


























































































































-




























































     1   11588904   745.61  1001.57  1167.04   919.25   710.11 (enable-sse2)

     2    8467920   645.24   758.25   865.87   702.67   454.95

     3    7841664   621.34   702.67   808.49   657.89   405.47


























































































































-




























































     1   11588904   771.32  1056.77  1231.28   979.63   753.99 (enable-ssse3)

     2    8467920   667.71   741.49   849.43   691.80   442.94

     3    7841664   645.24   691.80   789.47   645.24   397.07


























































































































-




























































     1   11588904   741.49  1032.38  1231.28   972.54   737.42 (enable-sse4.1)

     2    8467920   648.36   766.91   894.73   717.70   462.79

     3    7841664   624.23   717.70   833.60   671.05   416.80


























































































































-




























































     1   11588904   775.78  1091.14  1290.48  1016.74   775.78 (enable-sse4.2)

     2    8467920   674.42   771.32   900.74   729.40   467.63

     3    7841664   645.24   733.39   849.43   691.80   422.04


























































































































-

Core i7 2640M 2.8GHz (up to 3.5GHz) + clang 3.1

## 並べ替えなし


























































































































-




























































#tries       size    build   lookup  reverse   prefix  predict

                                      lookup   search   search

          [bytes]    [K/s]    [K/s]    [K/s]    [K/s]    [K/s]


























































































































-




























































     1   11588904  1198.30  2631.57  2354.56  2313.96  1383.61

     2    8467920   994.15  1560.58  1474.83  1427.76   691.80

     3    7841664   945.14  1412.74  1303.01  1290.48   586.07


























































































































-




























































     1   11588904  1209.10  2580.96  2354.56  2236.83  1398.02 (enable-sse2)

     2    8467920  1016.74  1578.94  1507.98  1443.12   737.42

     3    7841664   965.54  1427.76  1369.49  1315.78   627.15


























































































































-




























































     1   11588904  1220.09  2631.57  2440.18  2354.56  1412.74 (enable-ssse3)

     2    8467920  1009.10  1656.91  1560.58  1525.11   745.61

     3    7841664   958.64  1474.83  1412.74  1369.49   639.09


























































































































-




























































     1   11588904  1198.30  2631.57  2440.18  2354.56  1398.02 (enable-sse4.1)

     2    8467920   986.84  1636.71  1578.94  1525.11   745.61

     3    7841664   945.14  1474.83  1412.74  1398.02   639.09


























































































































-




























































     1   11588904  1209.10  2738.98  2532.26  2485.37  1398.02 (enable-sse4.2)

     2    8467920   986.84  1698.86  1616.99  1578.94   745.61

     3    7841664   945.14  1542.64  1458.80  1427.76   645.24


























































































































-

## ランダム順


























































































































-




























































#tries       size    build   lookup  reverse   prefix  predict

                                      lookup   search   search

          [bytes]    [K/s]    [K/s]    [K/s]    [K/s]    [K/s]


























































































































-




























































     1   11588904   798.87   958.64  1137.37   925.59   651.50

     2    8467920   710.11   702.67   794.14   657.89   404.25

     3    7841664   684.74   667.71   745.61   627.15   368.71


























































































































-




























































     1   11588904   823.37  1040.39  1220.09   945.14   684.74 (enable-sse2)

     2    8467920   733.39   745.61   865.87   691.80   434.34

     3    7841664   702.67   706.37   808.49   657.89   395.90


























































































































-




























































     1   11588904   818.35  1056.77  1254.30   986.84   691.80 (enable-ssse3)

     2    8467920   729.40   762.56   900.74   717.70   440.03

     3    7841664   702.67   702.67   828.46   667.71   391.28


























































































































-




























































     1   11588904   828.46  1056.77  1254.30   979.63   691.80 (enable-sse4.1)

     2    8467920   733.39   753.99   894.73   713.88   437.17

     3    7841664   702.67   699.01   838.81   677.83   400.63


























































































































-




























































     1   11588904   794.14  1016.74  1198.30   965.54   654.68 (enable-sse4.2)

     2    8467920   710.11   766.91   900.74   725.46   442.94

     3    7841664   681.27   721.56   849.43   688.26   404.25


























































































































-