Skip to content

Commit 5fc5cb8

Browse files
Decode short RunEnd runs with fixed-size block writes (#10488)
In TPC-DS, the RunEnd arrays that scans decode are mostly dictionary codes (`u16`, ~6 rows per run) and nullable `i64` keys (~7 rows per run). Filling each run with a loop sized to its length cost more than the fill: about 9 ns per 2-row run. ## Changes A run that fits in a block of at least 8 elements and 32 bytes (8 for `i64`, 16 for `u16`) now writes the whole block, which compiles to a few vector stores, and the next run overwrites the excess. Longer runs are filled exactly. The buffer keeps one block of spare capacity so the last run's block stays in bounds. Both the all-valid and nullable decode paths use it. Adds the `run_end_decode_primitive` benchmark. 65,536 rows, fastest of 200: | rows/run, nulls | i64 before | i64 after | u16 before | u16 after | | --------------- | ---------- | --------- | ---------- | --------- | | 1 | 164 µs | 224 µs | 136 µs | 198 µs | | 2, 4% | 345 µs | 138 µs | 362 µs | 123 µs | | 7 | 109 µs | 54 µs | 127 µs | 34 µs | | 7, 4% | 138 µs | 70 µs | 147 µs | 47 µs | | 26 | 24 µs | 25 µs | 12 µs | 14 µs | | 100 | 18 µs | 18 µs | 6.6 µs | 7.5 µs |
1 parent 94d2782 commit 5fc5cb8

3 files changed

Lines changed: 174 additions & 26 deletions

File tree

‎encodings/runend/Cargo.toml‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -61,3 +61,7 @@ harness = false
6161
[[bench]]
6262
name = "run_end_sum"
6363
harness = false
64+
65+
[[bench]]
66+
name = "run_end_decode_primitive"
67+
harness = false
Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
1+
// SPDX-License-Identifier: Apache-2.0
2+
// SPDX-FileCopyrightText: Copyright the Vortex contributors
3+
4+
//! Decoding primitive run-end arrays, in the shapes that dictionary codes and nullable keys take
5+
//! in TPC-DS: short runs, with and without nulls.
6+
7+
#![expect(clippy::cast_possible_truncation)]
8+
9+
use std::sync::LazyLock;
10+
11+
use divan::Bencher;
12+
use mimalloc::MiMalloc;
13+
use rand::RngExt;
14+
use rand::SeedableRng;
15+
use rand::rngs::StdRng;
16+
use vortex_array::VortexSessionExecute;
17+
use vortex_array::arrays::PrimitiveArray;
18+
use vortex_array::dtype::NativePType;
19+
use vortex_array::validity::Validity;
20+
use vortex_buffer::BitBuffer;
21+
use vortex_buffer::Buffer;
22+
use vortex_runend::compress::runend_decode_primitive;
23+
use vortex_session::VortexSession;
24+
25+
#[global_allocator]
26+
static GLOBAL: MiMalloc = MiMalloc;
27+
28+
fn main() {
29+
divan::main();
30+
}
31+
32+
static SESSION: LazyLock<VortexSession> = LazyLock::new(|| {
33+
let session = vortex_array::array_session();
34+
vortex_runend::initialize(&session);
35+
session
36+
});
37+
38+
const LEN: usize = 16_384;
39+
40+
/// `(average run length, fraction of null runs)`.
41+
const ARGS: &[(usize, f64)] = &[
42+
(1, 0.0),
43+
(2, 0.04),
44+
(7, 0.0),
45+
(7, 0.04),
46+
(26, 0.0),
47+
(100, 0.0),
48+
];
49+
50+
fn bench_decode<T: NativePType>(
51+
bencher: Bencher,
52+
avg_run: usize,
53+
null_frac: f64,
54+
value: fn(u64) -> T,
55+
) {
56+
let mut rng = StdRng::seed_from_u64(7);
57+
let (mut ends, mut values, mut valid) = (Vec::new(), Vec::new(), Vec::new());
58+
let mut pos = 0usize;
59+
while pos < LEN {
60+
pos = (pos + rng.random_range(1..=2 * avg_run - 1)).min(LEN);
61+
ends.push(pos as u32);
62+
values.push(value(rng.random_range(0..1_000)));
63+
valid.push(!rng.random_bool(null_frac));
64+
}
65+
let ends = PrimitiveArray::new(Buffer::from(ends), Validity::NonNullable);
66+
let validity = if null_frac > 0.0 {
67+
Validity::from(BitBuffer::from_iter(valid))
68+
} else {
69+
Validity::NonNullable
70+
};
71+
let values = PrimitiveArray::new(Buffer::from(values), validity);
72+
bencher
73+
.with_inputs(|| (ends.clone(), values.clone(), SESSION.create_execution_ctx()))
74+
.bench_refs(|(ends, values, ctx)| {
75+
runend_decode_primitive(ends.clone(), values.clone(), 0, LEN, ctx)
76+
});
77+
}
78+
79+
#[divan::bench(args = ARGS)]
80+
fn decode_i64(bencher: Bencher, (avg_run, null_frac): (usize, f64)) {
81+
bench_decode(bencher, avg_run, null_frac, |v| v as i64);
82+
}
83+
84+
#[divan::bench(args = ARGS)]
85+
fn decode_u16(bencher: Bencher, (avg_run, null_frac): (usize, f64)) {
86+
bench_decode(bencher, avg_run, null_frac, |v| v as u16);
87+
}

‎encodings/runend/src/compress.rs‎

Lines changed: 83 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -226,40 +226,24 @@ fn runend_decode_slice<T: Copy + Default>(
226226
) -> (Buffer<T>, Validity) {
227227
match values_validity {
228228
Mask::AllTrue(_) => {
229-
let mut decoded: BufferMut<T> = BufferMut::with_capacity(length);
230-
for (end, value) in run_ends.zip_eq(values) {
231-
assert!(
232-
end >= decoded.len(),
233-
"Runend ends must be monotonic, got {end} after {}",
234-
decoded.len()
235-
);
236-
assert!(end <= length, "Runend end must be less than overall length");
237-
// SAFETY:
238-
// We preallocate enough capacity because we know the total length
239-
unsafe { decoded.push_n_unchecked(*value, end - decoded.len()) };
229+
let mut decoded = RunWriter::new(length);
230+
for (end, &value) in run_ends.zip_eq(values) {
231+
decoded.write_run(value, end);
240232
}
241-
(decoded.into(), values_nullability.into())
233+
(decoded.finish(), values_nullability.into())
242234
}
243235
Mask::AllFalse(_) => (Buffer::<T>::zeroed(length), Validity::AllInvalid),
244236
Mask::Values(mask) => {
245237
// Nulls are usually rare and clustered, so start from all-valid and clear each
246238
// maximal streak of null runs once, rather than appending validity per run.
247-
let mut decoded: BufferMut<T> = BufferMut::with_capacity(length);
239+
let mut decoded = RunWriter::new(length);
248240
let mut decoded_validity = BitBufferMut::full(true, length);
249241
let mut null_start = None;
250242
for (end, (&value, is_valid)) in
251243
run_ends.zip_eq(values.iter().zip(mask.bit_buffer().iter()))
252244
{
253245
let start = decoded.len();
254-
assert!(
255-
end >= start,
256-
"Runend ends must be monotonic, got {end} after {start}"
257-
);
258-
assert!(end <= length, "Runend end must be less than overall length");
259-
let value = if is_valid { value } else { T::default() };
260-
// SAFETY:
261-
// We preallocate enough capacity because we know the total length
262-
unsafe { decoded.push_n_unchecked(value, end - start) };
246+
decoded.write_run(if is_valid { value } else { T::default() }, end);
263247
match (is_valid, null_start) {
264248
(false, None) => null_start = Some(start),
265249
(true, Some(null_from)) => {
@@ -270,17 +254,90 @@ fn runend_decode_slice<T: Copy + Default>(
270254
_ => {}
271255
}
272256
}
257+
let decoded = decoded.finish();
273258
if let Some(null_from) = null_start {
274-
let end = decoded.len();
275-
// SAFETY: null_from <= end <= length == decoded_validity.len()
276-
unsafe { decoded_validity.fill_range_unchecked(null_from, end, false) };
259+
// SAFETY: null_from <= decoded.len() <= length == decoded_validity.len()
260+
unsafe { decoded_validity.fill_range_unchecked(null_from, decoded.len(), false) };
277261
}
278262
decoded_validity.truncate(decoded.len());
279-
(decoded.into(), Validity::from(decoded_validity.freeze()))
263+
(decoded, Validity::from(decoded_validity.freeze()))
280264
}
281265
}
282266
}
283267

268+
/// Minimum bytes in a [`RunWriter`] block.
269+
const BLOCK_BYTES: usize = 32;
270+
271+
/// Writes runs of values into a buffer of up to `length` elements.
272+
///
273+
/// Runs are usually short, and filling each one with a loop sized to its length costs more than
274+
/// the fill itself. Instead a run that fits in a fixed block writes the whole block, which the
275+
/// compiler lowers to a few vector stores, and the next run overwrites whatever went past its
276+
/// end. Longer runs are filled exactly. The buffer has a block of spare capacity so that the last
277+
/// run's block stays in bounds.
278+
struct RunWriter<T> {
279+
buffer: BufferMut<T>,
280+
len: usize,
281+
length: usize,
282+
}
283+
284+
impl<T: Copy> RunWriter<T> {
285+
/// Elements in a block: enough to cover most short runs, at least 8 elements and 32 bytes.
286+
const BLOCK: usize = if size_of::<T>() == 0 || size_of::<T>() >= BLOCK_BYTES / 8 {
287+
8
288+
} else {
289+
BLOCK_BYTES / size_of::<T>()
290+
};
291+
292+
fn new(length: usize) -> Self {
293+
Self {
294+
buffer: BufferMut::with_capacity(length + Self::BLOCK),
295+
len: 0,
296+
length,
297+
}
298+
}
299+
300+
fn len(&self) -> usize {
301+
self.len
302+
}
303+
304+
/// Fill `self.len()..end` with `value`.
305+
#[inline]
306+
fn write_run(&mut self, value: T, end: usize) {
307+
assert!(
308+
end >= self.len,
309+
"Runend ends must be monotonic, got {end} after {}",
310+
self.len
311+
);
312+
assert!(
313+
end <= self.length,
314+
"Runend end must be less than overall length"
315+
);
316+
// SAFETY: `self.len <= end <= length`, and the buffer holds `length + BLOCK` elements, so
317+
// both the block and the remainder of the run are in bounds.
318+
unsafe {
319+
let dst = self.buffer.as_mut_ptr().add(self.len);
320+
let run_len = end - self.len;
321+
if run_len <= Self::BLOCK {
322+
for i in 0..Self::BLOCK {
323+
dst.add(i).write(value);
324+
}
325+
} else {
326+
for i in 0..run_len {
327+
dst.add(i).write(value);
328+
}
329+
}
330+
}
331+
self.len = end;
332+
}
333+
334+
fn finish(mut self) -> Buffer<T> {
335+
// SAFETY: every element below `self.len` was written by a run.
336+
unsafe { self.buffer.set_len(self.len) };
337+
self.buffer.freeze()
338+
}
339+
}
340+
284341
pub fn runend_decode_typed_primitive<T: NativePType>(
285342
run_ends: impl Iterator<Item = usize>,
286343
values: &[T],

0 commit comments

Comments
 (0)