github / github/rust-gems

Performance improvement in `SimHashIterator`

オープン
#78 コメント 0 件 リアクション 0 件 担当者 0 名 GitHub で見る
主要言語
Rust
スター
134
フォーク
24
平均マージ
16時間 27分
マージ済み PR(30日)
11

説明

The current `SimHashIterator` works by finding the most significant active bit, and then calculating the number of `SimHash` buckets that will exist from that bit to the end of the filter. This means we are iterating `(most_significant_bit / SIM_BUCKET_SIZE) + SIM_BUCKETS` buckets.

The problem here is that in the higher order bits the sparsity is very high, meaning that there will potentially be many buckets where the values we're mixing into our `SimHash`es will just be zeros, and given any value XOR `0` is just that value this is wasted computation.

We could move to use the `BitChunks` iterators which batch up our chunks into a `u64` and an index of that block of bits, skipping ranges full of zeros. This will introduce issues where if our `SimHash` bucket straddles multiple `BitChunks`, which can be solved by peeking the next chunk, making sure that the index is contiguous with our current chunk.

Right now `SIM_BUCKET_SIZE` is always `6` bits but if we allowed fully arbitrary `SimHash` bucket sizes this could get slightly gnarly because we'd need to be able to peek an arbitrary number of `BitChunk`s ahead of the current position.

The following is a line chart plot of the proportion of empty `bit_range`s mixed into the SimHashes using pseudorandomly generated geofilters with `0..100_000` items added to them.

Image

The ratio reduces very sharply after a couple of inserts but remains relatively high since newly added items have some chance of landing in a very significant bucket which introduces a load of zero gaps before the next one bit.

コントリビューションガイド

コントリビューションガイドを開く

調査の方向性

まずリポジトリ内で SimHashIterator、BitChunks、SIM_BUCKET_SIZE を見つけ、現在バケットがどのように形成されているかを確認します。BitChunks でゼロの範囲をスキップする方法と、複数のチャンクにまたがるバケットをどのように扱うかを調査します。SimHash のバケット結果を変更せずに空の範囲の混在を減らせれば完了です。

索引モデルが issue の本文から書いたものです。

評価

技術スタック
rust
領域
performance
issue の種類
リファクタリング
難易度
4/5
見積もり時間
3〜5日
活発さ
停滞
明瞭さ
おおむね明確
初心者へのやさしさ
38/100

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。