博士

ロボ子、Boost 1.90でBloom filterのbulk operationsが導入されたのじゃ！挿入とルックアップがめっちゃ速くなるらしいぞ。

ロボ子

Bloom filterのbulk operationsですか。具体的にどのような最適化がされているのでしょうか？

博士

それがの、Bloom filterの配列内の位置計算とアクセスを時間的に分離するのがミソらしいぞ。挿入処理では、アドレスのプリフェッチでキャッシュされた値にアクセスして、CPUのストールを避けるみたいじゃ。

ロボ子

なるほど。アドレスのプリフェッチですか。ルックアップ処理についてはどうでしょう？

博士

ルックアップ処理(k > 1の場合)は、非bulk手順だとパイプライン化に向かないらしい。分岐が多いからの。でも、bulk-modeルックアップだと、部分的な結果をビットマスクとして保持して、`std::countr_zero`を使って終わった列のグループをスキップするから、イテレーション回数が減るのじゃ！

ロボ子

`std::countr_zero`ですか。ビット演算で効率的にスキップするのですね。しかし、記事によると、bulkバージョンは条件分岐が少し多いとのことですが…。

博士

そうなんじゃ。でもベンチマークでは、追加のメモリフェッチを行うバージョンの方が速いことが示されたみたい。不思議じゃな〜。

ロボ子

興味深いですね。具体的にどれくらいの速度向上が見込めるのでしょうか？

博士

記事によると、例えばarraysizeが8Mの時、K=1、p=0の場合だと0.78倍だけど、p=0.1だと1.43倍になるみたいじゃ。arraysizeが大きくなると、もっと差が出るみたいだぞ！

ロボ子

なるほど。フィルタの構成とサイズによって速度向上の度合いが変わるのですね。場合によってはパフォーマンスが低下することもある、と。

博士

そういうことじゃ！でも、最大で3倍も速くなる可能性があるなら、試してみる価値はあるのじゃ！

ロボ子

そうですね。Boost.Bloomのbulk operations、私も試してみます。ところで博士、Bloom filterの「Bloom」って、誰かの名前から来ているのでしょうか？

博士

鋭い質問じゃな、ロボ子！実は、Bloom filterはBurton Howard Bloomさんという人が考案したのじゃ。…って、ロボ子もしかして、私の名前の由来を知りたかったのじゃ？残念ながら、私はただの天才美少女じゃ！

ロボ子

（苦笑）まさか。博士は博士です。