marisa-trie の PopCount を改良しました

簡潔ビットベクトルの基本操作である rank/select において重要な役割を果たす PopCount を改良することにより,marisa-trie (Google Code Archive - Long-term storage for Google Code Project Hosting.) を少しだけ高速化することができました.成果は Subversion からソースコードをダウンロードしてビルドすることにより確認できます.

一つ目の改良点は SSE4.2 で追加された popcnt 命令です.その名の通り,PopCount 専用の CPU 命令であり,PopCount を高速に実現できます.ただし,現状では使える CPU が限られているため,configure に --enable-popcnt を指定してビルドしたときだけ有効になるようにしています.

二つ目の改良点は popcnt 命令を使わない PopCount の効率化です.popcnt 命令をサポートしていない環境ではもちろん,PopCount の途中結果を残しておきたい状況があり,popcnt 命令を使うのが最適とは限りません.

PopCount とは

PopCount というのは,32/64-bit 整数に含まれる 1 になっているビットの数を求める処理です.

popcnt 命令の導入

popcnt 命令を導入するきっかけは,@nokuno さんに対応して欲しいと言われたことと,先月 x86/x64 最適化勉強会(x86/x64最適化勉強会3 : ATND)に参加したことです.以前にも popcnt 命令を検討したことはありましたが,そのときは使える環境がなかったので断念していました.現在は Core i7 を搭載した PC が手元にあるということで,実装・評価をしてライブラリに組み込むにまでいたりました.高速化の程度は微々たるものですが,たしかに速くなっています.

popcnt 命令の使い方としては,アセンブリで書くという手もありますが,gcc では __builtin_popcountll() という組み込み関数が使えます.コンパイルするときに -msse4.2 オプションを指定すれば,popcnt 命令を使ってくれます.ただし,SSE4.2 を使えない環境では動かないので注意が必要です.VC++ では __popcnt64() という関数があります.詳しくは http://gcc.gnu.org/onlinedocs/gcc-3.4.6/gcc/Other-Builtins.html (Other built-in functions provided by GCC) や __popcnt16, __popcnt, __popcnt64 | Microsoft Docs をご覧ください.

  // 64-bit 整数に含まれる 1 になっているビットの数を求めます.
  std::size_t count(UInt64 x) {
#ifdef MARISA_USE_POPCNT  // popcnt 命令の利用を指示するマクロです.
 #ifdef _MSC_VER
  #ifdef _WIN64
    return (std::size_t)::__popcnt64(x);  // VC++ 専用の関数を使います.
  #else  // _WIN64
    return PopCount(x).lo64();  // popcnt 命令を使わないときの動作です.
  #endif  // _WIN64
 #else  // _MSC_VER
    return ::__builtin_popcountll(x);  // gcc 専用の関数を使います.
 #endif  // _MSC_VER
#else  // MARISA_USE_POPCNT
    return PopCount(x).lo64();  // popcnt 命令を使わないときの動作です.
#endif  // MARISA_USE_POPCNT
  }

PopCount の効率化

popcnt 命令を使わないときの効率化については,Wikipedia の記事(Hamming weight - Wikipedia)を参考にしました.ただし,単純に良さそうなものをコピペするとイマイチな結果になってしまったため,試行錯誤を経て現在の実装にいたっています.

  explicit PopCount(UInt64 x) : value_() {
    // 格好良いコードにするより,野暮ったいコードの方が速くなりました.
    x = (x & 0x5555555555555555ULL) + ((x & 0xAAAAAAAAAAAAAAAAULL) >> 1);
    x = (x & 0x3333333333333333ULL) + ((x & 0xCCCCCCCCCCCCCCCCULL) >> 2);
    x = (x & 0x0F0F0F0F0F0F0F0FULL) + ((x & 0xF0F0F0F0F0F0F0F0ULL) >> 4);

    // x += x << 8; x += x << 16; x += x << 32; とするより高速になりました.
    x *= 0x0101010101010101ULL;

    value_ = x;
  }

前半は野暮ったいコードになっていますが,実際に試してみると,上手いコードより少し高速に動作します.高速になる理由は検証していないので何とも言えません.やってみたら速かったという単純な理由で採用しています.差も微々たるものです.

乗算の箇所については,近年の CPU では乗算が高速なことに加えて,演算結果が丁度良いという理由で採用しました.下位 8bits, 16bits, 24bits, ... に含まれる 1 の数もまとめて計算できるところがポイントです.詳しくは marisa-trie における rank/select の実装 - やた@はてな日記 をご覧ください.

どのくらい速くなったか

評価には marisa-trie に付属の marisa-benchmark を使いました.入力として使ったのは Wikipedia のタイトル一覧です.評価実験をおこなった PC の CPU は Intel(R) Core(TM) i7-2640M CPU @ 2.80GHz stepping 07 です.当然のことながら,SSE4.2 が使える環境を選んでいます.OS は Ubuntu 11.10 で,コンパイラgcc-4.6.1 です.

