Skip to content

Refine FoRScheme to per-chunk references when fastlanes.for.v2 is allowed - #10136

Merged
mhk197 merged 2 commits into
developfrom
mk/for-chunked-05-scheme
Sep 30, 2026
Merged

mhk197 merged 2 commits into
developfrom
mk/for-chunked-05-scheme

Conversation

@mhk197

@mhk197 mhk197 commented Sep 29, 2026 •

Copy link
Copy Markdown
Contributor

Stacked on #10135.

Summary

FoRScheme compresses with one reference per 1024-element chunk when the compressor's allowed serialized IDs include fastlanes.for.v2, following DecimalScheme. Default writes are unchanged: the core edition allows only fastlanes.for, so refine keeps v1.

FoRScheme

  • FoRScheme gains v1 and v2 modes with v1() and v2() constructors; Default is v1. The session registers FOR_V1.
  • refine returns v2 when fastlanes.for.v2 is allowed, and v1 otherwise.
  • produced_encodings: v1 declares fastlanes.for; v2 declares fastlanes.for and fastlanes.for.v2.
  • Compress: v2 always encodes with FoR::encode_chunked. Per-chunk references never pack wider than one reference, and the chunked encoder is faster than the single-reference one. The encoded child is bit-packed as before, and the references are compressed as child 0 with compress_child. When every chunk has the same minimum, the references compress to a constant and the array serializes as fastlanes.for.
  • Estimate: both modes use v1's estimate, unchanged. That is conservative for v2: it can understate v2's ratio, and it skips arrays where only per-chunk references would help, such as those whose minimum is zero or whose single-reference width is no narrower than plain BitPacking.

CUDA

The CUDA preset excludes fastlanes.for.v2, as it does multi-part decimals. The GPU FoR decoder returns an error for per-chunk references.

Follow-ups

  • Estimate per-chunk references. The existing samples can't estimate them: the sampler stitches 64-value runs from across the array, so no sampled chunk resembles a real one. Options are chunk-aligned sampling, or a read-only pass computing each chunk's min and max, which is much cheaper than encode_chunked because it writes nothing. The ratio should then count the references child. Done when estimate_skips_arrays_only_chunk_references_narrow expects v2, the golden snapshots don't regress, and the change in compression time is measured.

@codspeed

codspeed Bot commented Sep 29, 2026 •

Copy link
Copy Markdown

Merging this PR will not alter performance

⚠️ Unknown Walltime execution environment detected

Using the Walltime instrument on standard Hosted Runners will lead to inconsistent data.

For the most accurate results, we recommend using CodSpeed Macro Runners: bare-metal machines fine-tuned for performance measurement consistency.

✅ 2070 untouched benchmarks
🆕 15 new benchmarks
⏩ 503 skipped benchmarks1

Performance Changes

Mode Benchmark BASE HEAD Efficiency
🆕 WallTime decode_bitpacked_chunked_avx2[i64, 524288] N/A 34.1 µs N/A
🆕 WallTime decode_bitpacked_chunked_avx2[u32, 524288] N/A 19.8 µs N/A
🆕 WallTime decode_chunked_avx2[i64, 524288] N/A 19.2 µs N/A
🆕 WallTime encode_chunked_avx2[i64, 524288] N/A 24.5 µs N/A
🆕 WallTime encode_chunked_nullable_avx2[i64, 524288] N/A 135.5 µs N/A
🆕 WallTime decode_bitpacked_chunked_avx512[i64, 524288] N/A 31.8 µs N/A
🆕 WallTime decode_bitpacked_chunked_avx512[u32, 524288] N/A 17.2 µs N/A
🆕 WallTime decode_chunked_avx512[i64, 524288] N/A 19.2 µs N/A
🆕 WallTime encode_chunked_avx512[i64, 524288] N/A 19.3 µs N/A
🆕 WallTime encode_chunked_nullable_avx512[i64, 524288] N/A 61.7 µs N/A
🆕 WallTime decode_bitpacked_chunked_neon[i64, 524288] N/A 40.6 µs N/A
🆕 WallTime decode_bitpacked_chunked_neon[u32, 524288] N/A 26.4 µs N/A
🆕 WallTime decode_chunked_neon[i64, 524288] N/A 13.4 µs N/A
🆕 WallTime encode_chunked_neon[i64, 524288] N/A 35.8 µs N/A
🆕 WallTime encode_chunked_nullable_neon[i64, 524288] N/A 64.6 µs N/A

Comparing mk/for-chunked-05-scheme (c7a39c7) with develop (e868676)2

Open in CodSpeed

Footnotes

  1. 503 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. ↩

  2. No successful run was found on develop (4224390) during the generation of this report, so e868676 was used instead as the comparison base. There might be some changes unrelated to this pull request in this report. ↩

