Skip to content

Commit 62af4a1

Browse files
authored
Add PiecewiseSequence take microbenchmarks (#8830)
## Summary - add `piecewise_sequence_take_primitive` to compare constant-length PiecewiseSequence take against dense lengths and reifying constant lengths - add `take_slices_to_buffer_matrix` to compare extend/cursor-copy loops with and without preverification plus unchecked slicing ## Validation - `cargo +nightly fmt --all` - `cargo clippy -p vortex-array --all-targets --all-features -- -D warnings` - `cargo bench -p vortex-array --bench piecewise_sequence_take_primitive` - `cargo bench -p vortex-array --bench take_slices_to_buffer_matrix` --------- Signed-off-by: Daniel King <[email protected]>
1 parent 1e2df53 commit 62af4a1

3 files changed

Lines changed: 482 additions & 0 deletions

File tree

‎vortex-array/Cargo.toml‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -227,6 +227,14 @@ harness = false
227227
name = "take_primitive"
228228
harness = false
229229

230+
[[bench]]
231+
name = "piecewise_sequence_take_primitive"
232+
harness = false
233+
234+
[[bench]]
235+
name = "take_slices_to_buffer_matrix"
236+
harness = false
237+
230238
[[bench]]
231239
name = "take_struct"
232240
harness = false
Lines changed: 163 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,163 @@
1+
// SPDX-License-Identifier: Apache-2.0
2+
// SPDX-FileCopyrightText: Copyright the Vortex contributors
3+
4+
//! Primitive take benchmarks for [`PiecewiseSequenceArray`] length representations.
5+
//!
6+
//! The `reify_constant_lengths_then_take` case simulates removing the constant-length
7+
//! specialization: it starts with constant lengths, materializes them to a dense primitive array,
8+
//! and then executes the primitive take through the non-constant-length path.
9+
10+
#![allow(clippy::cast_possible_truncation)]
11+
#![expect(clippy::unwrap_used)]
12+
13+
use std::sync::LazyLock;
14+
15+
use divan::Bencher;
16+
use divan::counter::BytesCount;
17+
use rand::SeedableRng;
18+
use rand::prelude::*;
19+
use vortex_array::ArrayRef;
20+
use vortex_array::IntoArray;
21+
use vortex_array::VortexSessionExecute;
22+
use vortex_array::array_session;
23+
use vortex_array::arrays::ConstantArray;
24+
use vortex_array::arrays::PiecewiseSequenceArray;
25+
use vortex_array::arrays::PrimitiveArray;
26+
use vortex_session::VortexSession;
27+
28+
fn main() {
29+
LazyLock::force(&SESSION);
30+
divan::main();
31+
}
32+
33+
static SESSION: LazyLock<VortexSession> = LazyLock::new(array_session);
34+
35+
const SOURCE_LEN: usize = 512 * 1024;
36+
const OUTPUT_LEN: usize = 8 * 1024;
37+
const RUN_LENGTHS: &[usize] = &[1, 4, 16, 64, 256];
38+
39+
#[divan::bench(args = RUN_LENGTHS)]
40+
fn optimized_constant_lengths(bencher: Bencher, run_length: usize) {
41+
let values = values();
42+
let indices = piecewise_indices(
43+
run_length,
44+
lengths_constant(run_length, run_count(run_length)),
45+
);
46+
47+
bencher
48+
.counter(BytesCount::of_many::<i64>(OUTPUT_LEN))
49+
.with_inputs(|| (&values, indices.clone(), SESSION.create_execution_ctx()))
50+
.bench_refs(|(values, indices, ctx)| {
51+
divan::black_box(
52+
values
53+
.clone()
54+
.take(indices.clone())
55+
.unwrap()
56+
.execute::<PrimitiveArray>(ctx)
57+
.unwrap(),
58+
);
59+
});
60+
}
61+
62+
#[divan::bench(args = RUN_LENGTHS)]
63+
fn prebuilt_dense_lengths(bencher: Bencher, run_length: usize) {
64+
let values = values();
65+
let indices = piecewise_indices(run_length, lengths_dense(run_length, run_count(run_length)));
66+
67+
bencher
68+
.counter(BytesCount::of_many::<i64>(OUTPUT_LEN))
69+
.with_inputs(|| (&values, indices.clone(), SESSION.create_execution_ctx()))
70+
.bench_refs(|(values, indices, ctx)| {
71+
divan::black_box(
72+
values
73+
.clone()
74+
.take(indices.clone())
75+
.unwrap()
76+
.execute::<PrimitiveArray>(ctx)
77+
.unwrap(),
78+
);
79+
});
80+
}
81+
82+
#[divan::bench(args = RUN_LENGTHS)]
83+
fn reify_constant_lengths_then_take(bencher: Bencher, run_length: usize) {
84+
let values = values();
85+
let run_count = run_count(run_length);
86+
let starts = starts(run_count, run_length).into_array();
87+
let lengths = lengths_constant(run_length, run_count);
88+
let multipliers = ConstantArray::new(1u64, run_count).into_array();
89+
90+
bencher
91+
.counter(BytesCount::of_many::<i64>(OUTPUT_LEN))
92+
.with_inputs(|| {
93+
(
94+
&values,
95+
starts.clone(),
96+
lengths.clone(),
97+
multipliers.clone(),
98+
SESSION.create_execution_ctx(),
99+
)
100+
})
101+
.bench_refs(|(values, starts, lengths, multipliers, ctx)| {
102+
let lengths = lengths
103+
.clone()
104+
.execute::<PrimitiveArray>(ctx)
105+
.unwrap()
106+
.into_array();
107+
108+
// SAFETY: starts, reified lengths, and unit multipliers have the same run count, are
109+
// non-null unsigned integer arrays, and expand to OUTPUT_LEN by construction.
110+
let indices = unsafe {
111+
PiecewiseSequenceArray::new_unchecked(
112+
starts.clone(),
113+
lengths,
114+
multipliers.clone(),
115+
OUTPUT_LEN,
116+
)
117+
}
118+
.into_array();
119+
120+
divan::black_box(
121+
values
122+
.clone()
123+
.take(indices)
124+
.unwrap()
125+
.execute::<PrimitiveArray>(ctx)
126+
.unwrap(),
127+
);
128+
});
129+
}
130+
131+
fn values() -> ArrayRef {
132+
PrimitiveArray::from_iter((0..SOURCE_LEN).map(|idx| idx as i64)).into_array()
133+
}
134+
135+
fn run_count(run_length: usize) -> usize {
136+
assert_eq!(OUTPUT_LEN % run_length, 0);
137+
OUTPUT_LEN / run_length
138+
}
139+
140+
fn piecewise_indices(run_length: usize, lengths: ArrayRef) -> ArrayRef {
141+
let run_count = run_count(run_length);
142+
let starts = starts(run_count, run_length).into_array();
143+
let multipliers = ConstantArray::new(1u64, run_count).into_array();
144+
145+
// SAFETY: starts, lengths, and unit multipliers have the same run count, are non-null unsigned
146+
// integer arrays, and expand to OUTPUT_LEN by construction.
147+
unsafe { PiecewiseSequenceArray::new_unchecked(starts, lengths, multipliers, OUTPUT_LEN) }
148+
.into_array()
149+
}
150+
151+
fn lengths_constant(run_length: usize, run_count: usize) -> ArrayRef {
152+
ConstantArray::new(run_length as u64, run_count).into_array()
153+
}
154+
155+
fn lengths_dense(run_length: usize, run_count: usize) -> ArrayRef {
156+
PrimitiveArray::from_iter((0..run_count).map(|_| run_length as u64)).into_array()
157+
}
158+
159+
fn starts(run_count: usize, run_length: usize) -> PrimitiveArray {
160+
let mut rng = StdRng::seed_from_u64(0x51ced);
161+
let max_start = SOURCE_LEN - run_length;
162+
PrimitiveArray::from_iter((0..run_count).map(|_| rng.random_range(0..=max_start) as u64))
163+
}

0 commit comments

Comments
 (0)