This is an automated email from the ASF dual-hosted git repository.
Jefffrey 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 94464b4ba2 [Parquet] Alp criterion bench (#10662)
94464b4ba2 is described below
commit 94464b4ba285d8e6a0de46a7160784ddc3d357f6
Author: Kosta Tarasov <[email protected]>
AuthorDate: Fri Sep 4 21:25:57 2026 -0400
[Parquet] Alp criterion bench (#10662)
# Which issue does this PR close?
<!--
We generally require a GitHub issue to be filed for all bug fixes and
enhancements and this helps us generate change logs for our releases.
You can link an issue to this PR using the GitHub syntax.
-->
- Closes #10642 .
- stacks on #9372
# Rationale for this change
We need a benchmark to measure performance and prove future
optimizations
<!--
Why are you proposing this change? If this is already explained clearly
in the issue then this section is not needed.
Explaining clearly why changes are proposed helps reviewers understand
your changes and offer better suggestions for fixes.
-->
# What changes are included in this PR?
- Added a criterion benchmark
<!--
There is no need to duplicate the description in the issue here but it
is sometimes worth providing a summary of the individual changes in this
PR.
-->
# Are these changes tested?
- N/A
<!--
We typically require tests for all PRs in order to:
1. Prevent the code from being accidentally broken by subsequent changes
2. Serve as another way to document the expected behavior of the code
If tests are not included in your PR, please explain why (for example,
are they covered by existing tests)?
If this PR claims a performance improvement, please include evidence
such as benchmark results.
-->
# Are there any user-facing changes?
<!--
If there are user-facing changes then we may require documentation to be
updated before approving the PR.
If there are any breaking changes to public APIs, please call them out.
-->
---
parquet/Cargo.toml | 5 +
parquet/benches/alp.rs | 271 +++++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 276 insertions(+)
diff --git a/parquet/Cargo.toml b/parquet/Cargo.toml
index b6896459fd..600afa8d85 100644
--- a/parquet/Cargo.toml
+++ b/parquet/Cargo.toml
@@ -279,6 +279,11 @@ name = "encoding"
required-features = ["experimental", "default"]
harness = false
+[[bench]]
+name = "alp"
+required-features = ["experimental", "default"]
+harness = false
+
[[bench]]
name = "bit_packing"
required-features = ["experimental", "default"]
diff --git a/parquet/benches/alp.rs b/parquet/benches/alp.rs
new file mode 100644
index 0000000000..b83318f541
--- /dev/null
+++ b/parquet/benches/alp.rs
@@ -0,0 +1,271 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::{hint::black_box, sync::Arc};
+
+use criterion::{BatchSize, Criterion, Throughput, criterion_group,
criterion_main};
+use parquet::basic::Encoding;
+use parquet::data_type::{DataType, DoubleType, FloatType};
+use parquet::decoding::{Decoder, get_decoder};
+use parquet::encoding::{Encoder, get_encoder};
+use parquet::schema::types::{ColumnDescPtr, ColumnDescriptor, ColumnPath,
Type};
+
+/// 128 ALP vectors: 1 MiB of raw f64 values or 512 KiB of raw f32 values.
+const NUM_VALUES: usize = 128 * 1024;
+const RANDOM_ACCESS_ROWS: usize = 100;
+
+struct Fixture<F> {
+ name: &'static str,
+ values: Vec<F>,
+}
+
+fn column_descriptor<T: DataType>() -> ColumnDescPtr {
+ Arc::new(ColumnDescriptor::new(
+ Arc::new(
+ Type::primitive_type_builder("value", T::get_physical_type())
+ .build()
+ .unwrap(),
+ ),
+ 0,
+ 0,
+ ColumnPath::new(vec!["value".to_string()]),
+ ))
+}
+
+/// Decimal measurements with a wide range and a sparse high-precision reading.
+fn decimal_with_exceptions_f32() -> Vec<f32> {
+ (0..NUM_VALUES)
+ .map(|i| {
+ if i % 100 == 0 {
+ f32::from_bits(0x3f80_0000 | i as u32)
+ } else {
+ ((i * 17 % 200_000) as f32 - 100_000.0) / 100.0
+ }
+ })
+ .collect()
+}
+
+/// Decimal measurements with a wide range and a sparse high-precision reading.
+fn decimal_with_exceptions_f64() -> Vec<f64> {
+ (0..NUM_VALUES)
+ .map(|i| {
+ if i % 100 == 0 {
+ // A deterministic value that cannot normally use the decimal
ALP path.
+ f64::from_bits(0x3ff0_0000_0000_0000 | i as u64)
+ } else {
+ ((i * 17 % 200_000) as f64 - 100_000.0) / 100.0
+ }
+ })
+ .collect()
+}
+
+fn splitmix64(state: &mut u64) -> u64 {
+ *state = state.wrapping_add(0x9e37_79b9_7f4a_7c15);
+ let mut value = *state;
+ value = (value ^ (value >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
+ value = (value ^ (value >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
+ value ^ (value >> 31)
+}
+
+/// Uniform high-precision values generated by SplitMix64, without benchmark
setup RNG.
+fn high_precision_f32() -> Vec<f32> {
+ let mut state = 0x9e37_79b9_7f4a_7c15_u64;
+ (0..NUM_VALUES)
+ .map(|_| {
+ let value = splitmix64(&mut state);
+ (value >> 40) as f32 * (1.0 / (1_u32 << 24) as f32)
+ })
+ .collect()
+}
+
+/// Uniform high-precision values generated by SplitMix64, without benchmark
setup RNG.
+fn high_precision_f64() -> Vec<f64> {
+ let mut state = 0x9e37_79b9_7f4a_7c15_u64;
+ (0..NUM_VALUES)
+ .map(|_| {
+ let value = splitmix64(&mut state);
+ (value >> 11) as f64 * (1.0 / (1_u64 << 53) as f64)
+ })
+ .collect()
+}
+
+fn random_indices(len: usize) -> [usize; RANDOM_ACCESS_ROWS] {
+ let mut state = 0x4d59_5df4_d0f3_3173_u64;
+ std::array::from_fn(|_| ((splitmix64(&mut state) as u128 * len as u128) >>
64) as usize)
+}
+
+fn new_encoder<T: DataType>(descr: &ColumnDescPtr) -> Box<dyn Encoder<T>> {
+ get_encoder::<T>(Encoding::ALP, descr).unwrap()
+}
+
+fn encode<T: DataType>(encoder: &mut dyn Encoder<T>, values: &[T::T]) ->
bytes::Bytes {
+ encoder.put(values).unwrap();
+ encoder.flush_buffer().unwrap()
+}
+
+fn bench_fixture<T: DataType>(
+ c: &mut Criterion,
+ type_name: &str,
+ descr: &ColumnDescPtr,
+ fixture: &Fixture<T::T>,
+ bits_eq: fn(&T::T, &T::T) -> bool,
+) {
+ let benchmark_name = format!("{type_name}/{}", fixture.name);
+ let mut first_page = c.benchmark_group("alp/encode/first_page");
+ first_page.throughput(Throughput::Elements(fixture.values.len() as u64));
+ first_page.bench_function(&benchmark_name, |b| {
+ b.iter_batched(
+ || new_encoder::<T>(descr),
+ |mut encoder| {
+ let encoded = encode::<T>(encoder.as_mut(),
black_box(&fixture.values));
+ black_box(encoded)
+ },
+ BatchSize::SmallInput,
+ )
+ });
+ first_page.finish();
+
+ let mut encoder = new_encoder::<T>(descr);
+ let first_encoded = encode::<T>(encoder.as_mut(), &fixture.values);
+ let bits_per_value = first_encoded.len() as f64 * 8.0 /
fixture.values.len() as f64;
+ println!(
+ "{benchmark_name} encoded as {} bytes ({bits_per_value:.2}
bits/value)",
+ first_encoded.len()
+ );
+
+ let mut next_page = c.benchmark_group("alp/encode/next_page");
+ next_page.throughput(Throughput::Elements(fixture.values.len() as u64));
+ next_page.bench_function(&benchmark_name, |b| {
+ b.iter(|| {
+ let encoded = encode::<T>(encoder.as_mut(),
black_box(&fixture.values));
+ black_box(encoded)
+ })
+ });
+ next_page.finish();
+
+ let mut decoder: Box<dyn Decoder<T>> = get_decoder(descr.clone(),
Encoding::ALP).unwrap();
+ let mut decoded = vec![T::T::default(); fixture.values.len()];
+
+ decoder
+ .set_data(first_encoded.clone(), fixture.values.len())
+ .unwrap();
+ assert_eq!(decoder.get(&mut decoded).unwrap(), fixture.values.len());
+ assert!(
+ decoded
+ .iter()
+ .zip(&fixture.values)
+ .all(|(actual, expected)| bits_eq(actual, expected))
+ );
+
+ let mut decode = c.benchmark_group("alp/decode/page");
+ decode.throughput(Throughput::Elements(fixture.values.len() as u64));
+ decode.bench_function(&benchmark_name, |b| {
+ b.iter(|| {
+ decoder
+ .set_data(first_encoded.clone(), fixture.values.len())
+ .unwrap();
+ let read = decoder.get(&mut decoded).unwrap();
+ black_box((read, &decoded));
+ })
+ });
+ decode.finish();
+}
+
+fn bench_random_access<T: DataType>(
+ c: &mut Criterion,
+ type_name: &str,
+ descr: &ColumnDescPtr,
+ fixture: &Fixture<T::T>,
+ bits_eq: fn(&T::T, &T::T) -> bool,
+) {
+ let mut encoder = new_encoder::<T>(descr);
+ let encoded = encode::<T>(encoder.as_mut(), &fixture.values);
+ let indices = random_indices(fixture.values.len());
+ let mut decoder: Box<dyn Decoder<T>> = get_decoder(descr.clone(),
Encoding::ALP).unwrap();
+ let mut decoded = [T::T::default()];
+
+ for &index in &indices {
+ decoder
+ .set_data(encoded.clone(), fixture.values.len())
+ .unwrap();
+ assert_eq!(decoder.skip(index).unwrap(), index);
+ assert_eq!(decoder.get(&mut decoded).unwrap(), 1);
+ assert!(bits_eq(&decoded[0], &fixture.values[index]));
+ }
+
+ let mut random = c.benchmark_group("alp/decode/random_100");
+ random.throughput(Throughput::Elements(RANDOM_ACCESS_ROWS as u64));
+ random.bench_function(format!("{type_name}/{}", fixture.name), |b| {
+ b.iter(|| {
+ for &index in &indices {
+ decoder
+ .set_data(encoded.clone(), fixture.values.len())
+ .unwrap();
+ decoder.skip(index).unwrap();
+ decoder.get(&mut decoded).unwrap();
+ black_box(&decoded[0]);
+ }
+ })
+ });
+ random.finish();
+}
+
+fn bench_type<T: DataType>(
+ c: &mut Criterion,
+ type_name: &str,
+ fixtures: &[Fixture<T::T>],
+ bits_eq: fn(&T::T, &T::T) -> bool,
+) {
+ let descr = column_descriptor::<T>();
+ for fixture in fixtures {
+ bench_fixture::<T>(c, type_name, &descr, fixture, bits_eq);
+ bench_random_access::<T>(c, type_name, &descr, fixture, bits_eq);
+ }
+}
+
+fn criterion_benchmark(c: &mut Criterion) {
+ let f32_fixtures = [
+ Fixture {
+ name: "decimal_with_exceptions",
+ values: decimal_with_exceptions_f32(),
+ },
+ Fixture {
+ name: "high_precision",
+ values: high_precision_f32(),
+ },
+ ];
+ bench_type::<FloatType>(c, "f32", &f32_fixtures, |actual, expected| {
+ actual.to_bits() == expected.to_bits()
+ });
+
+ let f64_fixtures = [
+ Fixture {
+ name: "decimal_with_exceptions",
+ values: decimal_with_exceptions_f64(),
+ },
+ Fixture {
+ name: "high_precision",
+ values: high_precision_f64(),
+ },
+ ];
+ bench_type::<DoubleType>(c, "f64", &f64_fixtures, |actual, expected| {
+ actual.to_bits() == expected.to_bits()
+ });
+}
+
+criterion_group!(benches, criterion_benchmark);
+criterion_main!(benches);
