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]

Reply via email to