This will panic if len == 0. should guard against that.

Addressed in e828a78

Should we also state that the same hash needs to be used for other?

👍🏻 done in 0b135b5

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.

Done in 314d407

Is it always much faster? Should this be qualified at all?

You're right. It's not always faster. I ran some benchmarks and tried to distill the results into a comment (71e9f1e).

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:

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.

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

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

Sorry looks like 71e9f1e had gotten lost / overwritten. I now adopted your wording from #11641 (comment) (bfa6657)

insert_hash is public in every build, but check_hashes is the only way to query those hashes, and it needs the arrow feature. Without arrow, a caller can fill a filter with their own hashes and never check it. With arrow, a caller that has one probe hash has to build a BooleanBuffer.

Should check_hash be public too? The early exit is a reason to offer check_hashes for bulk probes, but it doesn't stop check_hash from being the single-hash counterpart to insert_hash. If it becomes public, the insert_hash docs could point to it alongside check_hashes.

I'd propose we wait until someone requests it (the use I have in Datafusion doesn't need it) but happy to do it now for API parity if you'd like.

check_hashes panics on a filter with no blocks, because hash_to_block_index returns 0 and self.0[0] is out of bounds. Sbbf::new returns such a filter for any bitset shorter than 32 bytes, so Sbbf::new(&[0; 31]).check_hashes(&[1]) panics. insert_hash panics the same way.

This predates the PR: insert and check on main go through the same hash_to_block_index and index. But union in this PR returns an error for an empty filter, so the three new methods disagree on that input. Do you want to handle it here, or in a separate PR? Here, an empty filter contains nothing, so check_hashes could return all unset bits, and insert_hash could document the panic in a # Panics section. A separate PR could stop Sbbf::new from producing an empty filter.

Handled as per your suggestion in 0cc21e1. I agree a followup should make Sbbf::new return an error.