zeroshade opened a new pull request, #1378:
URL: https://github.com/apache/arrow-go/pull/1378
### Rationale for this change
`parquet/metadata/bloom_filter.go` had two `// TODO: replace with bitset run
reader pool` comments in `GetSpacedHashes` / `InsertSpacedHashes`. Profiling
shows the set-bit run reader isn't the cost: it is inlined and devirtualized,
so it already stays on the stack and pooling it would add overhead for nothing.
The real per-call cost is the ~32KiB of batching scratch (`byteBatch`,
`rawBatch`, `hashBatch`) declared in `GetHashes`, `InsertHashes`,
`GetSpacedHashes` and `InsertSpacedHashes`. Those buffers are passed through
the `Hasher` / `BloomFilterBuilder` interfaces, so they escape: **2 allocations
/ ~35KiB per call regardless of input size**. Small calls (e.g. 64 values) paid
~5.5µs of mostly allocation and zeroing to hash 64 values.
### What changes are included in this PR?
- Move the scratch into a `sync.Pool`-backed `hashScratch` used by all four
batched helpers.
- Before returning scratch to the pool, clear the `byteBatch` entries that
may reference caller data, so pooled scratch doesn't keep caller byte arrays
alive.
- Remove the two run-reader TODOs (see rationale).
- Add `BenchmarkBloomFilterSpacedHashes` (get/insert × 64/1024/100000 values
× all-valid/alternating/random validity).
### Are these changes tested?
Covered by the existing bloom filter tests (`go test ./parquet/...` passes,
`-race` on `parquet/metadata` passes). Benchmarks, count=10, benchstat, Intel
Core Ultra 7 155H:
| Benchmark | old | new | Δ time | allocs old → new |
|---|---|---|---|---|
| SpacedHashes/insert/64/all-true | 5.52µs | 311ns | -94.4% | 2 → 0 |
| SpacedHashes/get/64/random | 5.50µs | 474ns | -91.4% | 3 → 1 |
| SpacedHashes/insert/1024/random | 13.0µs | 5.67µs | -56.6% | 2 → 0 |
| SpacedHashes/get/1024/alternating | 15.7µs | 9.06µs | -42.3% | 3 → 1 |
| SpacedHashes/insert/100000/all-true | 430µs | 406µs | -5.4% | 2 → 0 |
| HashBatching/bounded (InsertHashes, 100k) | 426µs | 402µs | -5.6% | 2 → 0 |
| file: WriteDictionaryBloomFilter/int32/card=10000 | 2.15ms | 1.46ms |
-31.9% | 403 → 207 |
| file: WriteDictionaryBloomFilter/byte_array/card=1000 | 4.13ms | 3.74ms |
-9.4% | 452 → 253 |
The end-to-end writer benchmark also drops B/op by 54% (int32) and 24%
(byte_array) at cardinality ≥ 1000. Low-cardinality cases are unchanged (p >
0.05). Micro-benchmark geomean: -63% time.
<details><summary>Full benchstat</summary>
```
goos: linux
goarch: amd64
pkg: github.com/apache/arrow-go/v18/parquet/file
cpu: Intel(R) Core(TM) Ultra 7 155H
│
/tmp/bloom_old.txt │ /tmp/bloom_new.txt │
│ sec/op
│ sec/op vs base │
WriteDictionaryBloomFilter/int32/cardinality=1-22 1.279m ±
4% 1.225m ± 6% -4.22% (p=0.029 n=10)
WriteDictionaryBloomFilter/byte_array/cardinality=1-22 1.929m ±
7% 1.952m ± 2% ~ (p=1.000 n=10)
WriteDictionaryBloomFilter/int32/cardinality=10-22 1.473m ±
2% 1.471m ± 7% ~ (p=0.912 n=10)
WriteDictionaryBloomFilter/byte_array/cardinality=10-22 2.434m ±
2% 2.441m ± 4% ~ (p=0.218 n=10)
WriteDictionaryBloomFilter/int32/cardinality=100-22 1.455m ±
5% 1.453m ± 4% ~ (p=0.684 n=10)
WriteDictionaryBloomFilter/byte_array/cardinality=100-22 2.717m ±
4% 2.751m ± 1% ~ (p=0.579 n=10)
WriteDictionaryBloomFilter/int32/cardinality=1000-22 2.102m ±
4% 1.444m ± 5% -31.30% (p=0.000 n=10)
WriteDictionaryBloomFilter/byte_array/cardinality=1000-22 4.131m ±
3% 3.742m ± 4% -9.41% (p=0.000 n=10)
WriteDictionaryBloomFilter/int32/cardinality=10000-22 2.149m ±
7% 1.464m ± 3% -31.85% (p=0.000 n=10)
WriteDictionaryBloomFilter/byte_array/cardinality=10000-22 4.163m ±
5% 3.855m ± 3% -7.38% (p=0.000 n=10)
geomean 2.205m
2.005m -9.09%
│ /tmp/bloom_old.txt │
/tmp/bloom_new.txt │
│ B/s │
B/s vs base │
WriteDictionaryBloomFilter/int32/cardinality=1-22 298.3Mi ± 4%
311.5Mi ± 5% +4.41% (p=0.029 n=10)
WriteDictionaryBloomFilter/int32/cardinality=10-22 258.9Mi ± 2%
259.3Mi ± 7% ~ (p=0.927 n=10)
WriteDictionaryBloomFilter/int32/cardinality=100-22 262.3Mi ± 6%
262.5Mi ± 3% ~ (p=0.684 n=10)
WriteDictionaryBloomFilter/int32/cardinality=1000-22 181.5Mi ± 4%
264.2Mi ± 5% +45.57% (p=0.000 n=10)
WriteDictionaryBloomFilter/int32/cardinality=10000-22 177.5Mi ± 7%
260.5Mi ± 4% +46.74% (p=0.000 n=10)
geomean 230.6Mi
270.9Mi +17.46%
│
/tmp/bloom_old.txt │ /tmp/bloom_new.txt │
│ B/op
│ B/op vs base │
WriteDictionaryBloomFilter/int32/cardinality=1-22 1.103Mi ±
0% 1.104Mi ± 0% ~ (p=0.529 n=10)
WriteDictionaryBloomFilter/byte_array/cardinality=1-22 596.0Ki ±
0% 596.1Ki ± 0% ~ (p=0.684 n=10)
WriteDictionaryBloomFilter/int32/cardinality=10-22 1.310Mi ±
0% 1.310Mi ± 0% ~ (p=1.000 n=10)
WriteDictionaryBloomFilter/byte_array/cardinality=10-22 808.3Ki ±
0% 808.5Ki ± 0% ~ (p=0.481 n=10)
WriteDictionaryBloomFilter/int32/cardinality=100-22 1.447Mi ±
0% 1.447Mi ± 0% ~ (p=0.739 n=10)
WriteDictionaryBloomFilter/byte_array/cardinality=100-22 987.8Ki ±
0% 988.1Ki ± 0% ~ (p=0.143 n=10)
WriteDictionaryBloomFilter/int32/cardinality=1000-22 6.040Mi ±
0% 2.785Mi ± 0% -53.90% (p=0.000 n=10)
WriteDictionaryBloomFilter/byte_array/cardinality=1000-22 13.59Mi ±
0% 10.35Mi ± 0% -23.84% (p=0.000 n=10)
WriteDictionaryBloomFilter/int32/cardinality=10000-22 6.056Mi ±
0% 2.802Mi ± 0% -53.73% (p=0.000 n=10)
WriteDictionaryBloomFilter/byte_array/cardinality=10000-22 13.61Mi ±
0% 10.37Mi ± 0% -23.81% (p=0.000 n=10)
geomean 2.397Mi
1.945Mi -18.85%
│
/tmp/bloom_old.txt │ /tmp/bloom_new.txt │
│ allocs/op
│ allocs/op vs base │
WriteDictionaryBloomFilter/int32/cardinality=1-22 184.0 ±
1% 184.0 ± 1% ~ (p=1.000 n=10)
WriteDictionaryBloomFilter/byte_array/cardinality=1-22 207.0 ±
0% 207.0 ± 0% ~ (p=1.000 n=10) ¹
WriteDictionaryBloomFilter/int32/cardinality=10-22 189.0 ±
0% 189.0 ± 0% ~ (p=1.000 n=10) ¹
WriteDictionaryBloomFilter/byte_array/cardinality=10-22 215.0 ±
0% 215.0 ± 0% ~ (p=1.000 n=10) ¹
WriteDictionaryBloomFilter/int32/cardinality=100-22 194.0 ±
1% 194.0 ± 1% ~ (p=0.450 n=10)
WriteDictionaryBloomFilter/byte_array/cardinality=100-22 227.0 ±
0% 227.0 ± 0% ~ (p=1.000 n=10) ¹
WriteDictionaryBloomFilter/int32/cardinality=1000-22 403.0 ±
0% 207.0 ± 0% -48.64% (p=0.000 n=10)
WriteDictionaryBloomFilter/byte_array/cardinality=1000-22 452.0 ±
0% 253.0 ± 0% -44.03% (p=0.000 n=10)
WriteDictionaryBloomFilter/int32/cardinality=10000-22 403.0 ±
0% 207.0 ± 0% -48.64% (p=0.000 n=10)
WriteDictionaryBloomFilter/byte_array/cardinality=10000-22 549.0 ±
1% 338.5 ± 1% -38.34% (p=0.000 n=10)
geomean 277.9
218.7 -21.31%
¹ all samples are equal
pkg: github.com/apache/arrow-go/v18/parquet/metadata
│ /tmp/bloom_old.txt │
/tmp/bloom_new.txt │
│ sec/op │
sec/op vs base │
BloomFilterHashBatching/materialized-22 666.7µ ± 3%
651.6µ ± 7% ~ (p=0.247 n=10)
BloomFilterHashBatching/bounded-22 426.1µ ± 2%
402.3µ ± 1% -5.56% (p=0.000 n=10)
BloomFilterSpacedHashes/get/64/all-true-22 5683.5n ± 15%
441.9n ± 4% -92.22% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/64/all-true-22 5518.5n ± 4%
310.8n ± 1% -94.37% (p=0.000 n=10)
BloomFilterSpacedHashes/get/64/alternating-22 5800.5n ± 2%
590.9n ± 2% -89.81% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/64/alternating-22 5764.5n ± 5%
509.5n ± 1% -91.16% (p=0.000 n=10)
BloomFilterSpacedHashes/get/64/random-22 5497.0n ± 4%
474.1n ± 2% -91.38% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/64/random-22 5614.5n ± 2%
372.0n ± 0% -93.37% (p=0.000 n=10)
BloomFilterSpacedHashes/get/1024/all-true-22 12.481µ ± 3%
6.142µ ± 3% -50.79% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/1024/all-true-22 11.431µ ± 3%
4.265µ ± 2% -62.69% (p=0.000 n=10)
BloomFilterSpacedHashes/get/1024/alternating-22 15.682µ ± 3%
9.056µ ± 1% -42.25% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/1024/alternating-22 15.682µ ± 6%
7.711µ ± 0% -50.83% (p=0.000 n=10)
BloomFilterSpacedHashes/get/1024/random-22 13.093µ ± 3%
6.846µ ± 3% -47.71% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/1024/random-22 13.044µ ± 5%
5.667µ ± 1% -56.55% (p=0.000 n=10)
BloomFilterSpacedHashes/get/100000/all-true-22 572.9µ ± 4%
512.0µ ± 4% -10.63% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/100000/all-true-22 429.5µ ± 3%
406.2µ ± 6% -5.43% (p=0.009 n=10)
BloomFilterSpacedHashes/get/100000/alternating-22 888.4µ ± 1%
877.9µ ± 2% ~ (p=0.089 n=10)
BloomFilterSpacedHashes/insert/100000/alternating-22 764.4µ ± 2%
745.4µ ± 2% -2.48% (p=0.001 n=10)
BloomFilterSpacedHashes/get/100000/random-22 761.7µ ± 2%
743.6µ ± 2% -2.38% (p=0.019 n=10)
BloomFilterSpacedHashes/insert/100000/random-22 664.8µ ± 2%
649.8µ ± 1% -2.26% (p=0.000 n=10)
geomean 48.24µ
17.68µ -63.35%
│ /tmp/bloom_old.txt │
/tmp/bloom_new.txt │
│ B/s │
B/s vs base │
BloomFilterHashBatching/materialized-22 572.2Mi ± 3%
585.4Mi ± 7% ~ (p=0.247 n=10)
BloomFilterHashBatching/bounded-22 895.4Mi ± 2%
948.1Mi ± 1% +5.89% (p=0.000 n=10)
BloomFilterSpacedHashes/get/64/all-true-22 42.98Mi ± 13%
552.44Mi ± 4% +1185.28% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/64/all-true-22 44.24Mi ± 4%
785.75Mi ± 1% +1676.07% (p=0.000 n=10)
BloomFilterSpacedHashes/get/64/alternating-22 42.09Mi ± 2%
413.18Mi ± 2% +881.66% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/64/alternating-22 42.35Mi ± 5%
479.16Mi ± 1% +1031.37% (p=0.000 n=10)
BloomFilterSpacedHashes/get/64/random-22 44.41Mi ± 4%
515.01Mi ± 2% +1059.61% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/64/random-22 43.49Mi ± 2%
656.24Mi ± 0% +1409.02% (p=0.000 n=10)
BloomFilterSpacedHashes/get/1024/all-true-22 313.0Mi ± 3%
636.0Mi ± 3% +103.18% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/1024/all-true-22 341.7Mi ± 3%
916.0Mi ± 2% +168.03% (p=0.000 n=10)
BloomFilterSpacedHashes/get/1024/alternating-22 249.1Mi ± 3%
431.3Mi ± 1% +73.16% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/1024/alternating-22 249.1Mi ± 6%
506.6Mi ± 0% +103.38% (p=0.000 n=10)
BloomFilterSpacedHashes/get/1024/random-22 298.4Mi ± 3%
570.6Mi ± 3% +91.24% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/1024/random-22 299.5Mi ± 5%
689.3Mi ± 1% +130.18% (p=0.000 n=10)
BloomFilterSpacedHashes/get/100000/all-true-22 665.9Mi ± 4%
745.1Mi ± 4% +11.90% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/100000/all-true-22 888.1Mi ± 3%
939.1Mi ± 6% +5.74% (p=0.009 n=10)
BloomFilterSpacedHashes/get/100000/alternating-22 429.4Mi ± 1%
434.5Mi ± 2% ~ (p=0.089 n=10)
BloomFilterSpacedHashes/insert/100000/alternating-22 499.0Mi ± 2%
511.7Mi ± 2% +2.55% (p=0.001 n=10)
BloomFilterSpacedHashes/get/100000/random-22 500.8Mi ± 2%
513.0Mi ± 2% +2.43% (p=0.019 n=10)
BloomFilterSpacedHashes/insert/100000/random-22 573.8Mi ± 2%
587.1Mi ± 1% +2.31% (p=0.000 n=10)
geomean 220.3Mi
601.0Mi +172.83%
│ /tmp/bloom_old.txt │
/tmp/bloom_new.txt │
│ B/op │
B/op vs base │
BloomFilterHashBatching/materialized-22 818.6Ki ± 0%
786.1Ki ± 0% -3.97% (p=0.000 n=10)
BloomFilterHashBatching/bounded-22 35456.000 ± 0%
1.000 ± 1300% -100.00% (p=0.000 n=10)
BloomFilterSpacedHashes/get/64/all-true-22 35968.0 ± 0%
515.0 ± 0% -98.57% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/64/all-true-22 34.62Ki ± 0%
0.00Ki ± 0% -100.00% (p=0.000 n=10)
BloomFilterSpacedHashes/get/64/alternating-22 35712.0 ± 0%
257.0 ± 0% -99.28% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/64/alternating-22 34.62Ki ± 0%
0.00Ki ± 0% -100.00% (p=0.000 n=10)
BloomFilterSpacedHashes/get/64/random-22 35744.0 ± 0%
289.0 ± 0% -99.19% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/64/random-22 34.62Ki ± 0%
0.00Ki ± 0% -100.00% (p=0.000 n=10)
BloomFilterSpacedHashes/get/1024/all-true-22 42.625Ki ± 0%
8.029Ki ± 0% -81.16% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/1024/all-true-22 34.62Ki ± 0%
0.00Ki ± 0% -100.00% (p=0.000 n=10)
BloomFilterSpacedHashes/get/1024/alternating-22 38.625Ki ± 0%
4.008Ki ± 0% -89.62% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/1024/alternating-22 34.62Ki ± 0%
0.00Ki ± 0% -100.00% (p=0.000 n=10)
BloomFilterSpacedHashes/get/1024/random-22 39.375Ki ± 0%
4.762Ki ± 0% -87.91% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/1024/random-22 34.62Ki ± 0%
0.00Ki ± 0% -100.00% (p=0.000 n=10)
BloomFilterSpacedHashes/get/100000/all-true-22 818.6Ki ± 0%
786.6Ki ± 0% -3.92% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/100000/all-true-22 35456.000 ± 0%
1.000 ± 1300% -100.00% (p=0.000 n=10)
BloomFilterSpacedHashes/get/100000/alternating-22 426.6Ki ± 0%
392.5Ki ± 0% -7.99% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/100000/alternating-22 35456.00 ± 0%
27.00 ± 96% -99.92% (p=0.000 n=10)
BloomFilterSpacedHashes/get/100000/random-22 426.6Ki ± 0%
392.6Ki ± 0% -7.97% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/100000/random-22 35456.00 ± 0%
12.00 ± 100% -99.97% (p=0.000 n=10)
geomean 62.54Ki
? ¹ ²
¹ summaries must be >0 to compute geomean
² ratios must be >0 to compute geomean
│ /tmp/bloom_old.txt │
/tmp/bloom_new.txt │
│ allocs/op │
allocs/op vs base │
BloomFilterHashBatching/materialized-22 3.000 ± 0%
1.000 ± 0% -66.67% (p=0.000 n=10)
BloomFilterHashBatching/bounded-22 2.000 ± 0%
0.000 ± 0% -100.00% (p=0.000 n=10)
BloomFilterSpacedHashes/get/64/all-true-22 3.000 ± 0%
1.000 ± 0% -66.67% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/64/all-true-22 2.000 ± 0%
0.000 ± 0% -100.00% (p=0.000 n=10)
BloomFilterSpacedHashes/get/64/alternating-22 3.000 ± 0%
1.000 ± 0% -66.67% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/64/alternating-22 2.000 ± 0%
0.000 ± 0% -100.00% (p=0.000 n=10)
BloomFilterSpacedHashes/get/64/random-22 3.000 ± 0%
1.000 ± 0% -66.67% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/64/random-22 2.000 ± 0%
0.000 ± 0% -100.00% (p=0.000 n=10)
BloomFilterSpacedHashes/get/1024/all-true-22 3.000 ± 0%
1.000 ± 0% -66.67% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/1024/all-true-22 2.000 ± 0%
0.000 ± 0% -100.00% (p=0.000 n=10)
BloomFilterSpacedHashes/get/1024/alternating-22 3.000 ± 0%
1.000 ± 0% -66.67% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/1024/alternating-22 2.000 ± 0%
0.000 ± 0% -100.00% (p=0.000 n=10)
BloomFilterSpacedHashes/get/1024/random-22 3.000 ± 0%
1.000 ± 0% -66.67% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/1024/random-22 2.000 ± 0%
0.000 ± 0% -100.00% (p=0.000 n=10)
BloomFilterSpacedHashes/get/100000/all-true-22 3.000 ± 0%
1.000 ± 0% -66.67% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/100000/all-true-22 2.000 ± 0%
0.000 ± 0% -100.00% (p=0.000 n=10)
BloomFilterSpacedHashes/get/100000/alternating-22 3.000 ± 0%
1.000 ± 0% -66.67% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/100000/alternating-22 2.000 ± 0%
0.000 ± 0% -100.00% (p=0.000 n=10)
BloomFilterSpacedHashes/get/100000/random-22 3.000 ± 0%
1.000 ± 0% -66.67% (p=0.000 n=10)
BloomFilterSpacedHashes/insert/100000/random-22 2.000 ± 0%
0.000 ± 0% -100.00% (p=0.000 n=10)
geomean 2.449
? ¹ ²
¹ summaries must be >0 to compute geomean
² ratios must be >0 to compute geomean
```
</details>
### Are there any user-facing changes?
No API changes; performance only.
--
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]
