This is an automated email from the ASF dual-hosted git repository.
alamb pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/arrow-rs.git
The following commit(s) were added to refs/heads/main by this push:
new e91185abdc bench(arrow-select): filter_bits over batches of random and
clustered masks (#11271)
e91185abdc is described below
commit e91185abdc90a9a6c2e5a8b8f447dafda292d250
Author: mightsleep <[email protected]>
AuthorDate: Thu Oct 1 15:19:18 2026 +0200
bench(arrow-select): filter_bits over batches of random and clustered masks
(#11271)
# Which issue does this PR close?
- Part of #11213.
# Rationale for this change
The `filter_bits` cases repeat one 65536-row mask, 1024 words. A recent
core
learns the per-word branches of masks repeated from one iteration to the
next, so on random masks the cases measure a better branch predictor
than a
real filter gets. They also have no clustered masks, as from a sorted or
time-ordered column, where word-level code sees mostly full and empty
words.
As suggested in review, the new cases filter a stream of 8K-row batches,
each
with its own mask, which also counts the per-batch overhead. There are
512
of them because the predictor learns fewer: on Zen 5 at the default
target,
with 8K-row batches at kept 1/64 and the same total work, 16K words of
masks
repeated per iteration (128 batches) run at 0.005 mispredictions and 1.9
ns
per word, and 64K words (512 batches) at 0.74 mispredictions and 6.0 ns
per
word, which is what a query that never sees the same mask twice pays.
As discussed in #11213, the benchmarks go in first so that the
`compress`
change can be measured against them.
# What changes are included in this PR?
`filter_bits batches`, 512 batches of 8K rows with a mask each, lazy
strategies only (the path that compresses word by word):
- independent rows, kept 1/1024 to 15/16 (8 cases)
- runs averaging 64 and 512 rows, kept 1/8, 1/2, 7/8 (6 cases)
# Are these changes tested?
Benchmarks only. `cargo fmt` is clean.
# Are there any user-facing changes?
No.
---------
Co-authored-by: Andrew Lamb <[email protected]>
---
arrow-select/benches/filter_bits.rs | 82 ++++++++++++++++++++++++++++++++++++-
1 file changed, 81 insertions(+), 1 deletion(-)
diff --git a/arrow-select/benches/filter_bits.rs
b/arrow-select/benches/filter_bits.rs
index 90e70b1e7b..ccce30027c 100644
--- a/arrow-select/benches/filter_bits.rs
+++ b/arrow-select/benches/filter_bits.rs
@@ -39,6 +39,31 @@ fn create_boolean_array(size: usize, true_density: f64, rng:
&mut StdRng) -> Boo
.collect()
}
+/// A mask whose set bits come in runs averaging `run` bits, with the unset
+/// runs sized to give `true_density`: a clustered or sorted column under a
+/// range predicate, rather than independent rows
+fn create_clustered_array(
+ size: usize,
+ true_density: f64,
+ run: f64,
+ rng: &mut StdRng,
+) -> BooleanArray {
+ let leave_set = 1.0 / run;
+ let leave_unset = true_density / (run * (1.0 - true_density));
+ let mut set = rng.random_bool(true_density);
+ (0..size)
+ .map(|_| {
+ let bit = set;
+ set = if set {
+ !rng.random_bool(leave_set)
+ } else {
+ rng.random_bool(leave_unset)
+ };
+ Some(bit)
+ })
+ .collect()
+}
+
fn bench_filter_bits(predicate: &FilterPredicate, array: &BooleanArray) {
hint::black_box(predicate.filter(array).unwrap());
}
@@ -86,5 +111,60 @@ fn add_benchmark(c: &mut Criterion) {
}
}
-criterion_group!(benches, add_benchmark);
+/// `filter_bits` over 512 batches of 8K rows, each with its own mask, as a
+/// query filters a stream of record batches. A recent core learns the
+/// per-word branches of masks repeated from one iteration to the next, up to
+/// at least 16K words, which makes random masks look faster than a real
+/// filter; 512 batches are 64K words, past that. Lazy strategies only, which
+/// compress word by word
+fn add_batched_benchmark(c: &mut Criterion) {
+ const BATCHES: usize = 512;
+ const ROWS: usize = 8192;
+ let mut rng = StdRng::seed_from_u64(43);
+
+ let data: Vec<BooleanArray> = (0..BATCHES)
+ .map(|_| create_boolean_array(ROWS, 0.5, &mut rng))
+ .collect();
+
+ let mut cases = vec![];
+ for (label, true_density) in [
+ ("1/1024", 1.0 / 1024.0),
+ ("1/256", 1.0 / 256.0),
+ ("1/64", 1.0 / 64.0),
+ ("1/16", 1.0 / 16.0),
+ ("1/4", 0.25),
+ ("1/2", 0.5),
+ ("3/4", 0.75),
+ ("15/16", 15.0 / 16.0),
+ ] {
+ let masks: Vec<_> = (0..BATCHES)
+ .map(|_| create_boolean_array(ROWS, true_density, &mut rng))
+ .collect();
+ cases.push((format!("random, kept {label}"), masks));
+ }
+ for run in [64, 512] {
+ for (label, true_density) in [("1/8", 0.125), ("1/2", 0.5), ("7/8",
0.875)] {
+ let masks: Vec<_> = (0..BATCHES)
+ .map(|_| create_clustered_array(ROWS, true_density, run as
f64, &mut rng))
+ .collect();
+ cases.push((format!("runs of {run}, kept {label}"), masks));
+ }
+ }
+
+ for (label, masks) in &cases {
+ let predicates: Vec<_> = masks
+ .iter()
+ .map(|m| FilterBuilder::new(m).build())
+ .collect();
+ c.bench_function(&format!("filter_bits batches ({label})"), |b| {
+ b.iter(|| {
+ for (predicate, array) in predicates.iter().zip(&data) {
+ bench_filter_bits(predicate, array);
+ }
+ })
+ });
+ }
+}
+
+criterion_group!(benches, add_benchmark, add_batched_benchmark);
criterion_main!(benches);
