Skip to content

Commit d7d9a98

Browse files
committed
feat: prototype NarrowArray for narrow integer storage
Signed-off-by: Matt Katz <[email protected]>
1 parent c215b0e commit d7d9a98

13 files changed

Lines changed: 1843 additions & 0 deletions

File tree

Lines changed: 86 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,86 @@
1+
// SPDX-License-Identifier: Apache-2.0
2+
// SPDX-FileCopyrightText: Copyright the Vortex contributors
3+
4+
#![cfg(test)]
5+
6+
use vortex_array::ArrayContext;
7+
use vortex_array::IntoArray;
8+
use vortex_array::VortexSessionExecute;
9+
use vortex_array::array_session;
10+
use vortex_array::arrays::BoolArray;
11+
use vortex_array::arrays::ConstantArray;
12+
use vortex_array::arrays::Narrow;
13+
use vortex_array::arrays::NarrowArray;
14+
use vortex_array::arrays::PrimitiveArray;
15+
use vortex_array::arrays::ScalarFn;
16+
use vortex_array::arrays::narrow::NarrowArraySlotsExt;
17+
use vortex_array::arrays::scalar_fn::ScalarFnArrayExt;
18+
use vortex_array::assert_arrays_eq;
19+
use vortex_array::builtins::ArrayBuiltins;
20+
use vortex_array::dtype::PType;
21+
use vortex_array::scalar_fn::fns::binary::CompareKernel;
22+
use vortex_array::scalar_fn::fns::operators::CompareOperator;
23+
use vortex_array::scalar_fn::fns::operators::Operator;
24+
use vortex_array::serde::SerializeOptions;
25+
use vortex_array::serde::SerializedArray;
26+
use vortex_buffer::ByteBufferMut;
27+
use vortex_buffer::buffer;
28+
use vortex_error::VortexResult;
29+
use vortex_error::vortex_err;
30+
use vortex_fastlanes::BitPacked;
31+
use vortex_fastlanes::BitPackedData;
32+
use vortex_session::registry::ReadContext;
33+
34+
#[test]
35+
fn narrow_bitpacked_comparison_selection_and_roundtrip() -> VortexResult<()> {
36+
let session = array_session();
37+
vortex_fastlanes::initialize(&session);
38+
let mut ctx = session.create_execution_ctx();
39+
let primitive = PrimitiveArray::from_iter((0u8..32).cycle().take(2300)).into_array();
40+
let packed = BitPackedData::encode(&primitive, 5, &mut ctx)?.into_array();
41+
let array = NarrowArray::try_new(packed, PType::U64.into())?;
42+
43+
let constant = ConstantArray::new(16u64, array.len()).into_array();
44+
let comparison = Narrow::compare(array.as_view(), &constant, CompareOperator::Lt, &mut ctx)?
45+
.ok_or_else(|| vortex_err!("expected narrow comparison kernel"))?;
46+
let comparison_view = comparison.as_::<ScalarFn>();
47+
assert!(comparison_view.get_child(0).is::<BitPacked>());
48+
assert_eq!(comparison_view.get_child(1).dtype(), &PType::U8.into());
49+
assert_arrays_eq!(
50+
comparison,
51+
BoolArray::from_iter((0..2300).map(|i| i % 32 < 16)),
52+
&mut ctx
53+
);
54+
55+
let sliced = array.slice(13..2200)?;
56+
assert!(sliced.as_::<Narrow>().values().is::<BitPacked>());
57+
let taken = sliced.take(buffer![0u32, 1020, 2186].into_array())?;
58+
assert!(taken.is::<Narrow>());
59+
assert_arrays_eq!(taken, buffer![13u64, 9, 23].into_array(), &mut ctx);
60+
61+
let array = array.into_array();
62+
let array_ctx = ArrayContext::empty();
63+
let mut bytes = ByteBufferMut::empty();
64+
for buffer in array.serialize(&array_ctx, &session, &SerializeOptions::default())? {
65+
bytes.extend_from_slice(&buffer);
66+
}
67+
let decoded = SerializedArray::try_from(bytes.freeze())?.decode(
68+
array.dtype(),
69+
array.len(),
70+
&ReadContext::new(array_ctx.to_ids()),
71+
&session,
72+
)?;
73+
assert!(decoded.as_::<Narrow>().values().is::<BitPacked>());
74+
assert_eq!(decoded.as_::<Narrow>().values().dtype(), &PType::U8.into());
75+
assert_arrays_eq!(
76+
decoded,
77+
PrimitiveArray::from_iter((0u64..32).cycle().take(2300)),
78+
&mut ctx
79+
);
80+
assert_arrays_eq!(
81+
decoded.binary(ConstantArray::new(300u64, 2300).into_array(), Operator::Lt)?,
82+
BoolArray::from_iter([true; 2300]),
83+
&mut ctx
84+
);
85+
Ok(())
86+
}