@mhk197
mhk197 added this pull request to stack #10109 September 29, 2026 18:11
@mhk197 mhk197 added the changelog/feature A new feature label Sep 29, 2026
@mhk197
mhk197 force-pushed the mk/for-chunked-05-scheme branch from 0bc6c52 to 87069c3 Compare September 30, 2026 15:59
@mhk197
mhk197 marked this pull request as ready for review September 30, 2026 16:05
@mhk197
mhk197 force-pushed the mk/for-chunked-05-scheme branch 2 times, most recently from 736d146 to e74bb01 Compare September 30, 2026 17:30
@mhk197 mhk197 linked an issue Sep 30, 2026 that may be closed by this pull request
Base automatically changed from mk/for-chunked-04-v2-wire to develop September 30, 2026 18:00
@mhk197
mhk197 force-pushed the mk/for-chunked-05-scheme branch from e74bb01 to c7a39c7 Compare September 30, 2026 18:00
@mhk197
mhk197 merged commit 0751940 into develop Sep 30, 2026
90 checks passed
@mhk197
mhk197 deleted the mk/for-chunked-05-scheme branch September 30, 2026 19:18
mhk197 added a commit that referenced this pull request Oct 1, 2026
## Summary

FoR's `CastReduce` now pushes down only casts that change nullability
(`eq_ignore_nullability`). Every cast that changes the integer type
declines, so the array decodes and the decoded values are cast. This
fixes three correctness bugs in casting FoR arrays. Two of them have
been there since before the new FoR array.

## Background

FoR stores each value as an offset from a reference: `encoded =
value.wrapping_sub(reference)` in the source type, and decoding is
`encoded.wrapping_add(reference)` in whatever type the array has. The
encoded values are therefore offsets modulo 2ⁿ, stored in the source
type, and not ordinary values.

The old kernel cast the encoded child and the references to the target
type separately, then rebuilt the FoR array. That treats the offsets as
plain values, which is only correct when every offset fits the source
type as a non-negative number and every decoded value fits the target
type.

## Bugs

Reproduced on `develop` and, for the first two, on the commit before the
blocked FoR stack (`ba5fcfcde0^`):

| Cast | Expected | Got |
|---|---|---|
| `[-128i8, 127]` → `i16` | `[-128, 127]` | `[-128, -129]` |
| `[100i16, 200]` → `i8` | `Err(value exceeds target range)` | `[100,
-56]` |
| `5..10` (reference `-5`) → `u32` | `[5, 6, 7, 8, 9]` | `Err(No
CastReduce to cast constant array from i32 to u32)` on decode |

1. **Widening a signed type whose range exceeds `T::MAX` gives wrong
values.** `[-128i8, 127]` has reference `-128`, so `127` is stored as
`255`, which wraps to `-1` in `i8`. Casting the encoded child to `i16`
sign-extends it to `-1`, which decodes as `-128 + -1 = -129`. Over `i8`
values `-128..=127`, 128 of 256 values come out wrong, with no error.
`FoR::encode` produces this whenever a signed column's range exceeds the
type's maximum.
2. **Narrowing wraps instead of erroring.** In `[100i16, 200]` cast to
`i8`, the reference `100` and the offsets `0` and `100` each fit `i8`,
but `100 + 100` doesn't, and the wrapping decode hides the overflow.
Sign changes such as `i8` → `u8` and `u8` → `i8` fail the same way. The
opposite also happens: `-100i32..100` fits `i8`, but its offsets
`0..=199` don't, so the cast fails on decode.
3. **An out-of-range reference leaves an undecodable array.** Values
`5..10` with reference `-5` can remain after filtering away the
negatives. Cast to `u32`, the values fit but the reference doesn't.
`Constant`'s `CastReduce` declines, so the references slot is left
holding a lazy `vortex.cast`, which `try_new_chunked` accepts because it
only checks dtype and length. The cast appears to succeed, and decoding
fails. Before #10105, the scalar reference cast failed eagerly, so the
whole cast errored instead. Per-chunk references hit the same issue,
because a slice keeps the references of every chunk it overlaps.

The existing tests didn't catch these: every conformance case has a
small range and widens.

## Why decline instead of proving the cast safe

- **The pushdown doesn't save work.** BitPacked's `CastReduce` only
handles nullability, and its widening `CastKernel` unpacks into a
full-width buffer. A pushed-down widening cast therefore executes as
`FoR(Cast(BitPacked))`: it unpacks into a wide buffer, then adds the
reference in a second pass, because the child is no longer BitPacked and
FoR's fused unpack-and-add path doesn't apply. Declining gives one fused
decode in the narrow type, then a widening primitive cast. The pass
count is the same, with the fused pass over narrower data.
- **Nothing downstream benefits.** For example, a compare on
`FoR(Cast(BitPacked))` can't use BitPacked's compare kernel.
- **It wouldn't apply to per-chunk references.** Since #10136,
`FoRScheme` writes per-chunk references when `fastlanes.for.v2` is
allowed. The proof needs the minimum and maximum of the references
child, which may be lazy inside a reduce rule, so every type change
would decline there anyway.

A nullability-only cast is always safe: it changes neither the values
nor the non-nullable references, so it is still pushed down, for single
and per-chunk references alike.

---------

Signed-off-by: Matt Katz <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

changelog/feature A new feature

Projects

None yet

Development

Successfully merging this pull request may close these issues.

Blocked FoR: Support compressing into v2

2 participants