You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "rabenhorst (via GitHub)" <gi...@apache.org> on 2026/05/05 14:12:53 UTC
[PR] Pre-size dedup HashTable in GenericByteDictionaryBuilder::with_capacity [arrow-rs]
rabenhorst opened a new pull request, #9908:
URL: https://github.com/apache/arrow-rs/pull/9908
# Which issue does this PR close?
- Closes #9907.
# Rationale for this change
`GenericByteDictionaryBuilder::with_capacity` left the internal `dedup` `HashTable` at default capacity (0), forcing 0 → 4 → 8 → 16 → 32 → 64 → … resize+rehash cycles on the first inserts even when callers passed a non-zero `value_capacity`.
`new()` already sizes `dedup` from `keys_builder.capacity()`; `with_capacity` (the variant intended to amortize allocations) should do the same from `value_capacity`. As-is, callers reaching for `with_capacity` to avoid alloc churn get the opposite of what they asked for on the dedup path.
See #9907 for the full context including a CPU profile showing `GenericByteDictionaryBuilder::append` at 7.24% cum where ~half is the resize+rehash cost on the first batch.
# What changes are included in this PR?
- `arrow-array/src/builder/generic_bytes_dictionary_builder.rs`: change `dedup: Default::default()` to `dedup: HashTable::with_capacity(value_capacity)` in `with_capacity`. One-line behavioral change.
- Regression test `test_with_capacity_presizes_dedup` asserting `dedup.capacity() >= value_capacity` after construction.
This fixes `StringDictionaryBuilder`, `BinaryDictionaryBuilder`, and the `Large*` variants (all type aliases over `GenericByteDictionaryBuilder`).
# Are these changes tested?
Yes. New test in `arrow-array/src/builder/generic_bytes_dictionary_builder.rs::tests`:
```rust
#[test]
fn test_with_capacity_presizes_dedup() {
// `with_capacity` must size the dedup `HashTable` from `value_capacity`,
// otherwise the first inserts force a chain of resize+rehash cycles.
let value_capacity = 128;
let builder =
GenericByteDictionaryBuilder::<Int32Type, GenericStringType<i32>>::with_capacity(
256,
value_capacity,
value_capacity * 32,
);
assert!(
builder.dedup.capacity() >= value_capacity,
"dedup HashTable not pre-sized: got capacity {}, expected >= {}",
builder.dedup.capacity(),
value_capacity,
);
}
```
Verified the test fails on unpatched `main` (`got capacity 0, expected >= 128`) and passes with the fix. Full `generic_bytes_dictionary_builder` test suite (17 tests) still passes. `cargo clippy --lib -- -D warnings` is clean.
I did not add a benchmark — the asymptotic behavior is what matters here (eliminating O(value_capacity) resize+rehash work on first use), and the existing arrow-rs benchmark suite already exercises dictionary builders. Happy to add one if reviewers prefer.
# Are there any user-facing changes?
No public API changes. Behavior change is strictly an allocation/perf improvement: callers of `with_capacity` who previously got a zero-capacity dedup table now get one sized to `value_capacity`. This means a slightly larger upfront allocation in exchange for avoiding the resize+rehash chain. Callers passing very large `value_capacity` values intentionally to hint the values buffer (but not expecting to insert that many distinct values) will now also pre-allocate that much dedup capacity — this matches the documented contract of the parameter (`"the number of distinct dictionary values"`).
---
## AI-assisted submission disclosure
Per `CONTRIBUTING.md` — this PR was prepared with AI assistance (Claude). The bug was found while profiling a downstream Arrow producer; the fix and regression test were reviewed and verified locally. The change is one line plus a focused test, and I am happy to debug and own follow-ups.
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Pre-size dedup HashTable in GenericByteDictionaryBuilder::with_capacity [arrow-rs]
Posted by "rabenhorst (via GitHub)" <gi...@apache.org>.
rabenhorst commented on PR #9908:
URL: https://github.com/apache/arrow-rs/pull/9908#issuecomment-4381537330
Thanks @etseidl @alamb — sharing the cleanest before/after we have. Rather than a synthetic microbenchmark we captured two 30-minute CPU profiles against the same workload, once with stock `arrow-array` 58.1.0 (the latest published release at the time, which has the bug), and once with this PR's branch pulled in via `[patch.crates-io]`.
### Setup
Workload: Arrow producer encoding OTel span data into dict-encoded `StringDictionaryBuilder` columns. ~50–500 unique values per column per batch, batches of ~1k rows — exactly the regime where the unpatched dedup HashTable resizes 0 → 4 → 8 → 16 → 32 → 64 on the first inserts.
Profile sample counts are comparable: 49,535 (unpatched) vs 50,718 (patched).
### Results (% of total CPU)
| Frame | Unpatched 58.1.0 | This PR | Δ |
|---|---|---|---|
| `GenericByteDictionaryBuilder::append` cum | 7.24% | **5.11%** | **−29%** |
| `GenericByteDictionaryBuilder::append` flat (self) | 3.29% | **0.72%** | **−78%** |
| └─ `RawVec::grow_one` (child of append) | 0.28% | 0.16% | −43% |
| └─ `HashTable::entry` (child of append) | 1.79% | 2.71% | +51% |
| └─ `ahash::RandomState::hash_one` (child) | 0.73% | 1.17% | +60% |
### Reading
- The clearest signal is `append`'s **flat self-time** dropping 78% (3.29% → 0.72% of total CPU). That self-time was the resize+rehash bookkeeping happening in `append`'s own frame on the unpatched build — exactly what pre-sizing the dedup eliminates.
- `RawVec::grow_one` drops 43%. The residual is likely the values builder's own buffer growth (`data_capacity`), which this PR doesn't touch.
- `HashTable::entry` and `hash_one` go **up** in absolute share because, with the resize churn gone, the same CPU budget processes more events, so steady-state probe + hash work grows proportionally. Within `append`, the two go from ~35% → ~76% of cum — the "nothing left to optimize cheaply" shape; what remains is the unavoidable SIMD-accelerated probe + hash.
- Net: ~2 pp of total CPU recovered on this workload.
Happy to add a criterion microbenchmark too if it would help — the asymptotic story is straightforward (pre-sizing eliminates the O(value_capacity) resize+rehash chain on the first batch through each builder), but a synthetic bench could make it reproducible against the existing arrow-array bench suite.
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Pre-size dedup HashTable in GenericByteDictionaryBuilder::with_capacity [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #9908:
URL: https://github.com/apache/arrow-rs/pull/9908#issuecomment-4382014092
> Happy to add a criterion microbenchmark too if it would help — the asymptotic story is straightforward (pre-sizing eliminates the O(value_capacity) resize+rehash chain on the first batch through each builder), but a synthetic bench could make it reproducible against the existing arrow-array bench suite.
The value of a micro benchmark would be that we could potentially catch regressions. However, that also relies on us remembering to run the relevant benchmarks; I personally think not adding a micro benchmark is fine
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Pre-size dedup HashTable in GenericByteDictionaryBuilder::with_capacity [arrow-rs]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan merged PR #9908:
URL: https://github.com/apache/arrow-rs/pull/9908
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org