‎narrow-array-benchmark-results.json‎

Lines changed: 173 additions & 0 deletions
Large diffs are not rendered by default.

‎narrow-array-benchmarks.md‎

Lines changed: 206 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,206 @@
1+
<!-- SPDX-License-Identifier: Apache-2.0 -->
2+
<!-- SPDX-FileCopyrightText: Copyright the Vortex contributors -->
3+
4+
# NarrowArray benchmarks
5+
6+
Measured on 2026-09-23 against comparison PR #9948 at
7+
`c215b0e423f558ef83ac0f99841160d70237a9b7`. All logical-i64 comparisons use the
8+
same executable and kernels. The existing primitive comparison benchmarks and kernels
9+
are unchanged by this draft.
10+
11+
The strongest measured compute benefit is i8 comparison. Smaller storage alone does not
12+
make every operation faster: i32/i16 constant comparison and gathers that return i64
13+
remain slower in this prototype. These are array microbenchmarks, not end-to-end queries.
14+
15+
## Buffer size
16+
17+
These are measured `ArrayRef::nbytes()` values for 1,048,576 non-null rows:
18+
19+
| Logical i64 representation | Buffer bytes | MiB | Reduction |
20+
| --- | ---: | ---: | ---: |
21+
| Primitive i64 | 8,388,608 | 8 | baseline |
22+
| Narrow over i32 | 4,194,304 | 4 | 50% |
23+
| Narrow over i16 | 2,097,152 | 2 | 75% |
24+
| Narrow over i8 | 1,048,576 | 1 | 87.5% |
25+
26+
The same ratios were verified at 8,192 and 16,777,216 rows. NarrowArray owns no value
27+
buffers; the child holds the narrower buffer. `nbytes()` does not count array objects,
28+
statistics, allocator bookkeeping, or process RSS. Nullable arrays also retain validity
29+
storage. No file-compression or serialized-size gain is claimed here.
30+
31+
## Comparisons at 1,048,576 rows
32+
33+
Pooled median time in microseconds; lower is better:
34+
35+
| Operation | Primitive i64 | Narrow/i32 | Narrow/i16 | Narrow/i8 |
36+
| --- | ---: | ---: | ---: | ---: |
37+
| `x < 16` | 171.50 | 196.48 | 208.60 | 38.98 |
38+
| `x == 16` | 179.35 | 206.44 | 220.19 | 41.67 |
39+
| `x < y` | 296.02 | 243.25 | 256.94 | 49.17 |
40+
| `x == y` | 305.44 | 244.58 | 257.90 | 49.69 |
41+
42+
For `<`, i8 storage is 4.40x faster against a constant and 6.02x faster against another
43+
column. Across the three individual passes those ratios range from 4.33–4.41x and
44+
6.03–7.02x, respectively. i32/i16 storage is about 15%/22% slower against a constant,
45+
but improves column comparisons by about 1.22x/1.15x in the pooled measurements.
46+
47+
Plain native-width controls use the same child buffers as the wrappers:
48+
49+
| Storage | Native `< constant` (us) | Narrow `< constant` (us) | Native `< column` (us) | Narrow `< column` (us) |
50+
| --- | ---: | ---: | ---: | ---: |
51+
| i32 | 196.04 | 196.48 | 242.75 | 243.25 |
52+
| i16 | 208.40 | 208.60 | 257.27 | 256.94 |
53+
| i8 | 38.50 | 38.98 | 48.38 | 49.17 |
54+
55+
The wrapper's difference from a native array at the same width is small at this row count.
56+
The 8-bit kernel optimization in the base PR is responsible for the large comparison
57+
advantage; NarrowArray makes that kernel available while preserving logical i64.
58+
59+
## Selection and pipelines at 1,048,576 rows
60+
61+
Times in microseconds. Filter selects approximately 50% of rows. Take gathers N/8
62+
indices in a deterministic pseudorandom order. Inputs, masks, and indices are prebuilt.
63+
Every operation is executed to its final primitive or boolean result before stopping the timer.
64+
65+
| Operation | Primitive i64 | Narrow/i32 | Narrow/i16 | Narrow/i8 |
66+
| --- | ---: | ---: | ---: | ---: |
67+
| Filter → i64 buffer | 304.85 | 227.27 | 156.02 | 342.69 |
68+
| Take → i64 buffer | 215.77 | 331.96 | 308.33 | 321.40 |
69+
| Compare → filter → i64 buffer | 458.10 | 402.62 | 342.27 | 382.17 |
70+
| Filter → compare → bool bitmap | 379.71 | 211.58 | 156.58 | 264.73 |
71+
| Take → compare → bool bitmap | 167.62 | 165.17 | 153.58 | 120.75 |
72+
73+
- Compare/filter with i8 storage is about 1.20x faster even with a final i64 result.
74+
- i16 is the strongest filtering representation in this fixture: filter → i64 is 1.95x
75+
faster and filter → compare is 2.42x faster. i8 filter → i64 is about 12% slower.
76+
- Take → compare benefits from i8 storage (1.39x), but take → i64 is about 49% slower.
77+
The current canonical fallback casts the narrow child to i64; the existing dictionary
78+
cast rule pushes that cast into all dictionary values before gathering. Avoiding that
79+
early widening is a follow-up optimization, not a benefit implemented by this draft.
80+
81+
## Encoding and canonical materialization
82+
83+
Times in microseconds for 1,048,576 rows:
84+
85+
| Operation | Primitive i64 | Narrow/i32 | Narrow/i16 | Narrow/i8 |
86+
| --- | ---: | ---: | ---: | ---: |
87+
| Encode, fresh bounds scan | 212.96 | 384.04 | 355.71 | 334.15 |
88+
| Materialize canonical i64 | 0.08 | 199.58 | 177.88 | 188.90 |
89+
90+
Encoding inputs require the indicated storage width: the common 0..31 pattern is shifted
91+
by 0 for i8, 128 for i16, 32,768 for i32, and 2,147,483,648 for i64. The i64 column is
92+
therefore the cost of discovering that narrowing is impossible, not a conversion baseline.
93+
Each sample uses fresh array statistics so the bounds scan cannot disappear into a cache.
94+
Input buffer generation and creation of the fresh array handle are outside the timer.
95+
96+
The i8 encoding cost is about 334 us. The pooled constant-comparison saving is about
97+
133 us per pass: roughly three comparisons amortize conversion, or three to four using
98+
individual-pass medians. Encoding solely for one comparison loses overall. Constructing
99+
NarrowArray around an existing narrow child avoids conversion and the bounds scan.
100+
101+
Canonical materialization is an additional cost: about 189 us to widen i8 to i64 here.
102+
The primitive-i64 materialization case is a no-op handle operation, not a buffer copy.
103+
Arithmetic, aggregates, and mixed-storage-width comparisons have no specialized Narrow
104+
kernel in this draft and may pay for widening.
105+
106+
## Row-count sweep
107+
108+
All times below are microseconds. These tables use `<`; equality and all native-width
109+
controls are in the machine-readable results.
110+
111+
### 8,192 rows
112+
113+
| Operation | Primitive i64 | Narrow/i32 | Narrow/i16 | Narrow/i8 |
114+
| --- | ---: | ---: | ---: | ---: |
115+
| `x < 16` | 2.21 | 2.54 | 2.62 | 1.29 |
116+
| `x < y` | 2.71 | 2.42 | 2.42 | 1.08 |
117+
118+
| Operation | Primitive i64 | Narrow/i32 | Narrow/i16 | Narrow/i8 |
119+
| --- | ---: | ---: | ---: | ---: |
120+
| FilterToI64 | 4.12 | 3.50 | 2.88 | 4.54 |
121+
| TakeToI64 | 1.21 | 4.04 | 3.75 | 4.17 |
122+
| CompareFilterToI64 | 7.46 | 5.83 | 5.29 | 5.88 |
123+
| FilterCompare | 6.62 | 3.88 | 3.42 | 4.33 |
124+
| TakeCompare | 2.25 | 3.29 | 3.21 | 3.12 |
125+
| Encode | 2.88 | 4.40 | 3.96 | 3.79 |
126+
| MaterializeI64 | 0.08 | 1.62 | 1.54 | 2.08 |
127+
128+
### 16,777,216 rows
129+
130+
| Operation | Primitive i64 | Narrow/i32 | Narrow/i16 | Narrow/i8 |
131+
| --- | ---: | ---: | ---: | ---: |
132+
| `x < 16` | 3568.77 | 3942.46 | 4217.94 | 738.85 |
133+
| `x < y` | 3905.52 | 2655.87 | 2815.94 | 544.52 |
134+
135+
| Operation | Primitive i64 | Narrow/i32 | Narrow/i16 | Narrow/i8 |
136+
| --- | ---: | ---: | ---: | ---: |
137+
| FilterToI64 | 4898.38 | 3663.04 | 2505.21 | 5478.21 |
138+
| TakeToI64 | 9284.69 | 12349.31 | 11896.35 | 12101.79 |
139+
| CompareFilterToI64 | 7328.42 | 6389.04 | 5343.48 | 6027.17 |
140+
| FilterCompare | 6034.90 | 3367.04 | 2483.33 | 4225.44 |
141+
| TakeCompare | 9435.10 | 8211.56 | 6757.50 | 3897.21 |
142+
| Encode | 3439.96 | 6205.85 | 5742.08 | 5420.33 |
143+
| MaterializeI64 | 0.25 | 3204.27 | 2862.83 | 3036.96 |
144+
145+
Small-array overhead matters: at 8K rows the i8 comparison gains are 1.71x/2.50x,
146+
and take → compare is slower for every narrow width. Large-buffer selection and allocation
147+
timings vary more between passes; consult the individual pass medians and quartiles rather
148+
than treating the pooled values as precise latency guarantees.
149+
150+
## Method
151+
152+
- Apple M5 Max, aarch64, macOS 26.6.1 (25G76), Rust 1.98.0.
153+
- Standard repository bench profile: optimized, 16 codegen units, LTO off. Repository
154+
`force-frame-pointers=yes`; no additional `RUSTFLAGS` or target-CPU override.
155+
- Three sequential passes, 140 samples per case per pass. Representations rotate both their
156+
starting position and traversal direction on every round. No concurrent builds or other
157+
benchmarks were launched during measurement.
158+
- The tables are pooled medians over 420 samples. Absolute times varied across passes;
159+
e.g. the 1M-row i64 constant comparison medians were 171, 223, and 141 us, while the
160+
corresponding narrow-i8 medians were 39, 52, and 32 us. Relative comparison benefits
161+
persisted. This was not a pinned-core or controlled-frequency experiment.
162+
- All compute inputs are ordinary uncompressed PrimitiveArray buffers with non-null values
163+
in 0..31. Native-width controls expose that width as their logical type; every Narrow
164+
representation keeps logical i64. Pairs have matching storage widths on both sides.
165+
- Timings include expression construction, execution, and result allocation. Input creation,
166+
conversion to the chosen input representation, execution-context creation, and destruction
167+
of the returned result are outside timing. Inputs are reused; no forced cold-cache flush.
168+
- Comparison/operation results are checked against the i64 reference before timing. Encoding
169+
checks both value equality and output buffer size. Mask and index generation are excluded;
170+
compare → filter includes construction of the predicate mask.
171+
- The public execution path may reorder or push operations through children. These pipeline
172+
measurements do not require a particular physical execution order.
173+
174+
Sources: [comparison matrix](vortex-array/benches/narrow_compare.rs),
175+
[selection/encoding matrix](vortex-array/benches/narrow.rs).
176+
[Machine-readable results](narrow-array-benchmark-results.json) contain every case, quartiles,
177+
and individual-pass medians. Raw per-sample CSVs are in
178+
`/private/tmp/narrow-{compare,operations}-run{1,2,3}.csv` on the measurement host.
179+
180+
Build command:
181+
182+
```sh
183+
CARGO_TARGET_DIR=/Users/matt/Desktop/repo/vortex/target \
184+
cargo bench -p vortex-array --bench narrow --bench narrow_compare --no-run
185+
```
186+
187+
The build prints the executable paths. The measured binaries were
188+
`target/release/deps/narrow_compare-081029d9296a0cf7` and
189+
`target/release/deps/narrow-729aa8d2feff4afe` under that target directory. Each was run with
190+
`VORTEX_NARROW_INTERLEAVED=1` three times, sequentially, redirecting stdout to its CSV;
191+
`narrow` also emits measured buffer bytes on stderr. Without that environment variable,
192+
the same targets expose ordinary Divan benchmarks via `cargo bench`.
193+
194+
## Validation
195+
196+
- `cargo nextest run -p vortex-array -p vortex-fastlanes`: 4,121 passed, one existing skip.
197+
- `cargo test --doc -p vortex-array`: 76 passed, 21 ignored.
198+
- `cargo clippy -p vortex-array -p vortex-fastlanes --all-targets --all-features -- -D warnings`: passed.
199+
- `cargo clippy --all-targets --all-features`: passed across the workspace.
200+
- `cargo +nightly-2026-09-10 fmt --all --check`: passed.
201+
- Three passes of both benchmark matrices: all result/size assertions passed.
202+
203+
The workspace build warned that clang-format was unavailable for a generated DuckDB header;
204+
no C++ or CUDA sources were changed.
205+
206+
x86 performance and end-to-end query workloads have not been measured for this draft.

