@@ -11,15 +11,13 @@ use crate::LEGACY_SESSION;
1111#[ expect( deprecated) ]
1212use crate :: ToCanonical as _;
1313use crate :: VortexSessionExecute ;
14- use crate :: aggregate_fn:: fns:: min_max:: min_max;
1514use crate :: arrays:: ConstantArray ;
1615use crate :: arrays:: ListViewArray ;
1716use crate :: arrays:: PrimitiveArray ;
1817use crate :: arrays:: listview:: ListViewArrayExt ;
1918use crate :: arrays:: primitive:: PrimitiveArrayExt ;
2019use crate :: builders:: builder_with_capacity;
2120use crate :: builtins:: ArrayBuiltins ;
22- use crate :: dtype:: DType ;
2321use crate :: dtype:: IntegerPType ;
2422use crate :: dtype:: Nullability ;
2523use crate :: dtype:: PType ;
@@ -54,6 +52,16 @@ fn rebuilt_offset_ptype(offsets_ptype: PType) -> PType {
5452/// list element dtypes.
5553pub const DEFAULT_REBUILD_DENSITY_THRESHOLD : f32 = 0.1 ;
5654
55+ /// Waste threshold to decide whether to trim a zero-copy-to-list `ListViewArray`.
56+ ///
57+ /// A zero-copy-to-list array has no overlaps and no interior gaps, so its only unreferenced bytes
58+ /// are leading and trailing elements. Trimming those is much cheaper than a full rebuild (a lazy
59+ /// `elements` slice plus an `O(num_lists)` offset adjustment, with no element data copy), so we use
60+ /// a more aggressive threshold than [`DEFAULT_REBUILD_DENSITY_THRESHOLD`].
61+ ///
62+ /// When the unreferenced (leading + trailing) fraction of `elements` exceeds this threshold, we trim.
63+ pub const DEFAULT_TRIM_ELEMENTS_THRESHOLD : f32 = 0.05 ;
64+
5765/// Modes for rebuilding a [`ListViewArray`].
5866pub enum ListViewRebuildMode {
5967 /// Removes all unused data and flattens out all list data, such that the array is zero-copyable
@@ -67,6 +75,9 @@ pub enum ListViewRebuildMode {
6775
6876 /// Removes any leading or trailing elements that are unused / not referenced by any views in
6977 /// the [`ListViewArray`].
78+ ///
79+ /// If the referenced `[start, end)` bounds are already known, prefer calling
80+ /// [`trim_elements`](ListViewArray::trim_elements) directly to avoid recomputing them.
7081 TrimElements ,
7182
7283 /// Equivalent to `MakeZeroCopyToList` plus `TrimElements`.
@@ -335,58 +346,24 @@ impl ListViewArray {
335346
336347 /// Rebuilds a [`ListViewArray`] by trimming any unused / unreferenced leading and trailing
337348 /// elements, which is defined as a contiguous run of values in the `elements` array that are
338- /// not referecened by any views in the corresponding [`ListViewArray`].
349+ /// not referenced by any views in the corresponding [`ListViewArray`].
339350 fn rebuild_trim_elements ( & self ) -> VortexResult < ListViewArray > {
340- let start = if self . is_zero_copy_to_list ( ) {
341- // If offsets are sorted, then the minimum offset is the first offset.
342- // Note that even if the first view is null, offsets must always be valid, so it is
343- // completely fine for us to use this as a lower-bounded start of the `elements`.
344- self . offset_at ( 0 )
345- } else {
346- let mut ctx = LEGACY_SESSION . create_execution_ctx ( ) ;
347- self . offsets ( )
348- . statistics ( )
349- . compute_min ( & mut ctx)
350- . vortex_expect (
351- "[ListViewArray::rebuild]: `offsets` must report min statistic that is a `usize`" ,
352- )
353- } ;
354-
355- let end = if self . is_zero_copy_to_list ( ) {
356- // If offsets are sorted and there are no overlaps (views are always "increasing"), we
357- // can just grab the last offset and last size.
358- let last_offset = self . offset_at ( self . len ( ) - 1 ) ;
359- let last_size = self . size_at ( self . len ( ) - 1 ) ;
360- last_offset + last_size
361- } else {
362- // Cast offsets and sizes to the widest integer type to prevent
363- // overflow when computing offsets + sizes. The end offset may not
364- // fit in the integer width otherwise.
365- let wide_dtype = DType :: from ( if self . offsets ( ) . dtype ( ) . as_ptype ( ) . is_unsigned_int ( ) {
366- PType :: U64
367- } else {
368- PType :: I64
369- } ) ;
370- let offsets = self . offsets ( ) . cast ( wide_dtype. clone ( ) ) ?;
371- let sizes = self . sizes ( ) . cast ( wide_dtype) ?;
372-
373- let mut ctx = LEGACY_SESSION . create_execution_ctx ( ) ;
374- let min_max = min_max (
375- & offsets
376- . binary ( sizes, Operator :: Add )
377- . vortex_expect ( "`offsets + sizes` somehow overflowed" ) ,
378- & mut ctx,
379- )
380- . vortex_expect ( "Something went wrong while computing min and max" )
381- . vortex_expect ( "We checked that the array was not empty in the top-level `rebuild`" ) ;
351+ let mut ctx = LEGACY_SESSION . create_execution_ctx ( ) ;
352+ let ( start, end) = self . referenced_element_bounds ( & mut ctx) ?;
382353
383- min_max
384- . max
385- . as_primitive ( )
386- . as_ :: < usize > ( )
387- . vortex_expect ( "unable to interpret the max `offset + size` as a `usize`" )
388- } ;
354+ // SAFETY: we calculated valid start and end bounds
355+ unsafe { self . trim_elements ( start, end) }
356+ }
389357
358+ /// Unsafely trims `elements` to the referenced half-open range `[start, end)`, adjusting every offset
359+ /// down by `start`. The result preserves the original `is_zero_copy_to_list` flag.
360+ ///
361+ /// # SAFETY
362+ ///
363+ /// `start` must be the minimum value of `offsets`, and end should be the maximum value of `offsets[i] + size[i]`
364+ /// over all indices `i` of offsets. Otherwise, `offsets` and `sizes` may hold references to elements that no longer exist
365+ /// and the array will be corrupted.
366+ pub unsafe fn trim_elements ( & self , start : usize , end : usize ) -> VortexResult < ListViewArray > {
390367 let adjusted_offsets = match_each_integer_ptype ! ( self . offsets( ) . dtype( ) . as_ptype( ) , |O | {
391368 let offset = <O as FromPrimitive >:: from_usize( start)
392369 . vortex_expect( "unable to convert the min offset `start` into a `usize`" ) ;
0 commit comments