marisa-trie で BMI2 の PDEP 命令を使えるようにしました

簡潔ビットベクトルの select に BMI2 の PDEP 命令を使うと実装を単純化できる上に高速化できるという情報を見つけたので marisa-trie (https://github.com/s-yata/marisa-trie) に組み込んで試してみました．

PDEP を使うのは， 64-bit 整数まで絞り込んだ後になります．
marisa-trie での該当箇所は以下の通りです．（MSVC 向けの部分はカットしました．）
unit から i+1 番目の 1 になっているビットの位置を求めています．（bit_id はただのオフセットなので気にしなくて OK です．）

std::size_t select_bit(std::size_t i, std::size_t bit_id, UInt64 unit) {
  return bit_id + ::__builtin_ctzll(_pdep_u64(1ULL << i, unit));
}

select は lookup や reverse_lookup の中で特に重い処理なので，結構効果がありました．
以下， marisa-benchmark に日本語 Wikipedia のタイトル一覧（順序そのまま）を入力したときの出力を貼っておきます．
実行環境の CPU は Core i7 6800K 3.4GHz です．

まずは PDEP を使わないバイナリです．

$ make clean && autoreconf && ./configure --enable-bmi && make
...
$ tools/marisa-benchmark -p jawiki-20191001-all-titles-in-ns0
Number of tries: 1 - 5
TAIL mode: Text mode
Node order: Descending weight order
Cache level: Normal cache
Number of keys: 1887667
Total length: 40976550
------+----------+--------+--------+--------+--------+--------
#tries       size    build   lookup  reverse   prefix  predict
                                      lookup   search   search
          [bytes]    [K/s]    [K/s]    [K/s]    [K/s]    [K/s]
------+----------+--------+--------+--------+--------+--------
     1   16224608  1446.04  3608.77  3206.54  3152.50        -
     2   11877920  1169.76  2051.87  1898.60  1977.19        -
     3   11008584  1158.67  1699.86  1695.10  1708.77        -
     4   10692624  1151.92  1685.07  1632.11  1644.95        -
     5   10557664  1155.25  1661.06  1597.17  1618.07        -
------+----------+--------+--------+--------+--------+--------

次に PDEP を使うバイナリです．

$ make clean && ./configure --enable-native-code && make
...
 
$ tools/marisa-benchmark -p jawiki-20191001-all-titles-in-ns0
...
------+----------+--------+--------+--------+--------+--------
#tries       size    build   lookup  reverse   prefix  predict
                                      lookup   search   search
          [bytes]    [K/s]    [K/s]    [K/s]    [K/s]    [K/s]
------+----------+--------+--------+--------+--------+--------
     1   16224608  1418.83  4134.11  3956.39  3858.28        -
     2   11877920  1220.01  2357.28  2276.49  2279.57        -
     3   11008584  1164.50  2037.00  1978.51  1985.62        -
     4   10692624  1158.25  1915.64  1929.95  1909.70        -
     5   10557664  1159.29  1916.36  1902.57  1872.88        -
------+----------+--------+--------+--------+--------+--------

PDEP を使わない場合と比べて PDEP を使う場合は， lookup が 14-20% の高速化， reverse_lookup が 17-23% の高速化となりました．