This is an automated email from the ASF dual-hosted git repository. github-merge-queue[bot] pushed a commit to branch gh-readonly-queue/main/pr-11770-c0acd1d7c149a937ba82b8ab30431de743fcad67 in repository https://gitbox.apache.org/repos/asf/arrow-rs.git
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,