‎narrow-array-design.md‎

Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
1+
<!-- SPDX-License-Identifier: Apache-2.0 -->
2+
<!-- SPDX-FileCopyrightText: Copyright the Vortex contributors -->
3+
4+
# NarrowArray prototype
5+
6+
`NarrowArray` is an ordinary array encoding that keeps a wide logical integer dtype while
7+
storing its values in a narrower child. This draft is stacked on comparison optimization
8+
PR #9948, which specializes bitmap construction for primitive i8/u8 comparisons.
9+
10+
```text
11+
NarrowArray(dtype = i64)
12+
└── PrimitiveArray(dtype = i8)
13+
```
14+
15+
The child can use any encoding with the required integer dtype, including bitpacking or a
16+
dictionary. The wrapper stores no value buffers. Signedness and nullability must match;
17+
the child must be strictly narrower. Nested wrappers are flattened.
18+
19+
## Construction
20+
21+
- `NarrowArray::try_new(child, dtype)` wraps an existing narrow child without scanning it.
22+
- `NarrowArray::encode(primitive, ctx)` scans non-null bounds, selects the smallest fitting
23+
integer type of the same signedness, and converts the buffer once. It returns the original
24+
array if no smaller type fits. Existing exact bounds can avoid the scan.
25+
26+
This preserves a useful distinction from a general cast: every child value is representable
27+
in the logical dtype, and widening preserves ordering and equality. The invariant allows
28+
comparisons to use the child's dtype without inspecting individual values.
29+
30+
## Execution
31+
32+
| Operation | Behavior |
33+
| --- | --- |
34+
| Compare to a fitting constant | Cast the constant once and compare the narrow child. |
35+
| Compare to an out-of-range constant | Produce the determined boolean values, preserving nulls. |
36+
| Compare two NarrowArrays with the same child dtype | Compare their children directly. |
37+
| Slice, filter, take, mask | Push into the child and retain the logical dtype. |
38+
| Cast to the child's exact dtype | Unwrap the child. |
39+
| Cast to another safely wider dtype | Rewrap the same child. |
40+
| Scalar access | Return a scalar at the logical dtype. |
41+
| Canonical execution | Execute a widening cast, allowing the child's cast kernel to participate. |
42+
| Other operations, including mixed child widths | Use the existing canonical fallback. |
43+
44+
Selection may retain a lazy child. Calling `execute::<PrimitiveArray>` on the result still
45+
requests a wide canonical buffer. The selection/comparison pipeline benchmarks execute through
46+
the public array operations; they do not count construction of an unevaluated child as work done.
47+
48+
## Serialization
49+
50+
The prototype uses encoding ID `vortex.narrow` and one metadata byte for the child's PType.
51+
Deserialization reconstructs the child at its stored width. Widening happens when a consumer
52+
requests canonical execution, not while reading the NarrowArray.
53+
54+
The encoding is registered in the array session. No released file edition has been modified
55+
to admit it, and the compressor does not automatically produce it.
56+
57+
## Scope and open work
58+
59+
This draft supports signed and unsigned primitive integers. It does not change
60+
`PrimitiveArray::narrow`, decimal storage, or DecimalByteParts. DecimalArray already permits
61+
coefficient storage widths independent of its logical decimal dtype; decimal kernels and
62+
DecimalByteParts integration need a separate design and measurements.
63+
64+
There are no specialized arithmetic or aggregate kernels yet. Arithmetic must retain logical
65+
overflow behavior, so operations such as `i64(120) + i64(120)` cannot simply execute in i8.
66+
General cast expressions are not rewritten into NarrowArray, avoiding a loop with canonical
67+
widening. Mixed-width comparison dispatch and automatic compressor selection remain open.
68+
Canonical execution after take also needs attention: the existing dictionary cast rule
69+
widens the full values child before gathering, which regresses the take-to-i64 benchmark.
70+
71+
The measured benefits and costs are recorded in [the benchmark report](narrow-array-benchmarks.md).
72+
The report distinguishes buffer savings from whole-process memory usage and prebuilt-array
73+
compute from encoding and materialization costs.

‎vortex-array/Cargo.toml‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -315,3 +315,11 @@ harness = false
315315
[[bench]]
316316
name = "slice_dict_primitive"
317317
harness = false
318+
319+
[[bench]]
320+
name = "narrow_compare"
321+
harness = false
322+
323+
[[bench]]
324+
name = "narrow"
325+
harness = false

0 commit comments

Comments
 (0)