mbutrovich commented on code in PR #11641:
URL: https://github.com/apache/arrow-rs/pull/11641#discussion_r4568537149


##########
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:
   > Nonetheless, I softened the wording on the comment and kept it generally 
correct without going into this level of detail.
   
   The comment on 
[`Block::check_branch_free`](https://github.com/apache/arrow-rs/blob/314d407c7018af3f6ea32e228bae7599207ce9cc/parquet/src/bloom_filter/mod.rs#L248-L250)
 still says "so it is faster when many hashes are checked in a loop", the same 
text as in the first commit. Your table shows the early exit winning on 
all-miss queries against filters with 1% and 5% of bits set. Could we say when 
each one wins? For example:
   
   ```rust
       /// Same result as [`Block::check`], but tests all 8 words without an 
early
       /// exit. This avoids a mispredicted branch when hits and misses are 
mixed
       /// or the filter is well filled. The early exit is faster when nearly
       /// every hash misses a sparse filter.
   ```



-- 
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