BitVector の select に SSE2 を使ってみる（続き）

最近は同じような内容ばかりでアレなのですが，BitVector の select に SSE2 を使ってみる - やた＠はてな日記の続きです．

概要

前回の記事で「PMOVMSKB を使うより BSR を使った方が速いかも…」と書いたので，それを検証してみました．残念ながら，結論は「環境による」というものです．Core2 Duo (Penryn) では少し遅くなり，Core i7 (Ivy Bridge) では少し速くなりました．

ただし，marisa-trie の検索時間を基準とした結果なので，アプリケーションによっては異なる結果になるかもしれません．

ソースコードの相違点

// PMOVMSKB を使うバージョン
skip = POPCNT_TABLE[_mm_movemask_epi8(x)];

// BSR を使うバージョン
skip = 63 - ::__builtin_clzl(_mm_cvtsi128_si64(x) + 1);

実験環境

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

Core2 Duo U9600 1.6GHz
- 64-bit Ubuntu + gcc 4.6
Core i7 3720QM 2.6GHz (up to 3.6GHz)
- Mac OSX + clang 3.2

キー集合

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

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

検索時間の計測には marisa-benchmark を使いました．

実験結果

Core2 Duo U9600 1.6GHz

誤差かどうか悩む程度の差ですが，何回か実行しても同様の傾向が確認できたため，BSR を使うバージョンの方がわずかに遅いという結論を出しました．

## PMOVMSKB を使うバージョン
$ build-old/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   464.39  1290.48  1290.48  1167.04   780.29
     2    8467920   382.36   745.61   771.32   706.37   362.73
     3    7841664   362.73   661.13   677.83   627.15   302.96
     4    7633584   357.89   624.23   657.89   599.15   289.25
     5    7548584   355.05   627.15   645.24   591.23   281.95

























































































































-

## BSR を使うバージョン
$ build-new/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   454.95  1278.19  1278.19  1156.98   775.78
     2    8467920   383.46   737.42   762.56   695.39   359.81
     3    7841664   363.71   654.68   671.05   615.64   300.92
     4    7633584   358.85   627.15   645.24   593.85   284.95
     5    7548584   355.05   618.48   639.09   541.17   277.29

























































































































-

Core i7 3720QM 2.6GHz (up to 3.6GHz)

BSR を使うバージョンの方が明らかに高速です．それほど大きな差ではありませんが，テーブルが不要になることもあり，BSR の方が優秀と考えて間違いないと思います．ただし，Core i7 では POPCNT を使うバージョンの方が高速になるので，残念ながら用なしです．

## PMOVMSKB を使うバージョン
$ build-old/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  1149.25  2872.48  2605.36  2596.00  1461.48
     2    8467920   955.29  1770.18  1649.93  1651.37   768.88
     3    7841664   899.13  1583.87  1487.61  1494.25   658.57
     4    7633584   883.96  1531.34  1444.24  1446.37   630.51
     5    7548584   875.01  1506.34  1418.17  1420.89   616.76

























































































































-

## BSR を使うバージョン
$ build-new/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  1151.49  2922.56  2662.46  2630.88  1455.42
     2    8467920   957.03  1781.64  1675.17  1680.66   769.12
     3    7841664   877.24  1602.64  1511.55  1513.70   659.18
     4    7633584   863.92  1550.00  1457.72  1468.56   631.62
     5    7548584   858.10  1523.96  1443.38  1443.21   617.07

























































































































-