etseidl commented on code in PR #11641:
URL: https://github.com/apache/arrow-rs/pull/11641#discussion_r4556143783
##########
parquet/src/bloom_filter/mod.rs:
##########
@@ -857,6 +931,65 @@ fn read_bloom_filter_header_and_length(buffer: &[u8]) ->
Result<(BloomFilterHead
mod tests {
use super::*;
+ fn bitset(f: &Sbbf) -> Vec<u8> {
+ let mut out = vec![];
+ f.write_bitset(&mut out).unwrap();
+ out
+ }
+
+ #[test]
+ fn test_branch_free_check_matches_check() {
+ let mut filter = Sbbf::new_with_num_of_bytes(256);
+ for i in 0..200u64 {
+ filter.insert(&(i * 7));
+ }
+ for i in 0..5000u64 {
+ let h = hash_as_bytes(&i);
+ assert_eq!(filter.check_hash(h), filter.check_hash_branch_free(h));
+ }
+ }
+
+ #[cfg(feature = "arrow")]
+ #[test]
+ fn test_check_hashes_matches_check_hash() {
+ let hashes: Vec<u64> = (0..5000u64).map(|i|
hash_as_bytes(&i)).collect();
+ let mut filter = Sbbf::new_with_num_of_bytes(256);
+ filter.insert_hashes(&hashes[..200]);
+ let result = filter.check_hashes(&hashes);
+ for (i, &h) in hashes.iter().enumerate() {
+ assert_eq!(result.value(i), filter.check_hash(h));
+ }
+ assert!((0..200).all(|i| result.value(i)));
+ }
+
+ #[test]
+ fn test_union_of_parts_matches_one_filter() {
+ let hashes: Vec<u64> = (0..100_000u64).map(|i|
hash_as_bytes(&i)).collect();
+ let mut whole = Sbbf::new_with_num_of_bytes(1 << 20);
+ whole.insert_hashes(&hashes);
+ let mut merged = Sbbf::new_with_num_of_bytes(1 << 20);
+ for chunk in hashes.chunks(7_000) {
+ let mut part = Sbbf::new_with_num_of_bytes(1 << 20);
+ part.insert_hashes(chunk);
+ merged.union(&part).unwrap();
+ }
+ assert_eq!(bitset(&whole), bitset(&merged));
+ // union then fold == fold then union
+ let mut folded = whole.clone();
+ folded.fold_to_target_fpp(0.01);
+ merged.fold_to_target_fpp(0.01);
+ assert_eq!(bitset(&folded), bitset(&merged));
Review Comment:
This is folding two filters we've already established above are identical. I
think the loop above needs to be repeated, with each part folded before
unioning into `merged`.
##########
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
+ /// checking one hash at a time.
+ #[cfg(feature = "arrow")]
+ pub fn check_hashes(&self, hashes: &[u64]) -> arrow_buffer::BooleanBuffer {
+ arrow_buffer::BooleanBuffer::collect_bool(hashes.len(), |i| {
+ self.check_hash_branch_free(hashes[i])
+ })
+ }
+
+ /// Adds the values of `other` to this filter, so that afterwards it
+ /// contains every value that either filter contained.
+ ///
+ /// `other` must have at least as many blocks as this filter, and a
+ /// multiple of them. When it has more, it is folded to the size of this
+ /// filter on the fly (see [`Self::fold_to_target_fpp`]), without changing
+ /// `other`. Folding and union commute: the result is the same as
+ /// inserting the values of both filters into one filter and folding it
+ /// to this size. This lets independent filters (for example, one per
+ /// thread) be built and then merged.
+ pub fn union(&mut self, other: &Sbbf) -> Result<(), ParquetError> {
+ let (len, other_len) = (self.0.len(), other.0.len());
+ if other_len < len || other_len % len != 0 {
Review Comment:
This will panic if `len == 0`. should guard against that.
##########
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
+ /// checking one hash at a time.
+ #[cfg(feature = "arrow")]
+ pub fn check_hashes(&self, hashes: &[u64]) -> arrow_buffer::BooleanBuffer {
+ arrow_buffer::BooleanBuffer::collect_bool(hashes.len(), |i| {
+ self.check_hash_branch_free(hashes[i])
+ })
+ }
+
+ /// Adds the values of `other` to this filter, so that afterwards it
+ /// contains every value that either filter contained.
+ ///
+ /// `other` must have at least as many blocks as this filter, and a
+ /// multiple of them. When it has more, it is folded to the size of this
+ /// filter on the fly (see [`Self::fold_to_target_fpp`]), without changing
+ /// `other`. Folding and union commute: the result is the same as
+ /// inserting the values of both filters into one filter and folding it
+ /// to this size. This lets independent filters (for example, one per
+ /// thread) be built and then merged.
Review Comment:
Should we also state that the same hash needs to be used for `other`?
##########
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:
Is it always much faster? Should this be qualified at all?
--
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]
