Skip to content

Commit 0f3b5a0

Browse files
alambandygrove
andauthored
[branch-56] fix: count the largest capacity seen for a shared buffer address (backport #27097) (#27175)
## Which issue does this PR close? - Backport of #27097 to `branch-56` - Part of #24461 - Closes #27069 Co-authored-by: Andy Grove <[email protected]>
1 parent b4b4edd commit 0f3b5a0

2 files changed

Lines changed: 230 additions & 66 deletions

File tree

‎datafusion/common/src/utils/memory.rs‎

Lines changed: 170 additions & 62 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,7 @@
55
//! This module provides a function to estimate the memory size of a HashTable prior to allocation
66
77
use crate::error::_exec_datafusion_err;
8+
use crate::hash_map::Entry;
89
use crate::{HashMap, HashSet, Result};
910
use arrow::array::types::{
1011
ByteArrayType, ByteViewType, Int8Type, Int16Type, Int32Type, Int64Type,
@@ -226,9 +227,9 @@ impl RecordBatchMemoryCounter {
226227

227228
impl BufferVisitor for RecordBatchMemoryCounter {
228229
fn visit(&mut self, buffer: &Buffer) {
229-
if self.counted_buffers.insert(buffer.data_ptr().addr()) {
230-
self.memory_usage += buffer.capacity();
231-
}
230+
self.memory_usage += self
231+
.counted_buffers
232+
.insert(buffer.data_ptr().addr(), buffer.capacity());
232233
}
233234
}
234235

@@ -237,8 +238,8 @@ impl BufferVisitor for RecordBatchMemoryCounter {
237238
/// Operators that retain batches incrementally and drop them later (sort,
238239
/// window, sort-merge join, TopK) count a batch when they retain it and
239240
/// [`Self::uncount_batch`] it when they drop it. The tracker keeps a reference
240-
/// count per buffer: a buffer's capacity is added when its count goes from 0
241-
/// to 1 and subtracted when it returns to 0.
241+
/// count per buffer: it is charged the largest capacity seen while its count
242+
/// is positive, and released when its count returns to 0.
242243
///
243244
/// **Contract**: a batch must be uncounted *before* its buffers are dropped.
244245
/// The tracker identifies buffers by their data-pointer address and does not
@@ -373,9 +374,9 @@ impl RecordBatchMemoryTracker {
373374
/// Counting visitor: retains each buffer once more.
374375
impl BufferVisitor for RecordBatchMemoryTracker {
375376
fn visit(&mut self, buffer: &Buffer) {
376-
if self.counted_buffers.increment(buffer.data_ptr().addr()) {
377-
self.memory_usage += buffer.capacity();
378-
}
377+
self.memory_usage += self
378+
.counted_buffers
379+
.increment(buffer.data_ptr().addr(), buffer.capacity());
379380
}
380381
}
381382

@@ -384,9 +385,7 @@ struct Uncount<'a>(&'a mut RecordBatchMemoryTracker);
384385

385386
impl BufferVisitor for Uncount<'_> {
386387
fn visit(&mut self, buffer: &Buffer) {
387-
if self.0.counted_buffers.decrement(buffer.data_ptr().addr()) {
388-
self.0.memory_usage -= buffer.capacity();
389-
}
388+
self.0.memory_usage -= self.0.counted_buffers.decrement(buffer.data_ptr().addr());
390389
}
391390
}
392391

@@ -604,137 +603,157 @@ fn array_children(array: &ArrayRef) -> Vec<&ArrayRef> {
604603
}
605604

606605
/// Tracks a small number of buffers inline, avoiding a heap allocation for
607-
/// typical batches, and promotes to a hash set when more buffers are seen.
606+
/// typical batches, and promotes to a hash map when more buffers are seen.
607+
///
608+
/// Keeps the largest capacity seen per address: buffers built with
609+
/// `Buffer::from_custom_allocation`, such as FFI imports, can share an address
610+
/// while reporting different capacities.
608611
#[derive(Debug)]
609612
struct BufferIdSet {
610613
inline: [Option<NonZero<usize>>; INLINE_BUFFER_IDS],
614+
/// Counted capacity of each inline buffer, parallel to `inline`.
615+
capacities: [usize; INLINE_BUFFER_IDS],
611616
len: usize,
612-
overflow: Option<HashSet<NonZero<usize>>>,
617+
overflow: Option<HashMap<NonZero<usize>, usize>>,
613618
}
614619

615620
impl Default for BufferIdSet {
616621
fn default() -> Self {
617622
Self {
618623
inline: [None; INLINE_BUFFER_IDS],
624+
capacities: [0; INLINE_BUFFER_IDS],
619625
len: 0,
620626
overflow: None,
621627
}
622628
}
623629
}
624630

625631
impl BufferIdSet {
626-
fn insert(&mut self, buffer_id: NonZero<usize>) -> bool {
632+
/// Returns the bytes of `capacity` not already counted for `buffer_id`.
633+
fn insert(&mut self, buffer_id: NonZero<usize>, capacity: usize) -> usize {
627634
if let Some(overflow) = &mut self.overflow {
628-
return overflow.insert(buffer_id);
635+
let counted = overflow.entry(buffer_id).or_insert(0);
636+
return grow_counted_capacity(counted, capacity);
629637
}
630638

631-
if self.inline[..self.len].contains(&Some(buffer_id)) {
632-
return false;
639+
for i in 0..self.len {
640+
if self.inline[i] == Some(buffer_id) {
641+
return grow_counted_capacity(&mut self.capacities[i], capacity);
642+
}
633643
}
634644

635645
if self.len < INLINE_BUFFER_IDS {
636646
self.inline[self.len] = Some(buffer_id);
647+
self.capacities[self.len] = capacity;
637648
self.len += 1;
638-
return true;
649+
return capacity;
639650
}
640651

641-
let mut overflow = HashSet::with_capacity(INLINE_BUFFER_IDS + 1);
642-
overflow.extend(self.inline.iter().flatten().copied());
643-
let inserted = overflow.insert(buffer_id);
652+
let mut overflow = HashMap::with_capacity(INLINE_BUFFER_IDS + 1);
653+
overflow.extend(self.inline.iter().flatten().copied().zip(self.capacities));
654+
overflow.insert(buffer_id, capacity);
644655
self.overflow = Some(overflow);
645-
inserted
656+
capacity
646657
}
647658
}
648659

660+
/// Raises `counted` to `capacity` if that is larger, returning the growth.
661+
#[inline(always)]
662+
fn grow_counted_capacity(counted: &mut usize, capacity: usize) -> usize {
663+
let growth = capacity.saturating_sub(*counted);
664+
*counted += growth;
665+
growth
666+
}
667+
649668
/// Reference-counted buffer tracker with an inline fast path.
650669
///
651-
/// Tracks buffer addresses with their reference counts. The first
652-
/// [`INLINE_BUFFER_IDS`] distinct buffers are stored in a fixed-size inline
653-
/// array to avoid heap allocation for typical batches. When more buffers are
654-
/// encountered, the tracker promotes to a heap-allocated `HashMap`.
670+
/// Tracks buffer addresses with their reference counts and counted capacities
671+
/// (the largest seen, as in [`BufferIdSet`]). The first [`INLINE_BUFFER_IDS`]
672+
/// distinct buffers are stored in fixed-size inline arrays to avoid heap
673+
/// allocation for typical batches. When more buffers are encountered, the
674+
/// tracker promotes to a heap-allocated `HashMap`.
655675
///
656-
/// The inline path stores addresses and counts in **separate** arrays so that
657-
/// the hot `position()` scan over addresses touches a contiguous
676+
/// The inline path stores addresses, counts and capacities in **separate**
677+
/// arrays so that the hot scan over addresses touches a contiguous
658678
/// `[Option<NonZero<usize>>; 16]` (128 bytes, two cache lines) without
659-
/// interleaved count words, matching the layout of the previous insert-only
660-
/// `BufferIdSet`.
679+
/// interleaved count words.
661680
#[derive(Debug)]
662681
struct BufferIdMap {
663682
/// Inline storage: buffer addresses (None = empty slot).
664683
ids: [Option<NonZero<usize>>; INLINE_BUFFER_IDS],
665684
/// Inline storage: per-slot reference counts, parallel to `ids`.
666685
counts: [u32; INLINE_BUFFER_IDS],
686+
/// Inline storage: per-slot counted capacities, parallel to `ids`.
687+
capacities: [usize; INLINE_BUFFER_IDS],
667688
/// Number of occupied inline slots.
668689
len: usize,
669690
/// Overflow storage used when more than `INLINE_BUFFER_IDS` distinct
670-
/// buffers are tracked.
671-
overflow: Option<HashMap<NonZero<usize>, u32>>,
691+
/// buffers are tracked: (reference count, counted capacity).
692+
overflow: Option<HashMap<NonZero<usize>, (u32, usize)>>,
672693
}
673694

674695
impl Default for BufferIdMap {
675696
fn default() -> Self {
676697
Self {
677698
ids: [None; INLINE_BUFFER_IDS],
678699
counts: [0; INLINE_BUFFER_IDS],
700+
capacities: [0; INLINE_BUFFER_IDS],
679701
len: 0,
680702
overflow: None,
681703
}
682704
}
683705
}
684706

685707
impl BufferIdMap {
686-
/// Increment the reference count for `buffer_id`. Returns `true` when the
687-
/// count went from 0 to 1 (i.e., the buffer is newly tracked).
708+
/// Increment the reference count for `buffer_id`, returning the bytes of
709+
/// `capacity` not already counted for it.
688710
#[inline(always)]
689-
fn increment(&mut self, buffer_id: NonZero<usize>) -> bool {
711+
fn increment(&mut self, buffer_id: NonZero<usize>, capacity: usize) -> usize {
690712
if let Some(overflow) = &mut self.overflow {
691-
let count = overflow.entry(buffer_id).or_insert(0);
713+
let (count, counted) = overflow.entry(buffer_id).or_insert((0, 0));
692714
*count += 1;
693-
return *count == 1;
715+
return grow_counted_capacity(counted, capacity);
694716
}
695717

696718
// Search inline slots.
697-
if let Some(i) = self.ids[..self.len]
698-
.iter()
699-
.position(|id| *id == Some(buffer_id))
700-
{
701-
self.counts[i] += 1;
702-
return false; // Already tracked, count > 1 now.
719+
for i in 0..self.len {
720+
if self.ids[i] == Some(buffer_id) {
721+
self.counts[i] += 1;
722+
return grow_counted_capacity(&mut self.capacities[i], capacity);
723+
}
703724
}
704725

705726
// New buffer: try inline first.
706727
if self.len < INLINE_BUFFER_IDS {
707728
self.ids[self.len] = Some(buffer_id);
708729
self.counts[self.len] = 1;
730+
self.capacities[self.len] = capacity;
709731
self.len += 1;
710-
return true;
732+
return capacity;
711733
}
712734

713735
// Promote to overflow.
714736
let mut overflow = HashMap::with_capacity(INLINE_BUFFER_IDS + 1);
715737
for i in 0..self.len {
716738
if let Some(id) = self.ids[i] {
717-
overflow.insert(id, self.counts[i]);
739+
overflow.insert(id, (self.counts[i], self.capacities[i]));
718740
}
719741
}
720-
overflow.insert(buffer_id, 1);
742+
overflow.insert(buffer_id, (1, capacity));
721743
self.overflow = Some(overflow);
722-
true
744+
capacity
723745
}
724746

725-
/// Decrement the reference count for `buffer_id`. Returns `true` when the
726-
/// count reached zero (i.e., the buffer is no longer tracked). Returns
727-
/// `false` if the buffer was not tracked or its count is still positive.
728-
fn decrement(&mut self, buffer_id: NonZero<usize>) -> bool {
747+
/// Decrement the reference count for `buffer_id`, returning its counted
748+
/// capacity when the count reaches zero and 0 otherwise.
749+
fn decrement(&mut self, buffer_id: NonZero<usize>) -> usize {
729750
if let Some(overflow) = &mut self.overflow {
730-
if let Some(count) = overflow.get_mut(&buffer_id) {
731-
*count -= 1;
732-
if *count == 0 {
733-
overflow.remove(&buffer_id);
734-
return true;
735-
}
736-
}
737-
return false;
751+
let Entry::Occupied(mut entry) = overflow.entry(buffer_id) else {
752+
return 0;
753+
};
754+
let (count, _) = entry.get_mut();
755+
*count -= 1;
756+
return if *count == 0 { entry.remove().1 } else { 0 };
738757
}
739758

740759
// Search inline slots.
@@ -743,20 +762,22 @@ impl BufferIdMap {
743762
if self.ids[i] == target {
744763
self.counts[i] -= 1;
745764
if self.counts[i] == 0 {
765+
let counted = self.capacities[i];
746766
// Swap-remove: move last entry here.
747767
self.len -= 1;
748768
if i < self.len {
749769
self.ids[i] = self.ids[self.len];
750770
self.counts[i] = self.counts[self.len];
771+
self.capacities[i] = self.capacities[self.len];
751772
}
752773
self.ids[self.len] = None;
753-
return true;
774+
return counted;
754775
}
755-
return false;
776+
return 0;
756777
}
757778
}
758779

759-
false
780+
0
760781
}
761782
}
762783

@@ -1229,6 +1250,93 @@ mod record_batch_tests {
12291250
assert_eq!(counter.count_batch(&batch), 0);
12301251
}
12311252

1253+
/// Arrays over one allocation with different capacities, as
1254+
/// `arrow::ffi::from_ffi` imports slices of one batch.
1255+
fn custom_allocation_arrays(lens: &[usize]) -> Vec<ArrayRef> {
1256+
use arrow::buffer::ScalarBuffer;
1257+
use std::ptr::NonNull;
1258+
1259+
let max_len = lens.iter().copied().max().unwrap_or(0);
1260+
let owner: Arc<Vec<i32>> = Arc::new((0..max_len as i32).collect());
1261+
let ptr = NonNull::new(owner.as_ptr().cast::<u8>().cast_mut()).unwrap();
1262+
lens.iter()
1263+
.map(|&len| {
1264+
// SAFETY: `owner` holds `len` values at `ptr`; the buffer keeps it alive.
1265+
let buffer = unsafe {
1266+
Buffer::from_custom_allocation(
1267+
ptr,
1268+
len * size_of::<i32>(),
1269+
Arc::clone(&owner) as _,
1270+
)
1271+
};
1272+
Arc::new(Int32Array::new(ScalarBuffer::new(buffer, 0, len), None))
1273+
as ArrayRef
1274+
})
1275+
.collect()
1276+
}
1277+
1278+
/// Arrays that fill the inline slots, so the next buffer promotes to overflow.
1279+
fn inline_filler_arrays() -> Vec<ArrayRef> {
1280+
(0..INLINE_BUFFER_IDS)
1281+
.map(|i| Arc::new(Int32Array::from(vec![i as i32])) as ArrayRef)
1282+
.collect()
1283+
}
1284+
1285+
#[test]
1286+
fn test_record_batch_memory_counter_counts_largest_capacity_at_address() {
1287+
let (small, large) = (16 * size_of::<i32>(), 1024 * size_of::<i32>());
1288+
for promote in [false, true] {
1289+
for (lens, expected) in [
1290+
([16, 1024], (small, large - small)),
1291+
([1024, 16], (large, 0)),
1292+
] {
1293+
let arrays = custom_allocation_arrays(&lens);
1294+
let mut counter = RecordBatchMemoryCounter::new();
1295+
if promote {
1296+
for array in inline_filler_arrays() {
1297+
counter.count_array(array.as_ref());
1298+
}
1299+
}
1300+
let base = counter.memory_usage();
1301+
1302+
let first = counter.count_array(arrays[0].as_ref());
1303+
let second = counter.count_array(arrays[1].as_ref());
1304+
assert_eq!((first, second), expected);
1305+
assert_eq!(counter.memory_usage() - base, large);
1306+
assert_eq!(counter.counted_buffers.overflow.is_some(), promote);
1307+
}
1308+
}
1309+
}
1310+
1311+
#[test]
1312+
fn test_uncount_releases_largest_capacity_at_address() {
1313+
let (small, large) = (16 * size_of::<i32>(), 1024 * size_of::<i32>());
1314+
for promote in [false, true] {
1315+
let arrays = custom_allocation_arrays(&[16, 1024]);
1316+
let mut tracker = RecordBatchMemoryTracker::new();
1317+
let fillers = inline_filler_arrays();
1318+
if promote {
1319+
for array in &fillers {
1320+
tracker.count_array(array.as_ref());
1321+
}
1322+
}
1323+
let base = tracker.memory_usage();
1324+
1325+
assert_eq!(tracker.count_array(arrays[0].as_ref()), small);
1326+
assert_eq!(tracker.count_array(arrays[1].as_ref()), large - small);
1327+
assert_eq!(tracker.counted_buffers.overflow.is_some(), promote);
1328+
// Released at its largest capacity once the last array goes.
1329+
assert_eq!(tracker.uncount_array(arrays[0].as_ref()), 0);
1330+
assert_eq!(tracker.uncount_array(arrays[1].as_ref()), large);
1331+
assert_eq!(tracker.memory_usage(), base);
1332+
1333+
for array in &fillers {
1334+
tracker.uncount_array(array.as_ref());
1335+
}
1336+
assert_eq!(tracker.memory_usage(), 0);
1337+
}
1338+
}
1339+
12321340
#[test]
12331341
fn test_array_memory_size_matches_array_data_layouts() {
12341342
let list_field = Arc::new(Field::new_list_field(DataType::Int32, true));

0 commit comments

Comments
 (0)