This is an automated email from the ASF dual-hosted git repository.
zeroshade pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/arrow-go.git
The following commit(s) were added to refs/heads/main by this push:
new a8af7331 perf(parquet): reuse boolean Bloom filter hashes (#1258)
a8af7331 is described below
commit a8af7331d9fe6addf0d271b7cca005a47edb877c
Author: Minh Vu <[email protected]>
AuthorDate: Mon Aug 31 22:38:51 2026 +0200
perf(parquet): reuse boolean Bloom filter hashes (#1258)
## What
- Precompute the xxHash values for `false` (`[]byte{0}`) and `true`
(`[]byte{1}`).
- Reuse them in dense and spaced boolean bitmap Bloom-filter paths.
- Keep custom `Hasher` implementations on the existing path.
This removes a `Sum64` call for every boolean while keeping the same
hash values.
## Benchmark
Apple M1 Pro, Go 1.26.3, 7 samples, one CPU:
`go test -vet=off ./parquet/metadata -run '^$' -bench
'^BenchmarkBloomFilter(HashingFromBitmap|BooleanBitmap)' -benchmem
-benchtime=150ms -count=7 -cpu=1`
The benchmark matrix covers 100K and 1M booleans, all false, all true,
alternating, random, and spaced values with 10% and 50% nulls.
Median results for alternating values:
| Case | Before | After |
| --- | --- | --- |
| Hash, 100K | 636.0 us, 802,819 B/op, 2 allocs | 181.6 us, 802,816
B/op, 1 alloc |
| Insert, 100K | 1.840 ms, 8,193 B/op, 2 allocs | 943.3 us, 8,193 B/op,
2 allocs |
| Hash, 1M | 7.206 ms, 8,003,596 B/op, 2 allocs | 1.510 ms, 8,003,584
B/op, 1 alloc |
| Insert, 1M | 18.832 ms, 8,193 B/op, 2 allocs | 9.767 ms, 8,193 B/op, 2
allocs |
For alternating data, hashing is 3.5x to 4.8x faster and insertion is
about 1.9x faster.
## Tests
- `go test ./parquet/metadata`
- `PARQUET_TEST_DATA="$PWD/parquet-testing/data" go test ./...`
- `go vet ./parquet/metadata`
---
parquet/metadata/bitmap_benchmark_test.go | 123 ++++++++++++++++++++++++++++
parquet/metadata/bloom_filter.go | 84 ++++++++++++++++++-
parquet/metadata/bloom_filter_batch_test.go | 43 ++++++++++
3 files changed, 248 insertions(+), 2 deletions(-)
diff --git a/parquet/metadata/bitmap_benchmark_test.go
b/parquet/metadata/bitmap_benchmark_test.go
index 773954e7..79339b8d 100644
--- a/parquet/metadata/bitmap_benchmark_test.go
+++ b/parquet/metadata/bitmap_benchmark_test.go
@@ -17,6 +17,7 @@
package metadata
import (
+ "fmt"
"testing"
"github.com/apache/arrow-go/v18/arrow/bitutil"
@@ -69,6 +70,128 @@ func BenchmarkBloomFilterHashingFromBitmap(b *testing.B) {
}
}
+// BenchmarkBloomFilterBooleanBitmap benchmarks dense and spaced boolean bloom
filter paths
+// with the built-in xxhash implementation.
+func BenchmarkBloomFilterBooleanBitmap(b *testing.B) {
+ for _, numValues := range []int{100_000, 1_000_000} {
+ numValues := numValues
+ for _, tc := range benchmarkBooleanBitmapCases(numValues) {
+ tc := tc
+ b.Run(fmt.Sprintf("hash/%d/%s", numValues, tc.name),
func(b *testing.B) {
+ bloom := NewBloomFilter(1024, 1024,
memory.DefaultAllocator)
+ b.ReportAllocs()
+ b.ResetTimer()
+
+ for i := 0; i < b.N; i++ {
+ _ = GetHashesFromBitmap(bloom.Hasher(),
tc.bitmap, 0, int64(numValues))
+ }
+ })
+
+ b.Run(fmt.Sprintf("insert/%d/%s", numValues, tc.name),
func(b *testing.B) {
+ bloom := NewBloomFilter(1024, 1024,
memory.DefaultAllocator)
+ b.ReportAllocs()
+ b.ResetTimer()
+
+ for i := 0; i < b.N; i++ {
+ InsertHashesFromBitmap(bloom,
tc.bitmap, 0, int64(numValues))
+ }
+ })
+ }
+
+ for _, tc := range benchmarkSpacedBooleanBitmapCases(numValues)
{
+ tc := tc
+ b.Run(fmt.Sprintf("spaced-hash/%d/%s", numValues,
tc.name), func(b *testing.B) {
+ bloom := NewBloomFilter(1024, 1024,
memory.DefaultAllocator)
+ b.ReportAllocs()
+ b.ResetTimer()
+
+ for i := 0; i < b.N; i++ {
+ _ =
GetSpacedHashesFromBitmap(bloom.Hasher(), tc.numValid, tc.bitmap, 0,
int64(numValues), tc.validBits, 0)
+ }
+ })
+
+ b.Run(fmt.Sprintf("spaced-insert/%d/%s", numValues,
tc.name), func(b *testing.B) {
+ bloom := NewBloomFilter(1024, 1024,
memory.DefaultAllocator)
+ b.ReportAllocs()
+ b.ResetTimer()
+
+ for i := 0; i < b.N; i++ {
+ InsertSpacedHashesFromBitmap(bloom,
tc.numValid, tc.bitmap, 0, int64(numValues), tc.validBits, 0)
+ }
+ })
+ }
+ }
+}
+
+type benchmarkBooleanBitmapCase struct {
+ name string
+ bitmap []byte
+ validBits []byte
+ numValid int64
+}
+
+func benchmarkBooleanBitmapCases(numValues int) []benchmarkBooleanBitmapCase {
+ patterns := []string{"all-false", "all-true", "alternating", "random"}
+ cases := make([]benchmarkBooleanBitmapCase, 0, len(patterns))
+ for _, pattern := range patterns {
+ cases = append(cases, benchmarkBooleanBitmapCase{
+ name: pattern,
+ bitmap: makeBenchmarkBooleanBitmap(numValues, pattern),
+ })
+ }
+ return cases
+}
+
+func benchmarkSpacedBooleanBitmapCases(numValues int)
[]benchmarkBooleanBitmapCase {
+ bitmap := makeBenchmarkBooleanBitmap(numValues, "alternating")
+ cases := make([]benchmarkBooleanBitmapCase, 0, 2)
+ for _, tc := range []struct {
+ name string
+ nullEvery int
+ }{
+ {name: "10pct-null", nullEvery: 10},
+ {name: "50pct-null", nullEvery: 2},
+ } {
+ validBits := make([]byte,
bitutil.BytesForBits(int64(numValues)))
+ var numValid int64
+ for i := 0; i < numValues; i++ {
+ if i%tc.nullEvery != 0 {
+ bitutil.SetBit(validBits, i)
+ numValid++
+ }
+ }
+ cases = append(cases, benchmarkBooleanBitmapCase{
+ name: tc.name,
+ bitmap: bitmap,
+ validBits: validBits,
+ numValid: numValid,
+ })
+ }
+ return cases
+}
+
+func makeBenchmarkBooleanBitmap(numValues int, pattern string) []byte {
+ bitmap := make([]byte, bitutil.BytesForBits(int64(numValues)))
+ var state uint64 = 0x9e3779b97f4a7c15
+ for i := 0; i < numValues; i++ {
+ set := false
+ switch pattern {
+ case "all-true":
+ set = true
+ case "alternating":
+ set = i%2 == 0
+ case "random":
+ state ^= state << 7
+ state ^= state >> 9
+ set = state&1 != 0
+ }
+ if set {
+ bitutil.SetBit(bitmap, i)
+ }
+ }
+ return bitmap
+}
+
// BenchmarkBloomFilterHashBatching compares the materialized and streaming
// paths used to update a bloom filter from a large fixed-width batch.
func BenchmarkBloomFilterHashBatching(b *testing.B) {
diff --git a/parquet/metadata/bloom_filter.go b/parquet/metadata/bloom_filter.go
index 842f8016..0dfbde9b 100644
--- a/parquet/metadata/bloom_filter.go
+++ b/parquet/metadata/bloom_filter.go
@@ -54,6 +54,9 @@ var (
0x47b6137b, 0x44974d91, 0x8824ad5b, 0xa2b7289d,
0x705495c7, 0x2df1424b, 0x9efc4947, 0x5c6bfb31}
+ booleanFalseHash = xxhash.Sum64([]byte{0})
+ booleanTrueHash = xxhash.Sum64([]byte{1})
+
defaultHashStrategy = format.BloomFilterHash{XXHASH: &format.XxHash{}}
defaultAlgorithm = format.BloomFilterAlgorithm{BLOCK:
&format.SplitBlockAlgorithm{}}
defaultCompression = format.BloomFilterCompression{UNCOMPRESSED:
&format.Uncompressed{}}
@@ -115,6 +118,13 @@ func (xxhasher) Sum64sInto(b [][]byte, vals []uint64) {
}
}
+func precomputedBooleanHashes(h Hasher) (falseHash, trueHash uint64, ok bool) {
+ if _, ok := h.(xxhasher); !ok {
+ return 0, 0, false
+ }
+ return booleanFalseHash, booleanTrueHash, true
+}
+
type sum64sIntoHasher interface {
Sum64sInto([][]byte, []uint64)
}
@@ -240,9 +250,20 @@ func GetHashesFromBitmap(h Hasher, bitmap []byte,
bitmapOffset int64, numValues
return []uint64{}
}
+ out := make([]uint64, numValues)
+ if falseHash, trueHash, ok := precomputedBooleanHashes(h); ok {
+ for i := range numValues {
+ if bitutil.BitIsSet(bitmap, int(bitmapOffset+i)) {
+ out[i] = trueHash
+ } else {
+ out[i] = falseHash
+ }
+ }
+ return out
+ }
+
// Convert each bool bit to []byte for hashing
// Reuse a single-byte slice to avoid allocating per value
- out := make([]uint64, numValues)
b := []byte{0}
for i := range numValues {
val := bitutil.BitIsSet(bitmap, int(bitmapOffset+i))
@@ -266,11 +287,30 @@ func GetSpacedHashesFromBitmap(h Hasher, numValid int64,
bitmap []byte, bitmapOf
}
out := make([]uint64, 0, numValid)
+ falseHash, trueHash, usePrecomputedHashes := precomputedBooleanHashes(h)
// Use SetBitRunReader to efficiently iterate over valid values
+ setReader := bitutils.NewSetBitRunReader(validBits, validBitsOffset,
numValues)
+ if usePrecomputedHashes {
+ for {
+ run := setReader.NextRun()
+ if run.Length == 0 {
+ break
+ }
+
+ for i := range run.Length {
+ if bitutil.BitIsSet(bitmap,
int(bitmapOffset+run.Pos+i)) {
+ out = append(out, trueHash)
+ } else {
+ out = append(out, falseHash)
+ }
+ }
+ }
+ return out
+ }
+
// Reuse a single-byte slice to avoid allocating per value
b := []byte{0}
- setReader := bitutils.NewSetBitRunReader(validBits, validBitsOffset,
numValues)
for {
run := setReader.NextRun()
if run.Length == 0 {
@@ -298,11 +338,27 @@ func InsertHashesFromBitmap(b BloomFilterBuilder, bitmap
[]byte, bitmapOffset in
}
h := b.Hasher()
+ falseHash, trueHash, usePrecomputedHashes := precomputedBooleanHashes(h)
var (
hashBatch [bloomFilterHashBatchSize]uint64
value [1]byte
)
+ if usePrecomputedHashes {
+ for offset := int64(0); offset < numValues; offset +=
bloomFilterHashBatchSize {
+ end := min(offset+int64(bloomFilterHashBatchSize),
numValues)
+ for i := offset; i < end; i++ {
+ if bitutil.BitIsSet(bitmap,
int(bitmapOffset+i)) {
+ hashBatch[i-offset] = trueHash
+ } else {
+ hashBatch[i-offset] = falseHash
+ }
+ }
+ b.InsertBulk(hashBatch[:end-offset])
+ }
+ return
+ }
+
for offset := int64(0); offset < numValues; offset +=
bloomFilterHashBatchSize {
end := min(offset+int64(bloomFilterHashBatchSize), numValues)
for i := offset; i < end; i++ {
@@ -324,12 +380,36 @@ func InsertSpacedHashesFromBitmap(b BloomFilterBuilder,
numValid int64, bitmap [
}
h := b.Hasher()
+ falseHash, trueHash, usePrecomputedHashes := precomputedBooleanHashes(h)
var (
hashBatch [bloomFilterHashBatchSize]uint64
value [1]byte
)
setReader := bitutils.NewSetBitRunReader(validBits, validBitsOffset,
numValues)
+ if usePrecomputedHashes {
+ for {
+ run := setReader.NextRun()
+ if run.Length == 0 {
+ break
+ }
+
+ runEnd := run.Pos + run.Length
+ for pos := run.Pos; pos < runEnd; pos +=
bloomFilterHashBatchSize {
+ end := min(pos+int64(bloomFilterHashBatchSize),
runEnd)
+ for i := pos; i < end; i++ {
+ if bitutil.BitIsSet(bitmap,
int(bitmapOffset+i)) {
+ hashBatch[i-pos] = trueHash
+ } else {
+ hashBatch[i-pos] = falseHash
+ }
+ }
+ b.InsertBulk(hashBatch[:end-pos])
+ }
+ }
+ return
+ }
+
for {
run := setReader.NextRun()
if run.Length == 0 {
diff --git a/parquet/metadata/bloom_filter_batch_test.go
b/parquet/metadata/bloom_filter_batch_test.go
index 932470ca..eee3078d 100644
--- a/parquet/metadata/bloom_filter_batch_test.go
+++ b/parquet/metadata/bloom_filter_batch_test.go
@@ -177,6 +177,49 @@ func TestInsertHashesFromBitmapBatchesValues(t *testing.T)
{
assert.Empty(t, empty.batches)
}
+func TestBitmapBloomHashingPreservesCustomHasher(t *testing.T) {
+ const (
+ numValues = bloomFilterHashBatchSize + 7
+ bitmapOffset = int64(3)
+ validOffset = int64(5)
+ )
+
+ bitmap := make([]byte, bitutil.BytesForBits(bitmapOffset+numValues))
+ validBits := make([]byte, bitutil.BytesForBits(validOffset+numValues))
+ var numValid int64
+ for i := 0; i < numValues; i++ {
+ if i%3 == 0 {
+ bitutil.SetBit(bitmap, int(bitmapOffset)+i)
+ }
+ if i%4 != 0 {
+ bitutil.SetBit(validBits, int(validOffset)+i)
+ numValid++
+ }
+ }
+
+ expectedDense := GetHashesFromBitmap(xxhasher{}, bitmap, bitmapOffset,
numValues)
+ hasher := &recordingHasher{}
+ assert.Equal(t, expectedDense, GetHashesFromBitmap(hasher, bitmap,
bitmapOffset, numValues))
+ assert.Len(t, hasher.inputs, numValues)
+
+ expectedSpaced := GetSpacedHashesFromBitmap(xxhasher{}, numValid,
bitmap, bitmapOffset, numValues, validBits, validOffset)
+ hasher = &recordingHasher{}
+ assert.Equal(t, expectedSpaced, GetSpacedHashesFromBitmap(hasher,
numValid, bitmap, bitmapOffset, numValues, validBits, validOffset))
+ assert.Len(t, hasher.inputs, int(numValid))
+
+ hasher = &recordingHasher{}
+ bloom := newBatchRecordingBloomFilter(hasher)
+ InsertHashesFromBitmap(bloom, bitmap, bitmapOffset, numValues)
+ assert.Equal(t, expectedDense, flattenHashBatches(bloom.batches))
+ assert.Len(t, hasher.inputs, numValues)
+
+ hasher = &recordingHasher{}
+ bloom = newBatchRecordingBloomFilter(hasher)
+ InsertSpacedHashesFromBitmap(bloom, numValid, bitmap, bitmapOffset,
numValues, validBits, validOffset)
+ assert.Equal(t, expectedSpaced, flattenHashBatches(bloom.batches))
+ assert.Len(t, hasher.inputs, int(numValid))
+}
+
func TestInsertSpacedHashesFromBitmapBatchesValidValues(t *testing.T) {
const (
numValues = 2*bloomFilterHashBatchSize + 19
