Hi all, I opened a PR last week that has not picked up a reviewer yet. I would appreciate a look, or a pointer to the right people for common/sketch.
JIRA: https://issues.apache.org/jira/browse/SPARK-56548 PR: https://github.com/apache/spark/pull/58551 Both bloom filter implementations reduce a hash to a bit index with "hash % bitSize", once per hash function, in the innermost loop of put and mightContain. Since bitSize is a field rather than a compile time constant, that is 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, and the Spark SQL runtime bloom filter sizes are powers of two in particular (spark.sql.optimizer.runtime.bloomFilter.numBits defaults to 2^23, and maxNumBits to 2^26). The PR caches "bitSize - 1" as a mask when the bit size is a power of two and masks instead of dividing, falling back to the modulo otherwise. 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. On power of two sizes, put goes from 36.2 to ~29 ns/row at 2^20 bits and mightContain from 14.4 to 13.1 ns/row; the full before/after table is in the PR description, along with a control run on unmodified master showing the two bit size shapes within 1-3% of each other before the change. A new BloomFilterBitIndexSuite pins down the "bitIndex == hash % bitSize" equivalence the change rests on, across both overloads and both bit size shapes. Thanks, Vivek
