Skip to content

Commit 007894e

Browse files
authored
Reuse buffers when interleaving byte views (apache#11281)
# Which issue does this PR close? Fixes apache#11280 And also helps with: apache/datafusion#23565 # Rationale for this change See the original issue, but, basically the interleave kernel can make sub-optimal string views especially when buffers are shared. # What changes are included in this PR? We use a btreemap on the seen buffers (not individual values) and use that to prevent us from cloning the same buffer multiple times. # Are these changes tested? Yes tested, and locally benchmarks have shown a moderate speed increase in some of the interleave benchmarks, on my dev machine which has an **AMD Ryzen 9 9950X3D** processor: | benchmark | main | this PR | change | |-----------------------------------------------------------------------|----------|----------|--------| | interleave str_view(0.0) 100 [0..100, 100..230, 450..1000] | 284.5 ns | 268.6 ns | -5.6% | | interleave str_view(0.0) 400 [0..100, 100..230, 450..1000] | 706.9 ns | 563.9 ns | -20.2% | | interleave str_view(0.0) 1024 [0..100, 100..230, 450..1000] | 1.717 µs | 1.250 µs | -27.2% | | interleave str_view(0.0) 1024 [0..100, 100..230, 450..1000, 0..1000] | 1.783 µs | 1.274 µs | -28.6% | # Are there any user-facing changes? No user facing changes, just an optimization.
1 parent 2f3cd82 commit 007894e

1 file changed

Lines changed: 76 additions & 8 deletions

File tree

‎arrow-select/src/interleave.rs‎

Lines changed: 76 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -26,10 +26,13 @@ use arrow_array::types::*;
2626
use arrow_array::*;
2727
use arrow_buffer::bit_mask::set_bits;
2828
use arrow_buffer::bit_util;
29-
use arrow_buffer::{ArrowNativeType, BooleanBuffer, MutableBuffer, NullBuffer, OffsetBuffer};
29+
use arrow_buffer::{
30+
ArrowNativeType, BooleanBuffer, Buffer, MutableBuffer, NullBuffer, OffsetBuffer,
31+
};
3032
use arrow_data::ByteView;
3133
use arrow_data::transform::MutableArrayData;
3234
use arrow_schema::{ArrowError, DataType, FieldRef, Fields};
35+
use std::collections::BTreeMap;
3336
use std::sync::Arc;
3437

3538
macro_rules! primitive_helper {
@@ -314,8 +317,17 @@ fn interleave_views<T: ByteViewType>(
314317
offsets.push(total_buffers);
315318
}
316319

320+
// Marks a buffer in `buffer_to_new_index` that has not yet been referenced.
321+
//
322+
// The view's buffer index is a signed 32-bit integer in the Arrow specification,
323+
// so `u32::MAX` can never be a valid buffer index
324+
const UNASSIGNED: u32 = u32::MAX;
325+
317326
// contains the mapping from old buffer index to new buffer index
318-
let mut buffer_to_new_index = vec![None; total_buffers];
327+
let mut buffer_to_new_index = vec![UNASSIGNED; total_buffers];
328+
329+
// Contains the index in `buffers` of each buffer already emitted, keyed by identity
330+
let mut seen_buffers = BTreeMap::new();
319331

320332
let views: Vec<u128> = indices
321333
.iter()
@@ -329,12 +341,15 @@ fn interleave_views<T: ByteViewType>(
329341
// value is big enough to be in a variadic buffer
330342
let view = ByteView::from(*view);
331343
let buffer_to_new_idx = offsets[*array_idx] + view.buffer_index as usize;
332-
let new_buffer_idx: u32 =
333-
*buffer_to_new_index[buffer_to_new_idx].get_or_insert_with(|| {
334-
buffers.push(array.data_buffers()[view.buffer_index as usize].clone());
335-
(buffers.len() - 1) as u32
336-
});
337-
view.with_buffer_index(new_buffer_idx).as_u128()
344+
let new_buffer_idx = &mut buffer_to_new_index[buffer_to_new_idx];
345+
if *new_buffer_idx == UNASSIGNED {
346+
*new_buffer_idx = push_buffer(
347+
&mut seen_buffers,
348+
&mut buffers,
349+
&array.data_buffers()[view.buffer_index as usize],
350+
);
351+
}
352+
view.with_buffer_index(*new_buffer_idx).as_u128()
338353
})
339354
.collect();
340355

@@ -344,6 +359,24 @@ fn interleave_views<T: ByteViewType>(
344359
Ok(Arc::new(array))
345360
}
346361

362+
/// Returns the index of `buffer` in `buffers`, adding it if not already present.
363+
///
364+
/// Multiple input arrays, e.g. slices of the same array, may reference the same
365+
/// buffer, so this checks by identity to ensure it is only emitted once
366+
#[inline(never)]
367+
fn push_buffer(
368+
seen: &mut BTreeMap<(*const u8, usize), u32>,
369+
buffers: &mut Vec<Buffer>,
370+
buffer: &Buffer,
371+
) -> u32 {
372+
*seen
373+
.entry((buffer.as_ptr(), buffer.len()))
374+
.or_insert_with(|| {
375+
buffers.push(buffer.clone());
376+
(buffers.len() - 1) as u32
377+
})
378+
}
379+
347380
fn interleave_struct(
348381
fields: &Fields,
349382
values: &[&dyn Array],
@@ -1674,6 +1707,41 @@ mod tests {
16741707
);
16751708
}
16761709

1710+
#[test]
1711+
fn test_interleave_views_shared_buffers() {
1712+
let long = |i: usize| format!("long_string_not_inlined_{i}");
1713+
let base = StringViewArray::from_iter_values((0..10).map(long));
1714+
assert_eq!(base.data_buffers().len(), 1);
1715+
1716+
// Slices share the same buffers
1717+
let a = base.slice(0, 5);
1718+
let b = base.slice(5, 5);
1719+
// A distinct buffer list containing the same underlying buffer
1720+
let c = StringViewArray::try_new(base.views().clone(), base.data_buffers().to_vec(), None)
1721+
.unwrap();
1722+
1723+
let indices = &[(0, 1), (1, 2), (2, 3), (0, 4), (1, 0), (2, 9)];
1724+
let values = interleave(&[&a, &b, &c], indices).unwrap();
1725+
let result = values.as_string_view();
1726+
assert_eq!(result.data_buffers().len(), 1);
1727+
1728+
let expected: Vec<_> = [1, 7, 3, 4, 5, 9].into_iter().map(long).collect();
1729+
let actual: Vec<_> = result.iter().map(|x| x.unwrap().to_string()).collect();
1730+
assert_eq!(actual, expected);
1731+
1732+
// Many slices, exceeding the linear scan threshold
1733+
let slices: Vec<_> = (0..40).map(|i| base.slice(i % 10, 1)).collect();
1734+
let arrays: Vec<&dyn Array> = slices.iter().map(|x| x as &dyn Array).collect();
1735+
let indices: Vec<_> = (0..40).rev().map(|i| (i, 0)).collect();
1736+
let values = interleave(&arrays, &indices).unwrap();
1737+
let result = values.as_string_view();
1738+
assert_eq!(result.data_buffers().len(), 1);
1739+
1740+
let expected: Vec<_> = (0..40).rev().map(|i| long(i % 10)).collect();
1741+
let actual: Vec<_> = result.iter().map(|x| x.unwrap().to_string()).collect();
1742+
assert_eq!(actual, expected);
1743+
}
1744+
16771745
#[test]
16781746
fn test_interleave_views_multiple_buffers() {
16791747
let str1 = "very_long_string_from_first_buffer".as_bytes();

0 commit comments

Comments
 (0)