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% の高速化となりました.