txwyy123 commented on PR #26149:
URL: https://github.com/apache/datafusion/pull/26149#issuecomment-6185683942
@jayzhan211 Final update on `column_count/64`. I spent the last two days
exhaustively testing alternative data structures to eliminate the overflow
regression. Here's the honest picture:
## Stable A/B benchmark (4 iterations each, same machine, back-to-back)
| Case | main (ns) | PR (ns) | Δ% |
|------|-----------|---------|-----|
| `column_count/1` | 17.3 | 18.9 | +9.6% (+1.6ns abs) |
| `column_count/4` | 59.3 | 55.8 | **−6.0%** ✅ |
| `column_count/16` | 259.5 | 262.7 | +1.2% |
| `column_count/64` | 2,042 | 2,258 | **+10.6%** (+216ns) |
| `row_count/*` | 58.4 | 53.7 | **−8.1%** ✅ |
| `layout/primitive` | 58.8 | 54.1 | **−8.0%** ✅ |
| `layout/list` | 131 | 121 | **−7.6%** ✅ |
| `layout/struct` | 175 | 162 | **−7.4%** ✅ |
| `shared_slices/4` | 1,769 | 1,676 | **−5.2%** ✅ |
| `shared_slices/16` | 8,447 | 9,063 | +7.3% |
| `shared_slices/64` | 33,558 | 35,146 | +4.7% |
My earlier comment showing −3.2% on `column_count/64` was a lucky
measurement — the regression is real at **+10%** and stable across multiple
runs. The earlier +7% report was also accurate; variance is ±3%.
## What I tried (and why nothing beats HashMap)
| # | Approach | column_count/64 | shared_slices/64 | Why it fails |
|---|---|---|---|---|
| 1 | **Sorted Vec** (binary search + insert) | **−16%** ✅ | **+32%** ❌ |
`Vec::insert` shifts up to 112 entries (73KB memcpy) on first-pass unique
insertions |
| 2 | **Lazy-sort Vec** (push + deferred sort) | **−12%** ✅ | **+47%** ❌ |
Linear scan of unsorted tail on every duplicate lookup |
| 3 | **Box\<enum{Set,Map}>** lazy upgrade | **−4%** ✅ | inline +8-14% ❌ |
Enum discriminant breaks `Option` niche opt → 8 bytes larger struct → all
inline cases regress |
| 4 | **Two separate Option fields** | same as #3 | same | 112 extra bytes
in struct, same inline regression |
| 5 | **HashSet + refcounts HashMap** | **0%** ✅ | **+34%** ❌ | Two hash
lookups per duplicate (Set check + refcounts insert) |
| 6 | **Inline capacity = 32** | **+27%** ❌ | +6% | `position()` linear scan
over 256 bytes (4 cache lines) too slow |
## Root cause (structural, not fixable)
`HashMap<NonZero<usize>, u32>` = **16 bytes/slot** (8-byte key + 4-byte
count + 4-byte alignment). `HashSet<NonZero<usize>>` = **8 bytes/slot**. This
doubles the hash table footprint and the number of cache lines touched per
probe. There is no way to fit both a `usize` key and a count in 8 bytes — every
alternative that avoids the 16-byte slot trades performance at a different
scale.
## Assessment
The +10% on `column_count/64` is the structural cost of refcounting. It
fires only when >16 **unique** buffers overflow the inline path (64 distinct
columns with no buffer sharing). In real operator workloads (sort, window,
join), batches are sliced from a parent — buffers are shared, not unique. The
`shared_slices/4` case (4 columns × 32 slices — the common operator pattern) is
**−5.2% faster** than main.
The inline path (≤16 unique buffers) is **6–8% faster** across the board
thanks to `#[inline(always)]` + `.position()`.
Happy to iterate if you have other ideas, or if you'd prefer to accept the
tradeoff.
--
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]
