|
| 1 | +// SPDX-License-Identifier: Apache-2.0 |
| 2 | +// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership |
| 3 | +// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements |
| 4 | + |
| 5 | +//! Definition / repetition level encoding in isolation, fed the way the column |
| 6 | +//! writer feeds it: one `put_with_observer` call per mini-batch, with an |
| 7 | +//! observer that counts values and updates a level histogram. |
| 8 | +
|
| 9 | +use std::hint::black_box; |
| 10 | + |
| 11 | +use criterion::{Criterion, Throughput, criterion_group, criterion_main}; |
| 12 | +use parquet::encodings::levels::LevelEncoder; |
| 13 | +use rand::prelude::*; |
| 14 | + |
| 15 | +const NUM_LEVELS: usize = 64 * 1024; |
| 16 | +const MINI_BATCH: usize = 1024; |
| 17 | + |
| 18 | +/// Levels for `List<T>` with nullable list and element: lists of `0..=max_len` |
| 19 | +/// elements, `null_pct` percent null lists and null elements. |
| 20 | +/// Returns `(def, rep)` with max def 3 and max rep 1. |
| 21 | +fn list_levels(rng: &mut StdRng, max_len: usize, null_pct: u32) -> (Vec<i16>, Vec<i16>) { |
| 22 | + let mut def = Vec::with_capacity(NUM_LEVELS); |
| 23 | + let mut rep = Vec::with_capacity(NUM_LEVELS); |
| 24 | + while def.len() < NUM_LEVELS { |
| 25 | + if rng.random_range(0..100) < null_pct { |
| 26 | + def.push(0); |
| 27 | + rep.push(0); |
| 28 | + continue; |
| 29 | + } |
| 30 | + let len = rng.random_range(0..=max_len); |
| 31 | + if len == 0 { |
| 32 | + def.push(1); |
| 33 | + rep.push(0); |
| 34 | + continue; |
| 35 | + } |
| 36 | + for i in 0..len { |
| 37 | + def.push(if rng.random_range(0..100) < null_pct { |
| 38 | + 2 |
| 39 | + } else { |
| 40 | + 3 |
| 41 | + }); |
| 42 | + rep.push((i != 0) as i16); |
| 43 | + } |
| 44 | + } |
| 45 | + def.truncate(NUM_LEVELS); |
| 46 | + rep.truncate(NUM_LEVELS); |
| 47 | + (def, rep) |
| 48 | +} |
| 49 | + |
| 50 | +/// Levels for `List<List<T>>`, all nullable: max def 5, max rep 2. |
| 51 | +fn nested_list_levels(rng: &mut StdRng) -> (Vec<i16>, Vec<i16>) { |
| 52 | + let mut def = Vec::with_capacity(NUM_LEVELS); |
| 53 | + let mut rep = Vec::with_capacity(NUM_LEVELS); |
| 54 | + while def.len() < NUM_LEVELS { |
| 55 | + let outer = rng.random_range(0..=4); |
| 56 | + if outer == 0 { |
| 57 | + def.push(rng.random_range(0..=1)); |
| 58 | + rep.push(0); |
| 59 | + continue; |
| 60 | + } |
| 61 | + for o in 0..outer { |
| 62 | + let first_rep = i16::from(o != 0); |
| 63 | + let inner = rng.random_range(0..=4); |
| 64 | + if inner == 0 { |
| 65 | + def.push(rng.random_range(2..=3)); |
| 66 | + rep.push(first_rep); |
| 67 | + continue; |
| 68 | + } |
| 69 | + for i in 0..inner { |
| 70 | + def.push(rng.random_range(4..=5)); |
| 71 | + rep.push(if i == 0 { first_rep } else { 2 }); |
| 72 | + } |
| 73 | + } |
| 74 | + } |
| 75 | + def.truncate(NUM_LEVELS); |
| 76 | + rep.truncate(NUM_LEVELS); |
| 77 | + (def, rep) |
| 78 | +} |
| 79 | + |
| 80 | +/// Runs of random length in `min_run..=max_run`, each a random level in `0..=max_level`. |
| 81 | +fn runs(rng: &mut StdRng, max_level: i16, min_run: usize, max_run: usize) -> Vec<i16> { |
| 82 | + let mut out = Vec::with_capacity(NUM_LEVELS); |
| 83 | + while out.len() < NUM_LEVELS { |
| 84 | + let v = rng.random_range(0..=max_level); |
| 85 | + let n = rng.random_range(min_run..=max_run); |
| 86 | + out.extend(std::iter::repeat_n(v, n)); |
| 87 | + } |
| 88 | + out.truncate(NUM_LEVELS); |
| 89 | + out |
| 90 | +} |
| 91 | + |
| 92 | +fn shapes() -> Vec<(String, i16, Vec<i16>)> { |
| 93 | + let mut rng = StdRng::seed_from_u64(42); |
| 94 | + let mut shapes = vec![]; |
| 95 | + for max_level in [1, 3, 7] { |
| 96 | + let levels = (0..NUM_LEVELS) |
| 97 | + .map(|_| rng.random_range(0..=max_level)) |
| 98 | + .collect(); |
| 99 | + shapes.push((format!("random/max{max_level}"), max_level, levels)); |
| 100 | + } |
| 101 | + shapes.push(( |
| 102 | + "alternating/max1".to_string(), |
| 103 | + 1, |
| 104 | + (0..NUM_LEVELS).map(|i| (i % 2) as i16).collect(), |
| 105 | + )); |
| 106 | + shapes.push(("mixed_runs/max3".to_string(), 3, runs(&mut rng, 3, 1, 40))); |
| 107 | + shapes.push(( |
| 108 | + "long_runs/max3".to_string(), |
| 109 | + 3, |
| 110 | + runs(&mut rng, 3, 1000, 5000), |
| 111 | + )); |
| 112 | + shapes.push(("uniform/max1".to_string(), 1, vec![1; NUM_LEVELS])); |
| 113 | + // 75% valid: mostly short runs of 1 with occasional nulls |
| 114 | + shapes.push(( |
| 115 | + "nullable_25pct/max1".to_string(), |
| 116 | + 1, |
| 117 | + (0..NUM_LEVELS) |
| 118 | + .map(|_| (rng.random_range(0..4) != 0) as i16) |
| 119 | + .collect(), |
| 120 | + )); |
| 121 | + shapes.push(( |
| 122 | + "sparse_99pct_null/max1".to_string(), |
| 123 | + 1, |
| 124 | + (0..NUM_LEVELS) |
| 125 | + .map(|_| (rng.random_range(0..100) == 0) as i16) |
| 126 | + .collect(), |
| 127 | + )); |
| 128 | + let (def, rep) = list_levels(&mut rng, 9, 10); |
| 129 | + shapes.push(("list_0_9/def_max3".to_string(), 3, def)); |
| 130 | + shapes.push(("list_0_9/rep_max1".to_string(), 1, rep)); |
| 131 | + let (def, rep) = list_levels(&mut rng, 4, 25); |
| 132 | + shapes.push(("list_0_4_25pct_null/def_max3".to_string(), 3, def)); |
| 133 | + shapes.push(("list_0_4_25pct_null/rep_max1".to_string(), 1, rep)); |
| 134 | + let (def, rep) = nested_list_levels(&mut rng); |
| 135 | + shapes.push(("list_list/def_max5".to_string(), 5, def)); |
| 136 | + shapes.push(("list_list/rep_max2".to_string(), 2, rep)); |
| 137 | + shapes |
| 138 | +} |
| 139 | + |
| 140 | +fn bench_levels(c: &mut Criterion) { |
| 141 | + let mut group = c.benchmark_group("level_encoding"); |
| 142 | + group.throughput(Throughput::Elements(NUM_LEVELS as u64)); |
| 143 | + for (name, max_level, levels) in shapes() { |
| 144 | + // What the column writer does per mini-batch: count values at max level |
| 145 | + // and update the page's level histogram |
| 146 | + group.bench_function(&name, |b| { |
| 147 | + let mut encoder = LevelEncoder::v2_streaming(max_level); |
| 148 | + let mut histogram = vec![0i64; max_level as usize + 1]; |
| 149 | + b.iter(|| { |
| 150 | + let mut at_max = 0usize; |
| 151 | + for chunk in black_box(levels.as_slice()).chunks(MINI_BATCH) { |
| 152 | + encoder.put_with_observer(chunk, |level, count| { |
| 153 | + at_max += count * (level == max_level) as usize; |
| 154 | + histogram[level as usize] += count as i64; |
| 155 | + }); |
| 156 | + } |
| 157 | + black_box(at_max); |
| 158 | + encoder.flush_to(|bytes| black_box(bytes.len())) |
| 159 | + }); |
| 160 | + black_box(&histogram); |
| 161 | + }); |
| 162 | + } |
| 163 | + group.finish(); |
| 164 | +} |
| 165 | + |
| 166 | +criterion_group!(benches, bench_levels); |
| 167 | +criterion_main!(benches); |
0 commit comments