Repository navigation
Improve performance of concat_elements ByteViewArray concatenation - #10161
Conversation
|
I'll fix the MSRV issue as soon as I can. |
|
@neilconway thought you might find this one interesting as well. I'm thinking of making a similar PR for the concat functions in DataFusion. The semantics wrt null handling are different compared to |
e718dee to
8b2a515
Compare
Jefffrey
left a comment
Jefffrey
left a comment
There was a problem hiding this comment.
could you post the full benchmark results for reference?
| if let Some(n) = &null_buffer { | ||
| if n.null_count() == 0 { | ||
| null_buffer = None | ||
| } | ||
| } |
There was a problem hiding this comment.
I wonder if its beneficial to push this logic inside NullBuffer::union
There was a problem hiding this comment.
I've gone ahead and made that change. null_count() > 0 check added in union and union_many.
| .map(|len| len as usize) | ||
| .sum(); | ||
|
|
||
| if data_size > u32::MAX as usize { |
There was a problem hiding this comment.
I think it might actually be i32::MAX
There was a problem hiding this comment.
Indeed, #6172 has the relevant spec citation for view:
All integers (length, buffer index, and offset) are signed.
So we should indeed limit to i32::MAX.
Of course. Here's what I'm seeing on a MBP M2.
Raw criterion output``` pepijn@Flandrien arrow-rs % cargo bench --bench concatenate_elements -- utf8_view Compiling arrow-string v59.0.0 (/Users/pepijn/RustroverProjects/arrow-rs/arrow-string) Compiling arrow v59.0.0 (/Users/pepijn/RustroverProjects/arrow-rs/arrow) Finished `bench` profile [optimized] target(s) in 5.62s Running benches/concatenate_elements.rs (target/release/deps/concatenate_elements-3ba9b7123e418511) concat utf8_view all_inline max_str_len=12 null_density=0 time: [169.57 µs 170.05 µs 170.53 µs] Found 1 outliers among 100 measurements (1.00%) 1 (1.00%) high mildconcat utf8_view max_str_len=20 null_density=0 concat utf8_view max_str_len=128 null_density=0 concat utf8_view all_inline max_str_len=12 null_density=0.2 concat utf8_view max_str_len=20 null_density=0.2 concat utf8_view max_str_len=128 null_density=0.2 pepijn@Flandrien arrow-rs % cargo bench --bench concatenate_elements -- utf8_view concat utf8_view max_str_len=20 null_density=0 concat utf8_view max_str_len=128 null_density=0 concat utf8_view all_inline max_str_len=12 null_density=0.2 concat utf8_view max_str_len=20 null_density=0.2 concat utf8_view max_str_len=128 null_density=0.2 |
1a3373a to
e4ddb27
Compare
| .map(|len| len as usize) | ||
| .sum(); | ||
|
|
||
| if data_size > u32::MAX as usize { |
There was a problem hiding this comment.
| if data_size > u32::MAX as usize { | |
| if data_size > i32::MAX as usize { |
There was a problem hiding this comment.
I just noticed I had missed that one as well. I've restructured the code a little bit to eliminate the duplicated check.
alamb
changed the title
concat_elements ByteViewArray concatenation
| (Some(lhs), Some(rhs)) => Some(Self::new(lhs.inner() & rhs.inner())), | ||
| (Some(n), None) | (None, Some(n)) => Some(n.clone()), | ||
| (None, None) => None, | ||
| (Some(lhs), Some(rhs)) if lhs.null_count() > 0 || rhs.null_count() > 0 => { |
There was a problem hiding this comment.
this is a nice bonus optimization
| views: Vec<u128>, | ||
| data: Vec<u8>, | ||
| inline: Vec<u8>, | ||
| phantom: PhantomData<T>, |
There was a problem hiding this comment.
you couuld potentially avoid the generic bounds on the struct and only make finish generic
However, it is not clear to me that is all that much ebtter
diff --git a/arrow-string/src/concat_elements.rs b/arrow-string/src/concat_elements.rs
index 0739c804919..323b7883b7b 100644
--- a/arrow-string/src/concat_elements.rs
+++ b/arrow-string/src/concat_elements.rs
@@ -17,7 +17,6 @@
//! Provides utility functions for concatenation of elements in arrays.
-use std::marker::PhantomData;
use std::sync::Arc;
use arrow_array::builder::{BufferBuilder, FixedSizeBinaryBuilder, make_view};
@@ -221,25 +220,21 @@ pub fn concat_elements_fixed_size_binary(
Ok(result.finish())
}
-struct ConcatByteViewBuilder<T>
-where
- T: ByteViewType,
-{
+struct ConcatByteViewBuilder {
views: Vec<u128>,
data: Vec<u8>,
inline: Vec<u8>,
- phantom: PhantomData<T>,
}
-impl<T> ConcatByteViewBuilder<T>
-where
- T: ByteViewType,
-{
+impl ConcatByteViewBuilder {
/// Returns the elementwise concatenation of two [`GenericByteViewArray`]s.
- fn concat_elements_view_array(
+ fn concat_elements_view_array<T>(
left: &GenericByteViewArray<T>,
right: &GenericByteViewArray<T>,
- ) -> Result<GenericByteViewArray<T>, ArrowError> {
+ ) -> Result<GenericByteViewArray<T>, ArrowError>
+ where
+ T: ByteViewType,
+ {
let len = left.len();
if len != right.len() {
return Err(ArrowError::ComputeError(format!(
@@ -304,7 +299,6 @@ where
views: Vec::with_capacity(item_capacity),
data: Vec::with_capacity(data_capacity),
inline: Vec::with_capacity(MAX_INLINE_VIEW_LEN as usize),
- phantom: PhantomData,
}
}
@@ -339,10 +333,13 @@ where
self.views.push(0);
}
- fn finish(
+ fn finish<T>(
self,
null_buffer: Option<NullBuffer>,
- ) -> Result<GenericByteViewArray<T>, ArrowError> {
+ ) -> Result<GenericByteViewArray<T>, ArrowError>
+ where
+ T: ByteViewType,
+ {
if let Some(ref nulls) = null_buffer {
if nulls.len() != self.views.len() {
return Err(ArrowError::ComputeError(format!(There was a problem hiding this comment.
No strong opinion on this one. It might results in a slightly smaller binary indeed. Would you prefer this change?
There was a problem hiding this comment.
no, I don't have a strong opinion. What you have here is good.
Much appreciated. |
|
🚀 |
Which issue does this PR close?
None
Rationale for this change
During profiling of a DataFusion query String concatenation, in particular of two StringView arrays, proved to be a hotspot.
This MR proposes a revised version of
concat_elements_string_view_arraywhich eliminates some overhead that comes from using a fairly generic implementation strategy.Benchmarking shows improvement of 20-40%.
What changes are included in this PR?
StringViewBuilderbased concatenation implementation with one that directly writes the various buffers of the arrayNullBuffer::unionandNullBuffer::union_manyto treat buffers withnull_count == 0as equivalent toNoneso thatNonecan be returned in more cases.Are these changes tested?
NullBuffer::unionandNullBuffer::union_manyAre there any user-facing changes?
No