Repository navigation
Commit e8e48c8
authored
Blocked
Tracking Issue: #10167
## Summary
Add an optional `block_offsets` child to `BitPackedArray` that stores
the byte boundaries of independently sized packed blocks, and make the
shared bit width in `BitPackedData` optional.
An array has exactly one of the two: a global bit width, as today, or
block offsets.
## Design
### Bit widths
`BitPackedData::global_bit_width` is `Some(width)` when every block
shares a width, and `None` when `block_offsets` is `Some`. Validation
requires exactly one of them.
`BitPackedArrayExt::bit_widths()` replaces `bit_width()`:
```rust
pub enum BitWidths {
/// Every block is packed at this bit width.
Global(u8),
/// Byte boundaries of the packed blocks, from which each block's bit width is derived.
Blocked(ArrayRef),
}
```
Paths that need one width (decoding, `scalar_at`, v1 serialization and
CUDA) return an error for blocked arrays until the decoder follow-ups.
There is a viewed and owned version of this.
### Block offsets
`block_offsets` is a non-nullable unsigned integer array with
`num_blocks + 1` entries, including a trailing end boundary.
Boundaries are relative to the first entry. Block `i` occupies bytes
`block_offsets[i] - block_offsets[0]` to `block_offsets[i + 1] -
block_offsets[0]` of the packed buffer, at `(block_offsets[i + 1] -
block_offsets[i]) / 128` bits, because a 1024-value block at width `w`
takes `128 * w` bytes.
For example, three blocks at widths 3, 0 and 7 have offsets `[0, 384,
384, 1280]`. Offsets with equal steps are still blocked; nothing
converts them to a global width.
## Validation
- A global width must be at most `ptype.bit_width()` (previously at most
64), and the packed buffer must hold `num_blocks * 128 * width` bytes,
as before.
- Block offsets must have a non-nullable unsigned integer dtype and
`num_blocks + 1` entries. Host-resident primitive offsets are also
checked boundary by boundary: they must be nondecreasing, each block
must be a whole number of 128-byte rows at most `ptype.bit_width()` bits
wide, and together they must span exactly the packed buffer. Other
encodings and device-resident offsets only get the dtype and length
checks.
## Scope
Nothing in this PR produces block offsets, but arrays built with
`try_new_with_block_offsets` can be constructed and inspected. Kernels
decline them, and decoding, scalar access, serialization and CUDA return
an error.
## Wire format and compatibility
`fastlanes.bitpacked` is unchanged. A global-width array has no block
offsets child, so it serializes exactly as before, and the reader builds
a global-width array from the metadata `bit_width`. Serializing a
blocked array with this plugin returns an error. Compression goldens are
unchanged.
## API changes
- `BitPackedArrayExt::bit_width()` and `BitPackedData::bit_width()` are
replaced by `BitPackedArrayExt::bit_widths() -> BitWidths`.
- `BitPackedDataParts::bit_width: u8` is replaced by `bit_widths:
BitWidths`.
- `BitPacked::try_new_with_block_offsets` constructs an array from
packed data and block boundaries. `BitPacked::try_new` and
`BitPackedData::try_new` are unchanged.
- `BitUnpackedChunks::try_new` and both `unpacked_chunks` accessors
return an error for blocked arrays.
- `bitpack_decompress::unpack_single` returns `VortexResult<Scalar>`.
- The unused `max_packed_value()` accessor is removed.
- The Python `FastLanesBitPackedArray.bit_width` property returns `int |
None`.
---------
Signed-off-by: Matt Katz <[email protected]>BitPacked: store block offsets as a child (#10004)1 parent 750b36d commit e8e48c8
27 files changed
Lines changed: 809 additions & 95 deletions
File tree
- encodings/fastlanes
- benches
- src
- bitpacking
- array
- compute
- vtable
- for_
- array
- vtable
- vortex-btrblocks/src/schemes/integer
- vortex-cuda
- benches
- src
- dynamic_dispatch
- kernel/encodings
- vortex-python
- python/vortex/_lib
- src/arrays
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
30 | 30 | | |
31 | 31 | | |
32 | 32 | | |
| 33 | + | |
33 | 34 | | |
34 | 35 | | |
35 | 36 | | |
| |||
58 | 59 | | |
59 | 60 | | |
60 | 61 | | |
| 62 | + | |
| 63 | + | |
| 64 | + | |
61 | 65 | | |
62 | 66 | | |
63 | 67 | | |
64 | 68 | | |
65 | 69 | | |
66 | | - | |
| 70 | + | |
67 | 71 | | |
68 | 72 | | |
69 | 73 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
34 | 34 | | |
35 | 35 | | |
36 | 36 | | |
| 37 | + | |
37 | 38 | | |
38 | 39 | | |
39 | 40 | | |
| |||
84 | 85 | | |
85 | 86 | | |
86 | 87 | | |
| 88 | + | |
| 89 | + | |
| 90 | + | |
87 | 91 | | |
88 | 92 | | |
89 | 93 | | |
90 | 94 | | |
91 | 95 | | |
92 | | - | |
| 96 | + | |
93 | 97 | | |
94 | 98 | | |
95 | 99 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
17 | 17 | | |
18 | 18 | | |
19 | 19 | | |
20 | | - | |
21 | 20 | | |
| 21 | + | |
22 | 22 | | |
23 | 23 | | |
24 | 24 | | |
| 25 | + | |
25 | 26 | | |
26 | 27 | | |
27 | 28 | | |
| |||
114 | 115 | | |
115 | 116 | | |
116 | 117 | | |
| 118 | + | |
| 119 | + | |
| 120 | + | |
117 | 121 | | |
118 | 122 | | |
119 | 123 | | |
120 | 124 | | |
121 | | - | |
| 125 | + | |
122 | 126 | | |
123 | 127 | | |
124 | 128 | | |
125 | 129 | | |
126 | 130 | | |
127 | | - | |
128 | | - | |
129 | 131 | | |
130 | 132 | | |
131 | 133 | | |
| |||
164 | 166 | | |
165 | 167 | | |
166 | 168 | | |
167 | | - | |
168 | | - | |
| 169 | + | |
| 170 | + | |
| 171 | + | |
| 172 | + | |
| 173 | + | |
169 | 174 | | |
170 | 175 | | |
171 | 176 | | |
| |||
176 | 181 | | |
177 | 182 | | |
178 | 183 | | |
179 | | - | |
| 184 | + | |
180 | 185 | | |
181 | 186 | | |
182 | 187 | | |
| |||
227 | 232 | | |
228 | 233 | | |
229 | 234 | | |
| 235 | + | |
230 | 236 | | |
231 | 237 | | |
232 | 238 | | |
| |||
259 | 265 | | |
260 | 266 | | |
261 | 267 | | |
262 | | - | |
| 268 | + | |
263 | 269 | | |
264 | 270 | | |
265 | 271 | | |
| |||
0 commit comments