Repository navigation
Commit 812de38
authored
Encode/Decode Kernels for Blocked
Stacked on #10105.
## Summary
Adds an encoder that picks one reference per 1024-element chunk, and a
fused decode for chunked FoR over BitPacked. No wire format changes:
arrays with varying references still can't be serialized until the next
PR.
## Encoder
`FoR::encode_chunked(array, ctx)` uses the same rule as `FoR::encode`,
applied per chunk:
- Each chunk's reference is the minimum of its valid values, so every
encoded value is small and non-negative. Null slots don't count towards
the minimum.
- Null rows encode as 0, as in `FoR::encode`.
- The minimum and the subtraction run per chunk while it is in cache,
without branches. Each value is masked with all ones or all zeros from
its validity bit, over fixed 64-value blocks, so both loops vectorize at
every integer width. I checked the aarch64 assembly: `umin`/`smin` and
`sub` at `.8b`/`.8h`/`.4s`/`.2d`, with no per-value branches.
- A chunk with no valid values reuses the previous chunk's reference (or
the first valid reference at the start), so the references compress into
runs.
- The references are a plain primitive child and the offset is 0.
Compressing the references is left to the compressor scheme.
```text
chunk 0 values: 1_000_000 .. 1_000_900 → reference 1_000_000, encoded 0..900
chunk 1 values: all null → reference 1_000_000, encoded 0
chunk 2 values: 9_000_000 .. 9_000_950 → reference 9_000_000, encoded 0..950
```
Encoding, `cargo bench -p vortex-fastlanes --bench for_encode`, median
per iteration on an M5 Max with 512 KiB of input (128Ki `u32` or 64Ki
`i64` values):
| | `FoR::encode` | `FoR::encode_chunked` |
|---|---|---|
| u32, non-null | 13.4 µs | 10.3 µs |
| i64, non-null | 18.0 µs | 12.5 µs |
| u32, 10% null | 112 µs | 27.6 µs |
| i64, 10% null | 61.5 µs | 25.0 µs |
## Decode
`decompress_many_refs` now dispatches like `decompress_one_ref`:
- **Fused**: unsigned arrays whose `encoded` child is `BitPacked` with
the same offset as the FoR. For each packed chunk it calls
`unchecked_unfor_pack` with that chunk's reference, writing full chunks
straight into the output and partial first/last chunks through a scratch
buffer. Patch values are added to the reference of the chunk they fall
in.
- **Unfused** (`add_references`): everything else. It decodes `encoded`,
then adds each chunk's reference. A uniquely owned buffer is updated in
place. A shared one, as when `encoded` is a plain primitive child, gets
the references added while it is copied, in one pass. Copying first and
then adding made this path 2.2× slower than single-reference decode.
A BitPacked child with patches slices lazily into `Slice(BitPacked)`, so
sliced arrays with patches take the unfused path. Single-reference FoR
behaves the same way today.
Decoding, `--bench for_decode`, same machine and input size. Every chunk
spans the same range, so both encodings pack at 7 bits and the
difference is the cost of the per-chunk references:
| | one reference | per-chunk references |
|---|---|---|
| u32, primitive child | 8.46 µs | 8.71 µs |
| i64, primitive child | 8.46 µs | 8.50 µs |
| u32, BitPacked child (fused) | 9.58 µs | 9.67 µs |
| i64, BitPacked child (unfused) | 19.1 µs | 19.2 µs |
Single-reference decode is as fast as it was before #10105. On aarch64,
the per-chunk reference adds compile to four 128-bit `add.4s`/`add.2d`
per iteration, and fused decode calls the same `unchecked_unfor_pack`
kernel as single-reference decode.
## Benchmarks
`for_encode` and `for_decode` cover `u32` and `i64` inputs of 256 KiB
and 512 KiB. They carry `#[cpu_features]`, so CodSpeed measures them on
the walltime legs instead of in simulation. Locally, every case takes
4–112 µs per iteration.
## CUDA
CUDA FoR decoding now returns an error for per-chunk references instead
of falling back to the CPU.
---------
Signed-off-by: Matt Katz <[email protected]>FoR (#10118)1 parent e868676 commit 812de38
9 files changed
Lines changed: 828 additions & 139 deletions
File tree
- encodings/fastlanes
- benches
- src/for
- array
- vtable
- vortex-cuda/src/kernel/encodings
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
40 | 40 | | |
41 | 41 | | |
42 | 42 | | |
| 43 | + | |
43 | 44 | | |
44 | 45 | | |
45 | 46 | | |
| |||
71 | 72 | | |
72 | 73 | | |
73 | 74 | | |
| 75 | + | |
| 76 | + | |
| 77 | + | |
| 78 | + | |
| 79 | + | |
| 80 | + | |
| 81 | + | |
| 82 | + | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
| 1 | + | |
| 2 | + | |
| 3 | + | |
| 4 | + | |
| 5 | + | |
| 6 | + | |
| 7 | + | |
| 8 | + | |
| 9 | + | |
| 10 | + | |
| 11 | + | |
| 12 | + | |
| 13 | + | |
| 14 | + | |
| 15 | + | |
| 16 | + | |
| 17 | + | |
| 18 | + | |
| 19 | + | |
| 20 | + | |
| 21 | + | |
| 22 | + | |
| 23 | + | |
| 24 | + | |
| 25 | + | |
| 26 | + | |
| 27 | + | |
| 28 | + | |
| 29 | + | |
| 30 | + | |
| 31 | + | |
| 32 | + | |
| 33 | + | |
| 34 | + | |
| 35 | + | |
| 36 | + | |
| 37 | + | |
| 38 | + | |
| 39 | + | |
| 40 | + | |
| 41 | + | |
| 42 | + | |
| 43 | + | |
| 44 | + | |
| 45 | + | |
| 46 | + | |
| 47 | + | |
| 48 | + | |
| 49 | + | |
| 50 | + | |
| 51 | + | |
| 52 | + | |
| 53 | + | |
| 54 | + | |
| 55 | + | |
| 56 | + | |
| 57 | + | |
| 58 | + | |
| 59 | + | |
| 60 | + | |
| 61 | + | |
| 62 | + | |
| 63 | + | |
| 64 | + | |
| 65 | + | |
| 66 | + | |
| 67 | + | |
| 68 | + | |
| 69 | + | |
| 70 | + | |
| 71 | + | |
| 72 | + | |
| 73 | + | |
| 74 | + | |
| 75 | + | |
| 76 | + | |
| 77 | + | |
| 78 | + | |
| 79 | + | |
| 80 | + | |
| 81 | + | |
| 82 | + | |
| 83 | + | |
| 84 | + | |
| 85 | + | |
| 86 | + | |
| 87 | + | |
| 88 | + | |
| 89 | + | |
| 90 | + | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
| 1 | + | |
| 2 | + | |
| 3 | + | |
| 4 | + | |
| 5 | + | |
| 6 | + | |
| 7 | + | |
| 8 | + | |
| 9 | + | |
| 10 | + | |
| 11 | + | |
| 12 | + | |
| 13 | + | |
| 14 | + | |
| 15 | + | |
| 16 | + | |
| 17 | + | |
| 18 | + | |
| 19 | + | |
| 20 | + | |
| 21 | + | |
| 22 | + | |
| 23 | + | |
| 24 | + | |
| 25 | + | |
| 26 | + | |
| 27 | + | |
| 28 | + | |
| 29 | + | |
| 30 | + | |
| 31 | + | |
| 32 | + | |
| 33 | + | |
| 34 | + | |
| 35 | + | |
| 36 | + | |
| 37 | + | |
| 38 | + | |
| 39 | + | |
| 40 | + | |
| 41 | + | |
| 42 | + | |
| 43 | + | |
| 44 | + | |
| 45 | + | |
| 46 | + | |
| 47 | + | |
| 48 | + | |
| 49 | + | |
| 50 | + | |
| 51 | + | |
| 52 | + | |
| 53 | + | |
| 54 | + | |
| 55 | + | |
| 56 | + | |
| 57 | + | |
| 58 | + | |
| 59 | + | |
| 60 | + | |
| 61 | + | |
| 62 | + | |
| 63 | + | |
| 64 | + | |
| 65 | + | |
| 66 | + | |
| 67 | + | |
| 68 | + | |
| 69 | + | |
| 70 | + | |
| 71 | + | |
| 72 | + | |
| 73 | + | |
| 74 | + | |
| 75 | + | |
| 76 | + | |
| 77 | + | |
| 78 | + | |
| 79 | + | |
| 80 | + | |
| 81 | + | |
| 82 | + | |
| 83 | + | |
| 84 | + | |
| 85 | + | |
| 86 | + | |
0 commit comments