Skip to content

Commit 692502f

Browse files
committed
walk the null runs once, skip the filter when no elements are kept
Signed-off-by: Matt Katz <[email protected]>
1 parent 98d8115 commit 692502f

1 file changed

Lines changed: 27 additions & 21 deletions

File tree

‎vortex-array/src/arrays/list/rebuild.rs‎

Lines changed: 27 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -97,7 +97,12 @@ pub(crate) fn null_runs_holding_elements(
9797
/// Drops the elements before the first of the lists laid out back to back, after the last, and
9898
/// under the runs of null lists from [`null_runs_holding_elements`], which come out empty.
9999
///
100-
/// Returns the elements kept and where each list now starts, with room to push one more offset.
100+
/// `end` is where the last list ends. It is a `usize` rather than an `O` because a list view's last
101+
/// list can end past what its offsets' type holds: with `u8` offsets `[1, 5, 105]` and sizes
102+
/// `[4, 100, 200]`, it ends at 305.
103+
///
104+
/// Returns the elements kept and where each list now starts. A [`ListArray`] needs one more offset,
105+
/// where its last list ends, so the buffer has room to push it without reallocating.
101106
pub(crate) fn drop_unreferenced_elements<O: IntegerPType>(
102107
elements: &ArrayRef,
103108
starts: &[O],
@@ -110,32 +115,16 @@ pub(crate) fn drop_unreferenced_elements<O: IntegerPType>(
110115
// The ranges of elements kept, counted from the first list's start.
111116
let mut kept = Vec::with_capacity(null_runs.len() + 1);
112117
let mut kept_start = 0;
118+
let mut offsets = BufferMut::with_capacity_in(starts.len() + 1, allocator.clone());
119+
offsets.extend_from_slice(starts);
120+
let mut dropped = starts.first().copied().unwrap_or_else(O::zero);
121+
let mut from = 0;
113122
for &(run_start, run_end) in null_runs {
114123
if kept_start < start_of(run_start) - first {
115124
kept.push((kept_start, start_of(run_start) - first));
116125
}
117126
kept_start = start_of(run_end) - first;
118-
}
119-
if kept_start < end - first {
120-
kept.push((kept_start, end - first));
121-
}
122-
let referenced = elements.slice(first..end)?;
123-
let elements = if let [(start, stop)] = kept[..] {
124-
referenced.slice(start..stop)?
125-
} else {
126-
let mut bits = BitBufferMut::new_unset(end - first);
127-
for &(start, stop) in &kept {
128-
bits.fill_range(start, stop, true);
129-
}
130-
// With the ranges cached on the mask, the filter copies the elements range by range.
131-
referenced.filter(Mask::from_buffer_with_slices(bits.freeze(), kept))?
132-
};
133127

134-
let mut offsets = BufferMut::with_capacity_in(starts.len() + 1, allocator.clone());
135-
offsets.extend_from_slice(starts);
136-
let mut dropped = starts.first().copied().unwrap_or_else(O::zero);
137-
let mut from = 0;
138-
for &(run_start, run_end) in null_runs {
139128
for offset in &mut offsets[from..run_start] {
140129
*offset = *offset - dropped;
141130
}
@@ -146,8 +135,25 @@ pub(crate) fn drop_unreferenced_elements<O: IntegerPType>(
146135
}
147136
from = run_end;
148137
}
138+
if kept_start < end - first {
139+
kept.push((kept_start, end - first));
140+
}
149141
for offset in &mut offsets[from..] {
150142
*offset = *offset - dropped;
151143
}
144+
145+
let referenced = elements.slice(first..end)?;
146+
let elements = match kept[..] {
147+
[] => referenced.slice(0..0)?,
148+
[(start, stop)] => referenced.slice(start..stop)?,
149+
_ => {
150+
let mut bits = BitBufferMut::new_unset(end - first);
151+
for &(start, stop) in &kept {
152+
bits.fill_range(start, stop, true);
153+
}
154+
// With the ranges cached on the mask, the filter copies the elements range by range.
155+
referenced.filter(Mask::from_buffer_with_slices(bits.freeze(), kept))?
156+
}
157+
};
152158
Ok((elements, offsets))
153159
}

0 commit comments

Comments
 (0)