marisa-0.2.0

効率化前の marisa-trie です.

$ xz -cd jawiki-20120121-all-titles-in-ns0.xz | tools/marisa-benchmark
Number of tries: 1 - 5
TAIL mode: Text mode
Node order: Descending weight order
Cache level: Normal cache
Number of keys: 1265072
Total length: 26513371
                                                                                                                          • -
#tries size build lookup reverse prefix predict lookup search search [bytes] [K/s] [K/s] [K/s] [K/s] [K/s]
                                                                                                                          • -
1 10925440 1090.58 2750.16 2480.53 2432.83 1664.57 2 7990536 878.52 1561.82 1506.04 1421.43 739.81 3 7401824 837.80 1405.64 1360.29 1304.20 629.39 4 7207216 816.18 1375.08 1304.20 1265.07 599.56 5 7127896 810.94 1345.82 1290.89 1252.55 582.98
                                                                                                                          • -
marisa-0.2.0 + popcnt 命令

popcnt 命令を使うようにした結果です.検索速度がわずかに向上しています.

## marisa-0.2.0 + popcnt
$ xz -cd jawiki-20120121-all-titles-in-ns0.xz | tools/marisa-benchmark
...
                                                                                                                          • -
#tries size build lookup reverse prefix predict lookup search search [bytes] [K/s] [K/s] [K/s] [K/s] [K/s]
                                                                                                                          • -
1 10925440 1100.06 2811.27 2635.57 2480.53 1686.76 2 7990536 910.12 1601.36 1542.77 1506.04 753.02 3 7401824 860.59 1454.11 1390.19 1360.29 638.93 4 7207216 843.38 1405.64 1345.82 1304.20 608.21 5 7127896 832.28 1390.19 1317.78 1290.89 596.73
                                                                                                                          • -
marisa-0.2.0 + popcnt 命令 + PopCount 効率化

popcnt 命令と PopCount の効率化をともに導入した結果です.検索速度がわずかに向上しています.

## marisa 最新版 with popcnt
$ xz -cd jawiki-20120121-all-titles-in-ns0.xz | tools/marisa-benchmark 
...
                                                                                                                          • -
#tries size build lookup reverse prefix predict lookup search search [bytes] [K/s] [K/s] [K/s] [K/s] [K/s]
                                                                                                                          • -
1 10925440 1090.58 2942.03 2691.64 2635.57 1757.04 2 7990536 890.90 1664.57 1561.82 1542.77 771.39 3 7401824 837.80 1506.04 1421.43 1405.64 652.10 4 7207216 832.28 1421.43 1375.08 1345.82 617.11 5 7127896 816.18 1421.43 1360.29 1331.65 605.30
                                                                                                                          • -
marisa-0.1.5 (おまけ)

2011 年の言語処理学会年次大会で発表した頃の marisa-trie です.restore と reverse lookup, find と prefix search, predict depth と predict search が対応しています.このくらい差があると分かりやすくて助かります.

$ xz -cd jawiki-20120121-all-titles-in-ns0.xz | tools/marisa-benchmark -i
#tries: 1 - 10
trie: patricia
tail: text
order: weight
predict: both IDs and strings
#keys: 1265072
total length: 26513371
                                                                                                                                                  • -
#tries #nodes size build restore lookup find predict predict breadth depth [bytes] [K/s] [K/s] [K/s] [K/s] [K/s] [K/s]
                                                                                                                                                  • -
1 1726083 10876106 658.89 2219.42 2342.73 2073.89 442.33 930.20 2 2297198 7928778 593.93 1265.07 1304.20 1228.23 258.71 470.29 3 2490129 7333788 575.03 1150.07 1160.62 1100.06 232.98 408.09 4 2573620 7135960 569.85 1109.71 1129.53 1063.09 224.30 390.45 5 2618043 7054965 564.76 1109.71 1109.71 1054.23 223.51 390.45 6 2644454 7012661 562.25 1100.06 1109.71 1045.51 221.17 383.36 7 2661685 6993006 562.25 1090.58 1100.06 1045.51 221.17 383.36 8 2673602 6980282 562.25 1072.09 1090.58 1028.51 219.25 379.90 9 2682297 6974273 557.30 1090.58 1100.06 1036.94 220.78 381.05 10 2688797 6969632 564.76 1081.26 1090.58 1036.94 219.25 378.76
                                                                                                                                                  • -

まとめ

地味な改良の話であり,成果も地味ですけど,それなりに楽しめました.簡潔データ構造を実装するときは例外なく使うであろうところなので,また使う機会があると思ってます.