Skip to content

Commit 68e0e58

Browse files
authored
Optimize ChunkedArray take routing (#9224)
## Summary - replace global comparison sorting in `ChunkedArray::take` with per-chunk index buckets - route monotonic indices with a linear chunk cursor and arbitrary indices with binary search over chunk offsets - preserve original ordering, nulls, duplicates, nested dtypes, and bounds behavior - skip the final reorder take when non-nullable indices are already monotonic - add a deterministic 32-case Divan benchmark covering ordering, chunk counts, duplicate density, nullability, nested values, and routing patterns ## Why The previous implementation sorted every valid `(global_index, original_position)` pair, then filtered each touched chunk before taking again to restore order. That made chunk routing approximately `O(M log M + C)`. Bucketing removes the global comparison sort: arbitrary routing is approximately `O(M log C + C)`, while monotonic routing is `O(M + C)`. ## Benchmarks Command, run sequentially against the original implementation and this branch: ```bash CARGO_INCREMENTAL=0 cargo bench -p vortex-array --bench take_chunked -- --sample-count 100 ``` Source length was 1,048,576 rows. Nested cases used `RecursiveCanonical` so child values were fully materialized. Values below are medians from 100 Divan samples. All 32 candidate medians improved. ### Core ordering | Pattern | Chunks | Indices | Before | After | Speedup | |---|---:|---:|---:|---:|---:| | Shuffled | 16 | 10,000 | 205.1 µs | 66.49 µs | 3.08× | | Shuffled | 16 | 100,000 | 2.460 ms | 576.5 µs | 4.27× | | Shuffled | 1,024 | 10,000 | 838.5 µs | 608.4 µs | 1.38× | | Shuffled | 1,024 | 100,000 | 3.240 ms | 1.631 ms | 1.99× | | Sorted | 16 | 10,000 | 92.74 µs | 44.02 µs | 2.11× | | Sorted | 16 | 100,000 | 850.1 µs | 315.1 µs | 2.70× | | Sorted | 1,024 | 10,000 | 698.0 µs | 501.9 µs | 1.39× | | Sorted | 1,024 | 100,000 | 1.622 ms | 907.7 µs | 1.79× | ### Small request count / high chunk count | Chunks | Indices | Before | After | Speedup | |---:|---:|---:|---:|---:| | 1,024 | 1 | 2.916 µs | 2.124 µs | 1.37× | | 1,024 | 16 | 18.74 µs | 8.666 µs | 2.16× | | 1,024 | 256 | 139.5 µs | 97.16 µs | 1.44× | | 1,024 | 1,000 | 349.9 µs | 269.4 µs | 1.30× | | 16,384 | 1 | 16.43 µs | 15.66 µs | 1.05× | | 16,384 | 16 | 131.8 µs | 24.08 µs | 5.47× | | 16,384 | 256 | 445.4 µs | 122.8 µs | 3.63× | | 16,384 | 1,000 | 929.0 µs | 419.4 µs | 2.22× | ### Duplicate density | Pattern | Chunks | Indices | Before | After | Speedup | |---|---:|---:|---:|---:|---:| | One repeated index | 16 | 100,000 | 364.9 µs | 273.7 µs | 1.33× | | 90% duplicates | 16 | 100,000 | 1.859 ms | 529.2 µs | 3.51× | | 99% duplicates | 16 | 100,000 | 1.825 ms | 520.3 µs | 3.51× | ### Value shape | Pattern | Value | Chunks | Indices | Before | After | Speedup | |---|---|---:|---:|---:|---:|---:| | 99% duplicates | Primitive | 16 | 10,000 | 125.0 µs | 62.81 µs | 1.99× | | 99% duplicates | Struct, 8 fields | 16 | 10,000 | 1.134 ms | 701.2 µs | 1.62× | | 99% duplicates | Fixed-size list, width 8 | 16 | 10,000 | 1.468 ms | 648.5 µs | 2.26× | | Shuffled | Primitive | 16 | 10,000 | 163.4 µs | 65.91 µs | 2.48× | | Shuffled | Struct, 8 fields | 16 | 10,000 | 1.733 ms | 779.5 µs | 2.22× | | Shuffled | Fixed-size list, width 8 | 16 | 10,000 | 2.150 ms | 664.6 µs | 3.24× | ### Nullable sorted indices | Validity | Chunks | Indices | Before | After | Speedup | |---|---:|---:|---:|---:|---:| | Nullable, all valid | 16 | 100,000 | 776.7 µs | 370.8 µs | 2.09× | | Nullable, all valid | 1,024 | 100,000 | 1.513 ms | 957.1 µs | 1.58× | | Nullable, 10% null | 16 | 100,000 | 777.8 µs | 395.2 µs | 1.97× | | Nullable, 10% null | 1,024 | 100,000 | 1.502 ms | 1.016 ms | 1.48× | ### Chunk routing patterns | Pattern | Chunks | Indices | Before | After | Speedup | |---|---:|---:|---:|---:|---:| | Same-chunk random | 1,024 | 100,000 | 1.830 ms | 614.1 µs | 2.98× | | Alternating first/last chunk | 1,024 | 100,000 | 2.027 ms | 757.7 µs | 2.68× | | Grouped by chunk | 1,024 | 100,000 | 2.814 ms | 1.490 ms | 1.89× | ## Validation - `CARGO_INCREMENTAL=0 cargo test -p vortex-array --lib arrays::chunked::compute::take::test` — 10 passed - `CARGO_INCREMENTAL=0 cargo clippy --all-targets --all-features` - `cargo +nightly fmt --all -- --check` - `git diff --check` --------- Signed-off-by: "Nicholas Gates" <[email protected]> Signed-off-by: Nicholas Gates <[email protected]>
1 parent 77e7bc2 commit 68e0e58

4 files changed

Lines changed: 579 additions & 62 deletions

File tree

‎vortex-array/Cargo.toml‎

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

230+
[[bench]]
231+
name = "take_chunked"
232+
harness = false
233+
230234
[[bench]]
231235
name = "piecewise_sequence_take_primitive"
232236
harness = false
Lines changed: 355 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,355 @@
1+
// SPDX-License-Identifier: Apache-2.0
2+
// SPDX-FileCopyrightText: Copyright the Vortex contributors
3+
4+
//! Benchmarks [`ChunkedArray`] take routing across ordering, chunk count, duplicate density,
5+
//! nullability, and value-shape configurations.
6+
7+
#![expect(clippy::unwrap_used)]
8+
9+
use std::fmt::Display;
10+
use std::fmt::Formatter;
11+
12+
use divan::Bencher;
13+
use divan::counter::ItemsCount;
14+
use vortex_array::ArrayRef;
15+
use vortex_array::IntoArray;
16+
use vortex_array::RecursiveCanonical;
17+
use vortex_array::VortexSessionExecute;
18+
use vortex_array::array_session;
19+
use vortex_array::arrays::ChunkedArray;
20+
use vortex_array::arrays::FixedSizeListArray;
21+
use vortex_array::arrays::PrimitiveArray;
22+
use vortex_array::arrays::StructArray;
23+
use vortex_array::dtype::FieldNames;
24+
use vortex_array::validity::Validity;
25+
use vortex_buffer::Buffer;
26+
27+
fn main() {
28+
divan::main();
29+
}
30+
31+
const SOURCE_LEN: usize = 1 << 20;
32+
const NESTED_WIDTH: usize = 8;
33+
34+
#[derive(Clone, Copy)]
35+
enum Pattern {
36+
Sorted,
37+
Shuffled,
38+
Repeated,
39+
Duplicate90,
40+
Duplicate99,
41+
SameChunk,
42+
AlternatingChunks,
43+
GroupedChunks,
44+
}
45+
46+
impl Display for Pattern {
47+
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
48+
f.write_str(match self {
49+
Self::Sorted => "sorted",
50+
Self::Shuffled => "shuffled",
51+
Self::Repeated => "repeated",
52+
Self::Duplicate90 => "duplicate90",
53+
Self::Duplicate99 => "duplicate99",
54+
Self::SameChunk => "same_chunk",
55+
Self::AlternatingChunks => "alternating_chunks",
56+
Self::GroupedChunks => "grouped_chunks",
57+
})
58+
}
59+
}
60+
61+
#[derive(Clone, Copy)]
62+
enum ValueKind {
63+
Primitive,
64+
Struct8,
65+
FixedSizeList8,
66+
}
67+
68+
impl Display for ValueKind {
69+
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
70+
f.write_str(match self {
71+
Self::Primitive => "primitive",
72+
Self::Struct8 => "struct8",
73+
Self::FixedSizeList8 => "fsl8",
74+
})
75+
}
76+
}
77+
78+
#[derive(Clone, Copy)]
79+
enum IndexValidity {
80+
NonNullable,
81+
AllValid,
82+
TenPercentNull,
83+
}
84+
85+
impl Display for IndexValidity {
86+
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
87+
f.write_str(match self {
88+
Self::NonNullable => "nonnull",
89+
Self::AllValid => "nullable_all_valid",
90+
Self::TenPercentNull => "nullable_10pct_null",
91+
})
92+
}
93+
}
94+
95+
#[derive(Clone, Copy)]
96+
struct Case {
97+
group: &'static str,
98+
pattern: Pattern,
99+
value_kind: ValueKind,
100+
validity: IndexValidity,
101+
chunks: usize,
102+
indices: usize,
103+
}
104+
105+
impl Case {
106+
const fn new(group: &'static str, pattern: Pattern, chunks: usize, indices: usize) -> Self {
107+
Self {
108+
group,
109+
pattern,
110+
value_kind: ValueKind::Primitive,
111+
validity: IndexValidity::NonNullable,
112+
chunks,
113+
indices,
114+
}
115+
}
116+
117+
const fn with_value_kind(mut self, value_kind: ValueKind) -> Self {
118+
self.value_kind = value_kind;
119+
self
120+
}
121+
122+
const fn with_validity(mut self, validity: IndexValidity) -> Self {
123+
self.validity = validity;
124+
self
125+
}
126+
}
127+
128+
impl Display for Case {
129+
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
130+
write!(
131+
f,
132+
"{}/{}/{}/{}/chunks={}/indices={}",
133+
self.group, self.pattern, self.value_kind, self.validity, self.chunks, self.indices
134+
)
135+
}
136+
}
137+
138+
fn cases() -> Vec<Case> {
139+
let mut cases = Vec::new();
140+
141+
for pattern in [Pattern::Sorted, Pattern::Shuffled] {
142+
for chunks in [16, 1_024] {
143+
for indices in [10_000, 100_000] {
144+
cases.push(Case::new("core", pattern, chunks, indices));
145+
}
146+
}
147+
}
148+
149+
for chunks in [1_024, 16_384] {
150+
for indices in [1, 16, 256, 1_000] {
151+
cases.push(Case::new("small_m", Pattern::Shuffled, chunks, indices));
152+
}
153+
}
154+
155+
for pattern in [
156+
Pattern::Repeated,
157+
Pattern::Duplicate90,
158+
Pattern::Duplicate99,
159+
] {
160+
cases.push(Case::new("duplicates", pattern, 16, 100_000));
161+
}
162+
163+
for pattern in [Pattern::Shuffled, Pattern::Duplicate99] {
164+
for value_kind in [
165+
ValueKind::Primitive,
166+
ValueKind::Struct8,
167+
ValueKind::FixedSizeList8,
168+
] {
169+
cases.push(Case::new("value_shape", pattern, 16, 10_000).with_value_kind(value_kind));
170+
}
171+
}
172+
173+
for chunks in [16, 1_024] {
174+
for validity in [IndexValidity::AllValid, IndexValidity::TenPercentNull] {
175+
cases.push(
176+
Case::new("nullable", Pattern::Sorted, chunks, 100_000).with_validity(validity),
177+
);
178+
}
179+
}
180+
181+
for pattern in [
182+
Pattern::SameChunk,
183+
Pattern::AlternatingChunks,
184+
Pattern::GroupedChunks,
185+
] {
186+
cases.push(Case::new("routing", pattern, 1_024, 100_000));
187+
}
188+
189+
cases
190+
}
191+
192+
fn primitive_values(start: usize, end: usize) -> ArrayRef {
193+
PrimitiveArray::from_iter((start..end).map(|value| u64::try_from(value).unwrap())).into_array()
194+
}
195+
196+
fn chunk_values(value_kind: ValueKind, start: usize, end: usize) -> ArrayRef {
197+
match value_kind {
198+
ValueKind::Primitive => primitive_values(start, end),
199+
ValueKind::Struct8 => {
200+
let fields: Vec<_> = (0..NESTED_WIDTH)
201+
.map(|field| {
202+
let field_offset = u64::try_from(field * SOURCE_LEN).unwrap();
203+
PrimitiveArray::from_iter(
204+
(start..end).map(|value| u64::try_from(value).unwrap() + field_offset),
205+
)
206+
.into_array()
207+
})
208+
.collect();
209+
StructArray::try_new(
210+
FieldNames::from(["f0", "f1", "f2", "f3", "f4", "f5", "f6", "f7"]),
211+
fields,
212+
end - start,
213+
Validity::NonNullable,
214+
)
215+
.unwrap()
216+
.into_array()
217+
}
218+
ValueKind::FixedSizeList8 => {
219+
let element_start = start * NESTED_WIDTH;
220+
let element_end = end * NESTED_WIDTH;
221+
FixedSizeListArray::new(
222+
primitive_values(element_start, element_end),
223+
u32::try_from(NESTED_WIDTH).unwrap(),
224+
Validity::NonNullable,
225+
end - start,
226+
)
227+
.into_array()
228+
}
229+
}
230+
}
231+
232+
fn chunked_values(case: Case) -> ArrayRef {
233+
let chunk_len = SOURCE_LEN / case.chunks;
234+
let chunks = (0..case.chunks)
235+
.map(|chunk_idx| {
236+
let start = chunk_idx * chunk_len;
237+
let end = start + chunk_len;
238+
chunk_values(case.value_kind, start, end)
239+
})
240+
.collect::<Vec<_>>();
241+
let dtype = chunks[0].dtype().clone();
242+
ChunkedArray::try_new(chunks, dtype).unwrap().into_array()
243+
}
244+
245+
fn advance_random(state: &mut u64) -> u64 {
246+
*state = state
247+
.wrapping_mul(6_364_136_223_846_793_005)
248+
.wrapping_add(1_442_695_040_888_963_407);
249+
*state
250+
}
251+
252+
fn index_values(case: Case) -> Vec<u64> {
253+
let mut state = 0x4d59_5df4_d0f3_3173u64;
254+
let mut indices = match case.pattern {
255+
Pattern::Sorted | Pattern::Shuffled => (0..case.indices)
256+
.map(|_| advance_random(&mut state) % u64::try_from(SOURCE_LEN).unwrap())
257+
.collect(),
258+
Pattern::Repeated => vec![u64::try_from(SOURCE_LEN / 2).unwrap(); case.indices],
259+
Pattern::Duplicate90 | Pattern::Duplicate99 => {
260+
let divisor = match case.pattern {
261+
Pattern::Duplicate90 => 10,
262+
Pattern::Duplicate99 => 100,
263+
_ => unreachable!(),
264+
};
265+
let unique_count = (case.indices / divisor).max(1);
266+
(0..case.indices)
267+
.map(|_| {
268+
let slot = usize::try_from(
269+
advance_random(&mut state) % u64::try_from(unique_count).unwrap(),
270+
)
271+
.unwrap();
272+
u64::try_from(slot * SOURCE_LEN / unique_count).unwrap()
273+
})
274+
.collect()
275+
}
276+
Pattern::SameChunk => {
277+
let chunk_len = SOURCE_LEN / case.chunks;
278+
let chunk_start = (case.chunks / 2) * chunk_len;
279+
(0..case.indices)
280+
.map(|_| {
281+
let local = usize::try_from(
282+
advance_random(&mut state) % u64::try_from(chunk_len).unwrap(),
283+
)
284+
.unwrap();
285+
u64::try_from(chunk_start + local).unwrap()
286+
})
287+
.collect()
288+
}
289+
Pattern::AlternatingChunks => {
290+
let chunk_len = SOURCE_LEN / case.chunks;
291+
(0..case.indices)
292+
.map(|position| {
293+
let chunk_idx = if position.is_multiple_of(2) {
294+
0
295+
} else {
296+
case.chunks - 1
297+
};
298+
let local = position / 2 % chunk_len;
299+
u64::try_from(chunk_idx * chunk_len + local).unwrap()
300+
})
301+
.collect()
302+
}
303+
Pattern::GroupedChunks => {
304+
let chunk_len = SOURCE_LEN / case.chunks;
305+
(0..case.indices)
306+
.map(|position| {
307+
let chunk_idx = position * case.chunks / case.indices;
308+
let local = usize::try_from(
309+
advance_random(&mut state) % u64::try_from(chunk_len).unwrap(),
310+
)
311+
.unwrap();
312+
u64::try_from(chunk_idx * chunk_len + local).unwrap()
313+
})
314+
.collect()
315+
}
316+
};
317+
318+
if matches!(case.pattern, Pattern::Sorted) {
319+
indices.sort_unstable();
320+
}
321+
indices
322+
}
323+
324+
fn take_indices(case: Case) -> ArrayRef {
325+
let indices = index_values(case);
326+
match case.validity {
327+
IndexValidity::NonNullable => PrimitiveArray::from_iter(indices).into_array(),
328+
IndexValidity::AllValid => {
329+
PrimitiveArray::new(Buffer::from(indices), Validity::AllValid).into_array()
330+
}
331+
IndexValidity::TenPercentNull => PrimitiveArray::new(
332+
Buffer::from(indices),
333+
Validity::from_iter((0..case.indices).map(|index| !index.is_multiple_of(10))),
334+
)
335+
.into_array(),
336+
}
337+
}
338+
339+
#[divan::bench(args = cases())]
340+
fn take(bencher: Bencher, case: Case) {
341+
let values = chunked_values(case);
342+
let indices = take_indices(case);
343+
let session = array_session();
344+
345+
bencher
346+
.counter(ItemsCount::new(case.indices))
347+
.with_inputs(|| (indices.clone(), session.create_execution_ctx()))
348+
.bench_refs(|(indices, ctx)| {
349+
values
350+
.take(indices.clone())
351+
.unwrap()
352+
.execute::<RecursiveCanonical>(ctx)
353+
.unwrap()
354+
});
355+
}

0 commit comments

Comments
 (0)