adriangb commented on code in PR #11641:
URL: https://github.com/apache/arrow-rs/pull/11641#discussion_r4568165288
##########
parquet/src/bloom_filter/mod.rs:
##########
@@ -563,6 +579,64 @@ impl Sbbf {
self.0[block_index].check(hash as u32)
}
+ /// Same result as [`Self::check_hash`], without data-dependent branches.
+ #[cfg_attr(not(any(feature = "arrow", test)), expect(dead_code))]
+ #[inline(always)]
+ fn check_hash_branch_free(&self, hash: u64) -> bool {
+ let block_index = self.hash_to_block_index(hash);
+ self.0[block_index].check_branch_free(hash as u32)
+ }
+
+ /// Inserts precomputed 64-bit hashes.
+ ///
+ /// The filter can hold hashes from any well-mixed 64-bit hash function,
+ /// but [`Self::check`] only finds values whose hashes were computed as
+ /// the Parquet specification requires (xxHash64, seed 0, of the plain
+ /// encoding). Use [`Self::check_hashes`] with the same hash function.
+ pub fn insert_hashes(&mut self, hashes: &[u64]) {
+ for &hash in hashes {
+ self.insert_hash(hash);
+ }
+ }
+
+ /// Checks precomputed 64-bit hashes (see [`Self::insert_hashes`]).
+ ///
+ /// Bit `i` of the result is set if `hashes[i]` may be in the filter. The
+ /// check has no data-dependent branches, which is much faster than
Review Comment:
You're right. It's not *always* faster. I ran some benchmarks and tried to
distill the results into a comment (71e9f1e7ab5cc709a27608391fe06ef773ccae7a).
You're right, it's not always faster, so I dropped the performance claim:
the doc now just says it is a branch-free bulk check.
TLDR of my benchmarks (2 MiB filter, precomputed hashes, the early-exit
check called once per hash via `BooleanBuffer::collect_bool`, as a caller would
write it):
With hits and misses mixed, branch-free is faster. At 50% hits it is
1.7–2.2x faster, depending on filter size.
When every hash misses, it depends on how full the filter is:
bits set | early exit vs branch-free
-- | --
1% | 0.85x (early exit wins)
5% | 0.92x
13% | 1.04x
28% | 1.43x
51% (sized for 1% fpp) | 2.38x
A miss in a nearly empty filter fails on the first word, so the early exit
predicts well. In a filter sized for its target fpp, a miss fails at an
unpredictable word and the branch mispredicts. Both versions pay the same
one-cache-line load, so testing all 8 words costs little extra.
So the early exit only wins on a nearly empty filter, and even then by less
than 15%. The new `hash_api` benchmark in `parquet/benches/bloom_filter.rs`
covers sparse and 1%-fpp filters with miss, hit and mixed queries.
Nonetheless, I softened the wording on the comment and kept it generally
correct without going into this level of detail.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]