プログラムの動作が異常に遅い原因は「ランダムアクセス」かもしれない

プログラミングをするときには、用途に応じた言語の選定やコーディングの美しさ、計算にかかるコストなどを考慮する必要があります。しかし、CloudflareのエンジニアであるMarek Majkowskiさんは、そうした言語の種類や計算コストだけでなく、CPUのメモリアクセス特性にも気を配らなければならないと、自身の体験をもとに語っています。 When Bloom filters don't bloom https://blog.cloudflare.com/when-bloom-filters-dont-bloom/ MarekさんはIPアドレスを詐称するIPスプーフィング攻撃を調査するため、パケットの地理的な経路が正当であるかを、画像のようなIPアドレスのリストから判断しようとしました。例えば、イタリアのプロバイダから送信されたパケットが、イタリアから遠く離れたブラジルのデータセンターを経

[aliceandbob]

「シーケンシャルアクセスが得意で、ランダムアクセスが不得意」なのではなくて、キャッシュにヒットするか／しないかの問題だと思います。

[youichirou]

しばしばあるgigazineの「いまいちよくわかってないのに翻訳記事化したやつ」感がする記事。

[yarumato]

“ブルームフィルタのようなデータ構造を使用するときは、CPUのキャッシュにそのデータ構造が収まるかどうか確認する必要がある”

[tmatsuu]

お、あの記事の日本語訳わいわい

[tech0403]

「最終的に得られる結果が不順でいいのであれば」という条件が抜けてる。Setと同じであるならソートされてないのだから、平等にパフォーマンス比較するならmmuniq-bloom|sortだし、ソートされてないと意味ない場合が多い。

[sgo2]

コレ見た方が良いhttps://qiita.com/aosho235/items/60bd41a5b41bcc3b6ea9