Skip to content

Commit 1718eb3

Browse files
authored
Add Patches lookup benchmarks (#7795)
Isolating benchmarks before this optimization: #7753 --------- Signed-off-by: Baris Palaska <[email protected]>
1 parent a31a0db commit 1718eb3

2 files changed

Lines changed: 170 additions & 0 deletions

File tree

‎vortex-array/Cargo.toml‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -124,6 +124,10 @@ harness = false
124124
name = "scalar_at_struct"
125125
harness = false
126126

127+
[[bench]]
128+
name = "patches_lookup"
129+
harness = false
130+
127131
[[bench]]
128132
name = "varbinview_compact"
129133
harness = false
Lines changed: 166 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,166 @@
1+
// SPDX-License-Identifier: Apache-2.0
2+
// SPDX-FileCopyrightText: Copyright the Vortex contributors
3+
4+
#![expect(clippy::unwrap_used)]
5+
#![expect(clippy::cast_possible_truncation)]
6+
7+
use divan::Bencher;
8+
use rand::RngExt;
9+
use rand::SeedableRng;
10+
use rand::rngs::StdRng;
11+
use vortex_array::IntoArray;
12+
use vortex_array::patches::PATCH_CHUNK_SIZE;
13+
use vortex_array::patches::Patches;
14+
use vortex_buffer::Buffer;
15+
16+
fn main() {
17+
divan::main();
18+
}
19+
20+
const ARRAY_LEN: usize = 1_000_000;
21+
const NUM_PATCHES: usize = 100;
22+
const NUM_QUERIES: usize = 1_000;
23+
24+
const PATCH_LOW: usize = 100_000;
25+
const PATCH_HIGH: usize = 110_000;
26+
27+
fn patches_from_indices(index_iter: impl Iterator<Item = u64>, chunked: bool) -> Patches {
28+
let mut indices: Vec<u64> = index_iter.collect();
29+
indices.sort();
30+
indices.dedup();
31+
let values: Buffer<i32> = (0..indices.len() as i32).collect();
32+
33+
let chunk_offsets = chunked.then(|| {
34+
let offsets: Vec<u64> = (0..ARRAY_LEN)
35+
.step_by(PATCH_CHUNK_SIZE)
36+
.map(|chunk_start| indices.partition_point(|&idx| (idx as usize) < chunk_start) as u64)
37+
.collect();
38+
Buffer::from(offsets).into_array()
39+
});
40+
41+
let patches = Patches::new(
42+
ARRAY_LEN,
43+
0,
44+
Buffer::from(indices).into_array(),
45+
values.into_array(),
46+
chunk_offsets,
47+
)
48+
.unwrap();
49+
if chunked {
50+
assert!(patches.chunk_offsets().is_some());
51+
}
52+
patches
53+
}
54+
55+
fn narrow_band_patches(chunked: bool) -> Patches {
56+
let mut rng = StdRng::seed_from_u64(42);
57+
patches_from_indices(
58+
(0..NUM_PATCHES).map(|_| rng.random_range((PATCH_LOW as u64)..(PATCH_HIGH as u64))),
59+
chunked,
60+
)
61+
}
62+
63+
fn full_range_patches(chunked: bool) -> Patches {
64+
let mut rng = StdRng::seed_from_u64(43);
65+
patches_from_indices(
66+
(0..NUM_PATCHES).map(|_| rng.random_range(0..(ARRAY_LEN as u64))),
67+
chunked,
68+
)
69+
}
70+
71+
fn queries_below_min() -> Vec<usize> {
72+
(0..NUM_QUERIES).collect()
73+
}
74+
75+
fn queries_above_max() -> Vec<usize> {
76+
(PATCH_HIGH..(PATCH_HIGH + NUM_QUERIES)).collect()
77+
}
78+
79+
fn queries_mixed_out_of_range() -> Vec<usize> {
80+
(0..NUM_QUERIES / 2)
81+
.map(|i| i * 100)
82+
.chain((0..NUM_QUERIES / 2).map(|i| PATCH_HIGH + i * 50))
83+
.collect()
84+
}
85+
86+
fn queries_in_range() -> Vec<usize> {
87+
let mut rng = StdRng::seed_from_u64(7);
88+
(0..NUM_QUERIES)
89+
.map(|_| rng.random_range(PATCH_LOW..PATCH_HIGH))
90+
.collect()
91+
}
92+
93+
fn queries_full_range() -> Vec<usize> {
94+
let mut rng = StdRng::seed_from_u64(11);
95+
(0..NUM_QUERIES)
96+
.map(|_| rng.random_range(0..ARRAY_LEN))
97+
.collect()
98+
}
99+
100+
fn bench_search_index(bencher: Bencher, patches: Patches, queries: Vec<usize>) {
101+
bencher
102+
.with_inputs(|| (&patches, &queries))
103+
.bench_refs(|(patches, queries)| {
104+
for &q in queries.iter() {
105+
divan::black_box(patches.search_index(q).unwrap());
106+
}
107+
});
108+
}
109+
110+
#[divan::bench]
111+
fn search_index_below_min(bencher: Bencher) {
112+
bench_search_index(bencher, narrow_band_patches(false), queries_below_min());
113+
}
114+
115+
#[divan::bench]
116+
fn search_index_below_min_chunked(bencher: Bencher) {
117+
bench_search_index(bencher, narrow_band_patches(true), queries_below_min());
118+
}
119+
120+
#[divan::bench]
121+
fn search_index_above_max(bencher: Bencher) {
122+
bench_search_index(bencher, narrow_band_patches(false), queries_above_max());
123+
}
124+
125+
#[divan::bench]
126+
fn search_index_above_max_chunked(bencher: Bencher) {
127+
bench_search_index(bencher, narrow_band_patches(true), queries_above_max());
128+
}
129+
130+
#[divan::bench]
131+
fn search_index_mixed_out_of_range(bencher: Bencher) {
132+
bench_search_index(
133+
bencher,
134+
narrow_band_patches(false),
135+
queries_mixed_out_of_range(),
136+
);
137+
}
138+
139+
#[divan::bench]
140+
fn search_index_mixed_out_of_range_chunked(bencher: Bencher) {
141+
bench_search_index(
142+
bencher,
143+
narrow_band_patches(true),
144+
queries_mixed_out_of_range(),
145+
);
146+
}
147+
148+
#[divan::bench]
149+
fn search_index_in_range(bencher: Bencher) {
150+
bench_search_index(bencher, narrow_band_patches(false), queries_in_range());
151+
}
152+
153+
#[divan::bench]
154+
fn search_index_in_range_chunked(bencher: Bencher) {
155+
bench_search_index(bencher, narrow_band_patches(true), queries_in_range());
156+
}
157+
158+
#[divan::bench]
159+
fn search_index_full_range_random(bencher: Bencher) {
160+
bench_search_index(bencher, full_range_patches(false), queries_full_range());
161+
}
162+
163+
#[divan::bench]
164+
fn search_index_full_range_random_chunked(bencher: Bencher) {
165+
bench_search_index(bencher, full_range_patches(true), queries_full_range());
166+
}

0 commit comments

Comments
 (0)