Skip to content

Commit c1f0d54

Browse files
perf: avoid unnecessary large allocations (apache#22558)
## Which issue does this PR close? Related a bit to apache#22526 ~Needs rebasing once apache#22416 is merged~ ## Rationale for this change split_off does this: > Returns a newly allocated vector containing the elements in the range [at, len). After the call, the original vector will be left containing the elements [0, at) with its previous capacity unchanged. which is bad when taking a small slice from a large Vec, for two reasons: * it will allocate memory for the remaining elements, which are a lot more than n * it will return a Vec with a very large capacity compared to its length split_vec_min_alloc still has some issues: apache#22548 but it uses drain + collect when n is small, which is better because it only allocates for the initial n elements and doesn't inflate the capacity ## What changes are included in this PR? ## Are these changes tested? Yes ## Are there any user-facing changes? No
1 parent 7b78f0c commit c1f0d54

2 files changed

Lines changed: 102 additions & 11 deletions

File tree

‎datafusion/expr-common/src/groups_accumulator.rs‎

Lines changed: 52 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -18,7 +18,7 @@
1818
//! Vectorized [`GroupsAccumulator`]
1919
2020
use arrow::array::{ArrayRef, BooleanArray};
21-
use datafusion_common::{Result, not_impl_err};
21+
use datafusion_common::{Result, not_impl_err, utils::split_vec_min_alloc};
2222

2323
/// Describes how many rows should be emitted during grouping.
2424
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
@@ -45,13 +45,7 @@ impl EmitTo {
4545
// Take the entire vector, leave new (empty) vector
4646
std::mem::take(v)
4747
}
48-
Self::First(n) => {
49-
// get end n+1,.. values into t
50-
let mut t = v.split_off(*n);
51-
// leave n+1,.. in v
52-
std::mem::swap(v, &mut t);
53-
t
54-
}
48+
Self::First(n) => split_vec_min_alloc(v, *n),
5549
}
5650
}
5751
}
@@ -254,3 +248,53 @@ pub trait GroupsAccumulator: Send + std::any::Any {
254248
/// compute, not `O(num_groups)`
255249
fn size(&self) -> usize;
256250
}
251+
252+
#[cfg(test)]
253+
mod tests {
254+
use super::EmitTo;
255+
256+
/// When `n` is small relative to `len`, the old `split_off(n) + swap` pattern had
257+
/// two allocation problems:
258+
///
259+
/// 1. The returned Vec kept the original large backing allocation even though it
260+
/// only contains `n` elements (wasted capacity on a short-lived value).
261+
/// 2. `split_off` allocated a fresh Vec for the `len - n` remaining elements,
262+
/// even though that side is much larger than `n` — the expensive side to
263+
/// allocate.
264+
///
265+
/// `split_vec_min_alloc` fixes both: when `n * 2 <= len` it uses
266+
/// `drain(0..n).collect()`, allocating only `n` elements for the emitted prefix
267+
/// and keeping the original large backing in the remaining accumulator.
268+
#[test]
269+
fn take_needed_first_small_n_allocates_minimally() {
270+
let mut v: Vec<i32> = Vec::with_capacity(128);
271+
v.extend(0..20i32);
272+
let original_capacity = v.capacity(); // 128
273+
274+
// n=4, n*2=8 <= len=20 -> drain branch in split_vec_min_alloc
275+
let emitted = EmitTo::First(4).take_needed(&mut v);
276+
277+
assert_eq!(emitted, vec![0, 1, 2, 3]);
278+
assert_eq!(v, (4..20i32).collect::<Vec<_>>());
279+
280+
// The emitted prefix must NOT carry the original large allocation.
281+
// Old split_off+swap returned a Vec with capacity=128 for only 4 elements.
282+
assert!(
283+
emitted.capacity() <= 4,
284+
"emitted prefix capacity {} should be ~n=4, not the original {}",
285+
emitted.capacity(),
286+
original_capacity,
287+
);
288+
289+
// The remaining accumulator must retain the original large allocation so
290+
// that incoming groups don't immediately force a realloc.
291+
// Old split_off+swap left the remaining vec with a small fresh allocation.
292+
assert_eq!(
293+
v.capacity(),
294+
original_capacity,
295+
"remaining vec capacity {} should equal original {}",
296+
v.capacity(),
297+
original_capacity,
298+
);
299+
}
300+
}

‎datafusion/physical-plan/src/aggregates/group_values/single_group_by/primitive.rs‎

Lines changed: 50 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -24,6 +24,7 @@ use arrow::array::{
2424
use arrow::datatypes::{DataType, i256};
2525
use datafusion_common::Result;
2626
use datafusion_common::hash_utils::RandomState;
27+
use datafusion_common::utils::split_vec_min_alloc;
2728
use datafusion_execution::memory_pool::proxy::VecAllocExt;
2829
use datafusion_expr::EmitTo;
2930
use half::f16;
@@ -207,9 +208,7 @@ where
207208
Some(_) => self.null_group.take(),
208209
None => None,
209210
};
210-
let mut split = self.values.split_off(n);
211-
std::mem::swap(&mut self.values, &mut split);
212-
build_primitive(split, null_group)
211+
build_primitive(split_vec_min_alloc(&mut self.values, n), null_group)
213212
}
214213
};
215214

@@ -223,3 +222,51 @@ where
223222
self.map.shrink_to(num_rows, |_| 0); // hasher does not matter since the map is cleared
224223
}
225224
}
225+
226+
#[cfg(test)]
227+
mod tests {
228+
use super::*;
229+
use arrow::array::types::Int32Type;
230+
use arrow::array::{ArrayRef, Int32Array};
231+
use arrow::datatypes::DataType;
232+
use datafusion_expr::EmitTo;
233+
use std::sync::Arc;
234+
235+
/// Mirror of the `EmitTo::take_needed` regression test, applied to the
236+
/// concrete `GroupValuesPrimitive` accumulator.
237+
///
238+
/// When `n` is small, the old `split_off(n) + swap` pattern used inside
239+
/// `emit(EmitTo::First(n))` left `self.values` with a small fresh allocation
240+
/// and returned the emitted prefix carrying the original large backing.
241+
///
242+
/// With `split_vec_min_alloc` and `n * 2 <= len`, the drain branch is taken:
243+
/// the emitted prefix gets a compact allocation and `self.values` retains the
244+
/// original large one.
245+
#[test]
246+
fn emit_first_small_n_allocates_minimally() -> Result<()> {
247+
let mut gv = GroupValuesPrimitive::<Int32Type>::new(DataType::Int32);
248+
249+
// Intern 20 distinct values; `new()` pre-allocates capacity 128 for `values`.
250+
let arr: ArrayRef = Arc::new(Int32Array::from_iter_values(0..20i32));
251+
let mut groups = vec![];
252+
gv.intern(&[arr], &mut groups)?;
253+
let capacity_before = gv.values.capacity(); // 128
254+
255+
// n=4, n*2=8 <= len=20 -> drain branch
256+
let emitted = gv.emit(EmitTo::First(4))?;
257+
258+
assert_eq!(emitted[0].len(), 4);
259+
260+
// `self.values` must retain its original large allocation.
261+
// Old split_off+swap left it with a fresh small allocation (~16).
262+
assert_eq!(
263+
gv.values.capacity(),
264+
capacity_before,
265+
"self.values capacity {} should equal original {} after small First(n) emit",
266+
gv.values.capacity(),
267+
capacity_before,
268+
);
269+
270+
Ok(())
271+
}
272+
}

0 commit comments

Comments
 (0)