Repository navigation
perf(alp): avoid per-combination allocations when searching exponents - #8565
Conversation
`find_best_exponents` ran a full `encode` for every `(e, f)` candidate just to size the result. it now estimates the size in a single allocation-free pass over the sample, leaving the chosen exponents (and the compression) unchanged. Relates to vortex-data#919 Signed-off-by: Han Damin <[email protected]>
Merging this PR will improve performance by 76.45%
|
| Mode | Benchmark | BASE |
HEAD |
Efficiency | |
|---|---|---|---|---|---|
| ❌ | Simulation | slice_empty_vortex |
310 ns | 368.3 ns | -15.84% |
| ❌ | Simulation | encode_varbin[(1000, 8)] |
141.1 µs | 157 µs | -10.14% |
| ❌ | Simulation | encode_varbin[(1000, 4)] |
140.5 µs | 156.1 µs | -10.03% |
| ⚡ | Simulation | compress_alp[f64, (1000, 0.0, 1.0)] |
237.2 µs | 73.3 µs | ×3.2 |
| ⚡ | Simulation | compress_alp[f64, (1000, 0.0, 0.95)] |
242.5 µs | 78.6 µs | ×3.1 |
| ⚡ | Simulation | compress_alp[f64, (1000, 0.0, 0.25)] |
242.5 µs | 78.7 µs | ×3.1 |
| ⚡ | Simulation | compress_alp[f64, (1000, 0.01, 1.0)] |
284.7 µs | 95.1 µs | ×3 |
| ⚡ | Simulation | compress_alp[f64, (1000, 0.1, 1.0)] |
286.1 µs | 96.8 µs | ×3 |
| ⚡ | Simulation | compress_alp[f64, (1000, 0.01, 0.95)] |
290.6 µs | 101.1 µs | ×2.9 |
| ⚡ | Simulation | compress_alp[f64, (1000, 0.01, 0.25)] |
290.1 µs | 100.9 µs | ×2.9 |
| ⚡ | Simulation | compress_alp[f64, (1000, 0.1, 0.25)] |
293.5 µs | 104.3 µs | ×2.8 |
| ⚡ | Simulation | compress_alp[f64, (1000, 0.1, 0.95)] |
297.4 µs | 108.8 µs | ×2.7 |
| ⚡ | Simulation | compress_alp[f32, (1000, 0.0, 1.0)] |
87.9 µs | 33.8 µs | ×2.6 |
| ⚡ | Simulation | compress_alp[f32, (1000, 0.0, 0.95)] |
93 µs | 39.1 µs | ×2.4 |
| ⚡ | Simulation | compress_alp[f32, (1000, 0.0, 0.25)] |
93.5 µs | 39.6 µs | ×2.4 |
| ⚡ | Simulation | compress_alp[f32, (1000, 0.01, 1.0)] |
118.2 µs | 56.2 µs | ×2.1 |
| ⚡ | Simulation | compress_alp[f32, (1000, 0.1, 1.0)] |
119.5 µs | 57.9 µs | ×2.1 |
| ⚡ | Simulation | compress_alp[f32, (1000, 0.01, 0.25)] |
124.2 µs | 62.5 µs | +98.52% |
| ⚡ | Simulation | compress_alp[f32, (1000, 0.01, 0.95)] |
123.8 µs | 62.6 µs | +97.78% |
| ⚡ | Simulation | compress_alp[f32, (1000, 0.1, 0.25)] |
127.7 µs | 65.6 µs | +94.57% |
| ... | ... | ... | ... | ... | ... |
ℹ️ Only the first 20 benchmarks are displayed. Go to the app to view all benchmarks.
Tip
Investigate this regression by commenting @codspeedbot fix this regression on this PR, or directly use the CodSpeed MCP with your agent.
Comparing miniex:perf/alp-exponent-sampling (88c7c53) with develop (f41dc23)
Footnotes
-
4 benchmarks were skipped, so the baseline results were used instead. If they were deleted from the codebase, click here and archive them to remove them from the performance reports. ↩
|
very cool optimization! just one ask |
fold the four kept/all min/max options into two `Option<(min, max)>` and a shared `update_bounds` helper, since both bounds widen with the same fallback. document what the `kept` and `all` ranges mean. no behavior change; the size estimate is bit-for-bit unchanged. Signed-off-by: Han Damin <[email protected]>
AdamGS
left a comment
AdamGS
left a comment
There was a problem hiding this comment.
Thanks for this contribution! great improvement.
Summary
find_best_exponentsran a fullencodefor every(e, f)candidate just to size the result, allocating the encoded, patch and chunk-offset buffers across the wholee/fsearch space. It now estimates the size in a single allocation-free pass viaestimate_encoded_size_for_exponents, which reproduces the existingestimate_encoded_sizeexactly, so the chosen exponents (and therefore the compressed output) are bit-for-bit unchanged.This is the throughput half of #919; the two-level stratified sampling / top-N reuse the issue describes would change which exponents are picked and depends on per-column scheme state (#8434), so I left it out here.
Benchmark
encodings/alp/benches/alp_compress.rs, compress medians (type, length, patch-fraction, valid-fraction):Testing
cargo nextest run -p vortex-alp -p vortex-btrblockspasses, including a new equivalence test (estimate_for_exponents_matches_full_encode) that asserts the allocation-free estimate equals a fullencode+estimate_encoded_sizefor every candidate exponent across kept, patched and all-patched inputs.fmt+clippy --all-targets --all-features+cargo docclean.I'm Korean, so sorry if any wording reads a little awkward.