|
| 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. |
0 commit comments