55//! This module provides a function to estimate the memory size of a HashTable prior to allocation
66
77use crate :: error:: _exec_datafusion_err;
8+ use crate :: hash_map:: Entry ;
89use crate :: { HashMap , HashSet , Result } ;
910use arrow:: array:: types:: {
1011 ByteArrayType , ByteViewType , Int8Type , Int16Type , Int32Type , Int64Type ,
@@ -226,9 +227,9 @@ impl RecordBatchMemoryCounter {
226227
227228impl 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.
374375impl 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
385386impl 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 ) ]
609612struct 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
615620impl 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
625631impl 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 ) ]
662681struct 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
674695impl 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
685707impl 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