Vivek1106-04 opened a new pull request, #58551: URL: https://github.com/apache/spark/pull/58551
### What changes were proposed in this pull request? Both bloom filter implementations reduce a hash into a bit index with `hash % bitSize`, once per hash function, in the innermost loop of `put` and `mightContain`: ```java // BloomFilterImplV2#scatterHashAndSetAllBits long combinedIndex = combinedHash < 0 ? ~combinedHash : combinedHash; bitsChanged |= bits.set(combinedIndex % bitSize); ``` `bitSize` is a field rather than a compile time constant, so this compiles down to a hardware division on every probe. `BitArray` rounds its allocation up to whole 64 bit words, so its bit size is a power of two for a wide range of requested sizes. Taking a non-negative value modulo a power of two is exactly masking off its low bits, and both implementations already flip negative hashes before reducing them. This PR: - caches the mask (`bitSize - 1` when the bit size is a power of two, 0 otherwise) in `BitArray`. It is computed in the single private constructor that every construction path funnels through, including `BitArray#readFrom`, so no deserialization path can miss it. - routes both scatter loops of `BloomFilterImpl` (V1) and `BloomFilterImplV2` through a new `BloomFilterBase#bitIndex`, which masks when the mask is set and falls back to the modulo otherwise. The condition is loop invariant, so it is hoisted out of the loop. - lets the V1 fallback use a 32 bit division when its hash and the bit size both fit in an int, instead of widening both to a 64 bit one. V1's `combinedHash` is an `int`, so today it pays a 64 bit division to reduce a 32 bit value. The bit positions produced are unchanged, so there is no new `BloomFilter.Version`, no change to serialized filters, no change to the memory footprint and no change to the false positive rate. ### Why are the changes needed? This is the hottest loop of the runtime bloom filter used by `bloom_filter_agg` / `might_contain` for join pushdown, and the reduction happens once per hash function per row. The Spark SQL runtime bloom filter sizes are powers of two, so the masking path is what those filters take: `spark.sql.optimizer.runtime.bloomFilter.numBits` defaults to `8388608` (2^23) and `spark.sql.optimizer.runtime.bloomFilter.maxNumBits` to `67108864` (2^26). Benchmark, on the power of two sizes (`Bit Size Shape Impact` section added to `SparkBloomFilterBenchmark`), per row nanoseconds, lower is better. Two runs after the change are given because these numbers carry a few percent of run to run noise: | Case | before | after (run 1 / run 2) | | --- | --- | --- | | Put, 100k items, 2^20 bits, V1 | 36.2 | 27.6 / 29.5 | | Put, 100k items, 2^20 bits, V2 | 35.7 | 32.5 / 29.3 | | Put, 1M items, 2^23 bits, V1 | 38.9 | 35.6 / 35.7 | | Put, 1M items, 2^23 bits, V2 | 39.1 | 36.2 / 36.1 | | MightContain, 100k items, 2^20 bits, V1 | 14.7 | 13.7 / 13.6 | | MightContain, 100k items, 2^20 bits, V2 | 14.4 | 13.1 / 13.1 | | MightContain, 1M items, 2^23 bits, V1 | 13.7 | 13.3 / 13.3 | | MightContain, 1M items, 2^23 bits, V2 | 13.4 | 12.5 / 12.5 | The benchmark compares a filter of `2^k` bits against one of `2^k + 64` bits, which hold practically the same number of bits but take the masking and the modulo path respectively. As a control, the same benchmark on unmodified `master` puts the two within 1-3% of each other for every case above, so the gap is the change rather than the bit size shape. The non power of two cases are unchanged by this PR, as expected. These numbers are from an Apple silicon machine, whose divider is comparatively fast; the benchmark result files are not regenerated here, since that should happen on the standard benchmark hardware. ### Does this PR introduce _any_ user-facing change? No. The bit indices, and therefore the contents of every bloom filter, are identical to before. ### How was this patch tested? New `BloomFilterBitIndexSuite`, which pins down the equivalence the change rests on: - the mask is set exactly for power of two bit sizes, including the rounding up to whole words, - the mask survives a `BitArray` write/read round trip, - `bitIndex(hash, bitSize, mask) == hash % bitSize` for 10000 random hashes plus the edge values, over both power of two and non power of two bit sizes, for the `long` and the `int` overload, and for a bit size beyond the int range. New cases in `BloomFilterSuite` covering V1 and V2 against a power of two and a non power of two bit size: no false negatives, plus a serialization round trip. Existing suites: `sketch/test` (44 tests) and `BloomFilterAggregateQuerySuite` (11 tests) pass. Benchmark cases added to `SparkBloomFilterBenchmark`; the result files should be regenerated through the GitHub Actions benchmark workflow for a consistent environment. ### Was this patch authored or co-authored using generative AI tooling? Generated-by: Claude Code (Claude Opus 5) -- 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] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
