This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/arrow-rs.git
The following commit(s) were added to refs/heads/main by this push:
new ef22fc44f3 perf: Optimize appending out-of-line views in `concat`,
`BatchCoalescer` (#11770)
ef22fc44f3 is described below
commit ef22fc44f3a92b142c1583261418326e565811a9
Author: Neil Conway <[email protected]>
AuthorDate: Tue Oct 27 05:29:35 2026 +0000
perf: Optimize appending out-of-line views in `concat`, `BatchCoalescer`
(#11770)
# Which issue does this PR close?
- N/A
# Rationale for this change
When views are appended to an array that already has data buffers, the
view of each out-of-line string must have its buffer index increased by
the number of buffers already in the array. The obvious way to do this
is to unpack the view (`u128` -> `ByteView`), update the `buffer_index`
field, and re-pack it. During the course of working on #11656, we found
that it is significantly faster to instead update the corresponding bits
in the raw view directly, via shifting and addition.
This PR applies this optimization to two additional places:
`GenericByteViewBuilder::append_array`, which `concat` uses for string
and binary view arrays, and
`InProgressByteViewArray::append_views_and_update_buffer_index`, which
is used by `BatchCoalescer`.
# What changes are included in this PR?
See above. We also add a sanity-check that the output buffer count fits
in 32 bits (which will always be true in practice; the previous behavior
of `GenericByteViewBuilder::append_array` was to silently truncate the
buffer count in this situation). The benchmark improvements for `concat`
and `coalesce_kernels` landed separately in #11768. This PR also passes
the RNG seed to the `Utf8` and `Dictionary(Int32, Utf8)` inputs of
`coalesce_kernels`, which previously generated the same strings for
every batch.
# Benchmarks
- AMD EPYC Milan (x86)
- coalesce_kernels, filter keeping 1% of rows
- single_utf8view, no nulls: 3.30 ms → 3.20 ms (−3.0%)
- single_utf8view (string_len=13..40), no nulls: 3.29 ms → 3.23 ms
(−2.0%) (runs 3% apart)
- single_binaryview, no nulls: 3.30 ms → 3.17 ms (−4.1%) (runs 6% apart)
- mixed_utf8view (max_string_len=20), no nulls: 1.78 ms → 1.73 ms
(−2.6%)
- mixed_binaryview (max_string_len=20), no nulls: 1.86 ms → 1.81 ms
(−2.9%) (runs 7% apart)
- single_utf8view, 10% nulls: 4.93 ms → 4.80 ms (−2.8%)
- single_utf8view (string_len=13..40), 10% nulls: 5.05 ms → 4.89 ms
(−3.2%)
- single_binaryview, 10% nulls: 4.92 ms → 4.89 ms (−0.5%)
- mixed_utf8view (max_string_len=20), 10% nulls: 3.09 ms → 3.05 ms
(−1.3%)
- mixed_binaryview (max_string_len=20), 10% nulls: 3.08 ms → 3.06 ms
(−0.4%)
- coalesce_kernels, filter keeping 80% of rows
- single_utf8view, no nulls: 868.1 µs → 783.3 µs (−9.8%)
- single_utf8view (string_len=13..40), no nulls: 867.8 µs → 800.2 µs
(−7.8%) (runs 4% apart)
- single_binaryview, no nulls: 868.5 µs → 793.2 µs (−8.7%) (runs 2.9%
apart)
- mixed_utf8view (max_string_len=20), no nulls: 730.6 µs → 701.1 µs
(−4.0%)
- mixed_binaryview (max_string_len=20), no nulls: 1.50 ms → 1.50 ms
(+0.3%) (copies its strings, so doesn't reach the changed code)
- single_utf8view, 10% nulls: 1.01 ms → 922.8 µs (−8.7%)
- single_utf8view (string_len=13..40), 10% nulls: 1.02 ms → 949.7 µs
(−6.5%)
- single_binaryview, 10% nulls: 1.02 ms → 921.9 µs (−10.0%)
- mixed_utf8view (max_string_len=20), 10% nulls: 900.1 µs → 869.6 µs
(−3.4%)
- mixed_binaryview (max_string_len=20), 10% nulls: 895.8 µs → 873.1 µs
(−2.5%)
- coalesce_kernels, take of 80% of rows
- single_utf8view, no nulls: 824.6 µs → 757.0 µs (−8.2%) (runs 2.8%
apart)
- single_binaryview, no nulls: 830.5 µs → 737.2 µs (−11.2%) (runs 4%
apart)
- mixed_utf8view (max_string_len=20), no nulls: 563.8 µs → 515.6 µs
(−8.5%) (runs 2.4% apart)
- mixed_binaryview (max_string_len=20), no nulls: 1.43 ms → 1.43 ms
(+0.2%) (copies its strings, so doesn't reach the changed code)
- single_utf8view, 10% nulls: 1.17 ms → 1.06 ms (−10.2%) (runs 7% apart)
- single_binaryview, 10% nulls: 1.15 ms → 1.05 ms (−8.5%) (runs 4%
apart)
- mixed_utf8view (max_string_len=20), 10% nulls: 924.3 µs → 885.9 µs
(−4.2%) (runs 3% apart)
- mixed_binaryview (max_string_len=20), 10% nulls: 919.9 µs → 906.8 µs
(−1.4%) (runs 6% apart)
- concat of 10 string view arrays of 8192 rows
- all_inline str_len=12, no nulls: 31.57 µs → 31.54 µs (−0.1%)
- str_len=20, no nulls: 74.88 µs → 48.63 µs (−35.1%)
- str_len=128, no nulls: 75.02 µs → 49.00 µs (−34.7%)
- mixed str_len=3..20, no nulls: 73.95 µs → 48.69 µs (−34.2%)
- all_inline str_len=12, 20% nulls: 32.44 µs → 32.39 µs (−0.2%)
- str_len=20, 20% nulls: 76.59 µs → 50.01 µs (−34.7%)
- str_len=128, 20% nulls: 76.39 µs → 49.99 µs (−34.6%)
- mixed str_len=3..20, 20% nulls: 75.54 µs → 49.92 µs (−33.9%) (runs 4%
apart)
- Apple M4 Max (ARM)
- coalesce_kernels, filter keeping 1% of rows
- single_utf8view, no nulls: 1.62 ms → 1.51 ms (−6.9%) (runs 4% apart)
- single_utf8view (string_len=13..40), no nulls: 1.62 ms → 1.54 ms
(−5.0%) (runs 4% apart)
- single_binaryview, no nulls: 1.57 ms → 1.48 ms (−5.7%) (runs 2.4%
apart)
- mixed_utf8view (max_string_len=20), no nulls: 1.08 ms → 1.04 ms
(−3.3%)
- mixed_binaryview (max_string_len=20), no nulls: 1.12 ms → 1.05 ms
(−6.1%) (runs 5% apart)
- single_utf8view, 10% nulls: 2.44 ms → 2.43 ms (−0.3%) (runs 2.2%
apart)
- single_utf8view (string_len=13..40), 10% nulls: 2.49 ms → 2.45 ms
(−1.4%) (runs 2.5% apart)
- single_binaryview, 10% nulls: 2.45 ms → 2.47 ms (+1.0%) (runs 6%
apart)
- mixed_utf8view (max_string_len=20), 10% nulls: 2.61 ms → 2.54 ms
(−2.6%)
- mixed_binaryview (max_string_len=20), 10% nulls: 2.58 ms → 2.53 ms
(−2.2%)
- coalesce_kernels, filter keeping 80% of rows
- single_utf8view, no nulls: 562.9 µs → 519.8 µs (−7.7%)
- single_utf8view (string_len=13..40), no nulls: 562.7 µs → 520.0 µs
(−7.6%)
- single_binaryview, no nulls: 562.5 µs → 520.3 µs (−7.5%)
- mixed_utf8view (max_string_len=20), no nulls: 535.7 µs → 517.7 µs
(−3.4%)
- mixed_binaryview (max_string_len=20), no nulls: 1.10 ms → 1.11 ms
(+1.7%) (copies its strings, so doesn't reach the changed code)
- single_utf8view, 10% nulls: 618.9 µs → 578.6 µs (−6.5%)
- single_utf8view (string_len=13..40), 10% nulls: 617.9 µs → 574.5 µs
(−7.0%)
- single_binaryview, 10% nulls: 621.6 µs → 574.5 µs (−7.6%)
- mixed_utf8view (max_string_len=20), 10% nulls: 600.8 µs → 581.4 µs
(−3.2%)
- mixed_binaryview (max_string_len=20), 10% nulls: 602.1 µs → 581.4 µs
(−3.4%)
- coalesce_kernels, take of 80% of rows
- single_utf8view, no nulls: 458.1 µs → 397.7 µs (−13.2%)
- single_binaryview, no nulls: 448.5 µs → 389.3 µs (−13.2%) (runs 3.0%
apart)
- mixed_utf8view (max_string_len=20), no nulls: 311.2 µs → 290.2 µs
(−6.7%)
- mixed_binaryview (max_string_len=20), no nulls: 995.3 µs → 999.1 µs
(+0.4%) (copies its strings, so doesn't reach the changed code)
- single_utf8view, 10% nulls: 641.5 µs → 560.2 µs (−12.7%) (runs 4%
apart)
- single_binaryview, 10% nulls: 639.6 µs → 545.5 µs (−14.7%)
- mixed_utf8view (max_string_len=20), 10% nulls: 468.9 µs → 450.5 µs
(−3.9%)
- mixed_binaryview (max_string_len=20), 10% nulls: 470.5 µs → 448.9 µs
(−4.6%)
- concat of 10 string view arrays of 8192 rows
- all_inline str_len=12, no nulls: 15.67 µs → 15.61 µs (−0.4%)
- str_len=20, no nulls: 31.13 µs → 27.40 µs (−12.0%)
- str_len=128, no nulls: 31.20 µs → 27.55 µs (−11.7%)
- mixed str_len=3..20, no nulls: 30.80 µs → 27.24 µs (−11.6%)
- all_inline str_len=12, 20% nulls: 16.16 µs → 16.10 µs (−0.4%)
- str_len=20, 20% nulls: 31.77 µs → 28.10 µs (−11.5%)
- str_len=128, 20% nulls: 31.84 µs → 28.28 µs (−11.2%)
- mixed str_len=3..20, 20% nulls: 31.33 µs → 27.92 µs (−10.9%)
# Are these changes tested?
Covered by existing tests.
# Are there any significant user-facing changes?
Only in a corner case: if the output buffer count exceeds `u32::MAX`, we
now panic rather than silently truncating the count.
---
.../src/builder/generic_bytes_view_builder.rs | 28 ++++++++++++++-----
arrow-select/src/coalesce/byte_view.rs | 25 ++++++++++++-----
arrow/benches/coalesce_kernels.rs | 32 ++++++++++++++++------
3 files changed, 62 insertions(+), 23 deletions(-)
diff --git a/arrow-array/src/builder/generic_bytes_view_builder.rs
b/arrow-array/src/builder/generic_bytes_view_builder.rs
index 6ff209ef74..3c21b8624b 100644
--- a/arrow-array/src/builder/generic_bytes_view_builder.rs
+++ b/arrow-array/src/builder/generic_bytes_view_builder.rs
@@ -224,6 +224,10 @@ impl<T: ByteViewType + ?Sized> GenericByteViewBuilder<T> {
/// Appends an array to the builder.
/// This will flush any in-progress block and append the data buffers
/// and add the (adapted) views.
+ ///
+ /// # Panics
+ ///
+ /// Panics if the builder would hold more than `u32::MAX` data buffers
pub fn append_array(&mut self, array: &GenericByteViewArray<T>) {
self.flush_in_progress();
// keep original views if this array is the first to be added or if
there are no data buffers (all inline views)
@@ -231,18 +235,28 @@ impl<T: ByteViewType + ?Sized> GenericByteViewBuilder<T> {
let starting_buffer = self.completed.len() as u32;
self.completed.extend(array.data_buffers().iter().cloned());
+ assert!(
+ u32::try_from(self.completed.len()).is_ok(),
+ "Too many blocks"
+ );
if keep_views {
self.views_buffer.extend_from_slice(array.views());
} else {
self.views_buffer.extend(array.views().iter().map(|v| {
- let mut byte_view = ByteView::from(*v);
- if byte_view.length > MAX_INLINE_VIEW_LEN {
- // Small views (<=12 bytes) are inlined, so only need to
update large views
- byte_view.buffer_index += starting_buffer;
- }
-
- byte_view.as_u128()
+ // A view of a string of 12 bytes or fewer stores the string
+ // inline and has no buffer index, so adding 0 leaves it
+ // unchanged.
+ let offset = if *v as u32 > MAX_INLINE_VIEW_LEN {
+ starting_buffer
+ } else {
+ 0
+ };
+ // The buffer index is bits 64 to 95 of a view. Adding
+ // `starting_buffer` gives the string's buffer index in the
+ // builder, which fits in 32 bits, so the sum never carries
+ // into bit 96.
+ v + ((offset as u128) << 64)
}));
}
diff --git a/arrow-select/src/coalesce/byte_view.rs
b/arrow-select/src/coalesce/byte_view.rs
index 085bf1f1e7..468aab0b52 100644
--- a/arrow-select/src/coalesce/byte_view.rs
+++ b/arrow-select/src/coalesce/byte_view.rs
@@ -194,8 +194,12 @@ impl<B: ByteViewType> InProgressByteViewArray<B> {
self.size_of_completed_buffers_from_current_source += buffers_size;
}
- let starting_buffer: u32 = self.completed.len().try_into().expect("too
many buffers");
+ let starting_buffer = self.completed.len() as u32;
self.completed.extend_from_slice(buffers);
+ assert!(
+ u32::try_from(self.completed.len()).is_ok(),
+ "too many buffers"
+ );
if starting_buffer == 0 {
// If there are no buffers, we can just use the views as is
@@ -203,12 +207,19 @@ impl<B: ByteViewType> InProgressByteViewArray<B> {
} else {
// If there are buffers, we need to update the buffer index
let updated_views = views.iter().map(|v| {
- let mut byte_view = ByteView::from(*v);
- if byte_view.length > MAX_INLINE_VIEW_LEN {
- // Small views (<=12 bytes) are inlined, so only need to
update large views
- byte_view.buffer_index += starting_buffer;
- }
- byte_view.as_u128()
+ // A view of a string of 12 bytes or fewer stores the string
+ // inline and has no buffer index, so adding 0 leaves it
+ // unchanged.
+ let offset = if *v as u32 > MAX_INLINE_VIEW_LEN {
+ starting_buffer
+ } else {
+ 0
+ };
+ // The buffer index is bits 64 to 95 of a view. Adding
+ // `starting_buffer` gives the string's buffer index in the
+ // output, which fits in 32 bits, so the sum never carries into
+ // bit 96.
+ v + ((offset as u128) << 64)
});
self.views.extend(updated_views);
diff --git a/arrow/benches/coalesce_kernels.rs
b/arrow/benches/coalesce_kernels.rs
index 974d2a4bb5..faaee8f6e6 100644
--- a/arrow/benches/coalesce_kernels.rs
+++ b/arrow/benches/coalesce_kernels.rs
@@ -1447,10 +1447,17 @@ impl DataStreamBuilder {
)
.with_timezone(Arc::clone(tz)),
),
- DataType::Utf8 => Arc::new(create_string_array::<i32>(
- self.batch_size,
- self.null_density,
- )), // TODO seed
+ // Strings of 0 to 399 bytes; `max_string_len` doesn't apply
+ DataType::Utf8 => Arc::new(
+ create_string_array_with_len_range_and_prefix_and_seed::<i32>(
+ self.batch_size,
+ self.null_density,
+ 0,
+ 399,
+ "",
+ seed,
+ ),
+ ),
DataType::Binary =>
Arc::new(create_binary_array_with_len_range_and_prefix_and_seed::<
i32,
>(
@@ -1482,11 +1489,18 @@ impl DataStreamBuilder {
if key_type.as_ref() == &DataType::Int32
&& value_type.as_ref() == &DataType::Utf8 =>
{
- Arc::new(create_string_dict_array::<Int32Type>(
- self.batch_size,
- self.null_density,
- self.max_string_len,
- )) // TODO seed
+ Arc::new(
+
create_string_array_with_len_range_and_prefix_and_seed::<i32>(
+ self.batch_size,
+ self.null_density,
+ self.max_string_len,
+ self.max_string_len,
+ "",
+ seed,
+ )
+ .iter()
+ .collect::<DictionaryArray<Int32Type>>(),
+ )
}
DataType::FixedSizeBinary(size) =>
Arc::new(create_fixed_size_binary_array(
self.batch_size,
