You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "XiangpengHao (via GitHub)" <gi...@apache.org> on 2024/07/22 15:48:59 UTC
[PR] Fast byte view construction [arrow-rs]
XiangpengHao opened a new pull request, #6102:
URL: https://github.com/apache/arrow-rs/pull/6102
# Which issue does this PR close?
<!--
We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes #123` indicates that this PR will close issue #123.
-->
Closes #6034. Let's merge #6101 first.
# Rationale for this change
<!--
Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed.
Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes.
-->
# What changes are included in this PR?
Implement a fast byte view construction, check issue #6034 for more details.
<!--
There is no need to duplicate the description in the issue here but it is sometimes worth providing a summary of the individual changes in this PR.
-->
# Are there any user-facing changes?
<!--
If there are user-facing changes then we may require documentation to be updated before approving the PR.
-->
<!---
If there are any breaking changes to public APIs, please add the `breaking change` label.
-->
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fast byte view construction [arrow-rs]
Posted by "Xuanwo (via GitHub)" <gi...@apache.org>.
Xuanwo commented on code in PR #6102:
URL: https://github.com/apache/arrow-rs/pull/6102#discussion_r1686850762
##########
arrow-array/src/builder/generic_bytes_view_builder.rs:
##########
@@ -420,23 +420,48 @@ pub type StringViewBuilder = GenericByteViewBuilder<StringViewType>;
/// [`GenericByteViewBuilder::append_null`] as normal.
pub type BinaryViewBuilder = GenericByteViewBuilder<BinaryViewType>;
+/// Creates a view from a fixed length input (the compiler can generate
+/// specialized code for this)
+fn make_view_inner<const LEN: usize>(data: &[u8]) -> u128 {
+ let mut view_buffer = [0; 16];
+ view_buffer[0..4].copy_from_slice(&(LEN as u32).to_le_bytes());
+ view_buffer[4..4 + LEN].copy_from_slice(&data[..LEN]);
+ u128::from_le_bytes(view_buffer)
+}
+
/// Create a view based on the given data, block id and offset
-#[inline(always)]
+/// Note that the code below is carefully examined with x86_64 assembly code: <https://godbolt.org/z/685YPsd5G>
+/// The goal is to avoid calling into `ptr::copy_non_interleave`, which makes function call (i.e., not inlined),
+/// which slows down things.
+#[inline(never)]
pub fn make_view(data: &[u8], block_id: u32, offset: u32) -> u128 {
- let len = data.len() as u32;
- if len <= 12 {
- let mut view_buffer = [0; 16];
- view_buffer[0..4].copy_from_slice(&len.to_le_bytes());
- view_buffer[4..4 + data.len()].copy_from_slice(data);
- u128::from_le_bytes(view_buffer)
- } else {
- let view = ByteView {
- length: len,
- prefix: u32::from_le_bytes(data[0..4].try_into().unwrap()),
- buffer_index: block_id,
- offset,
- };
- view.into()
+ let len = data.len();
+
+ // Generate specialized code for each potential small string length
+ // to improve performance
+ match len {
+ 0 => make_view_inner::<0>(data),
+ 1 => make_view_inner::<1>(data),
+ 2 => make_view_inner::<2>(data),
+ 3 => make_view_inner::<3>(data),
+ 4 => make_view_inner::<4>(data),
+ 5 => make_view_inner::<5>(data),
+ 6 => make_view_inner::<6>(data),
+ 7 => make_view_inner::<7>(data),
+ 8 => make_view_inner::<8>(data),
+ 9 => make_view_inner::<9>(data),
+ 10 => make_view_inner::<10>(data),
+ 11 => make_view_inner::<11>(data),
+ 12 => make_view_inner::<12>(data),
Review Comment:
Thanks a lot!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fast byte view construction [arrow-rs]
Posted by "Xuanwo (via GitHub)" <gi...@apache.org>.
Xuanwo commented on code in PR #6102:
URL: https://github.com/apache/arrow-rs/pull/6102#discussion_r1686829055
##########
arrow-array/src/builder/generic_bytes_view_builder.rs:
##########
@@ -420,23 +420,48 @@ pub type StringViewBuilder = GenericByteViewBuilder<StringViewType>;
/// [`GenericByteViewBuilder::append_null`] as normal.
pub type BinaryViewBuilder = GenericByteViewBuilder<BinaryViewType>;
+/// Creates a view from a fixed length input (the compiler can generate
+/// specialized code for this)
+fn make_view_inner<const LEN: usize>(data: &[u8]) -> u128 {
+ let mut view_buffer = [0; 16];
+ view_buffer[0..4].copy_from_slice(&(LEN as u32).to_le_bytes());
+ view_buffer[4..4 + LEN].copy_from_slice(&data[..LEN]);
+ u128::from_le_bytes(view_buffer)
+}
+
/// Create a view based on the given data, block id and offset
-#[inline(always)]
+/// Note that the code below is carefully examined with x86_64 assembly code: <https://godbolt.org/z/685YPsd5G>
+/// The goal is to avoid calling into `ptr::copy_non_interleave`, which makes function call (i.e., not inlined),
+/// which slows down things.
+#[inline(never)]
pub fn make_view(data: &[u8], block_id: u32, offset: u32) -> u128 {
- let len = data.len() as u32;
- if len <= 12 {
- let mut view_buffer = [0; 16];
- view_buffer[0..4].copy_from_slice(&len.to_le_bytes());
- view_buffer[4..4 + data.len()].copy_from_slice(data);
- u128::from_le_bytes(view_buffer)
- } else {
- let view = ByteView {
- length: len,
- prefix: u32::from_le_bytes(data[0..4].try_into().unwrap()),
- buffer_index: block_id,
- offset,
- };
- view.into()
+ let len = data.len();
+
+ // Generate specialized code for each potential small string length
+ // to improve performance
+ match len {
+ 0 => make_view_inner::<0>(data),
+ 1 => make_view_inner::<1>(data),
+ 2 => make_view_inner::<2>(data),
+ 3 => make_view_inner::<3>(data),
+ 4 => make_view_inner::<4>(data),
+ 5 => make_view_inner::<5>(data),
+ 6 => make_view_inner::<6>(data),
+ 7 => make_view_inner::<7>(data),
+ 8 => make_view_inner::<8>(data),
+ 9 => make_view_inner::<9>(data),
+ 10 => make_view_inner::<10>(data),
+ 11 => make_view_inner::<11>(data),
+ 12 => make_view_inner::<12>(data),
Review Comment:
This PR is really a WoW.
One question: do we choose `12` because it's the maximum value that fits within a `u128` (aka, `(12 + 4) * 8`)? It took me some time to figure this out. Should we add this explanation in the comments?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Faster `GenericByteView` construction [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #6102:
URL: https://github.com/apache/arrow-rs/pull/6102#discussion_r1688549688
##########
parquet/benches/arrow_reader.rs:
##########
@@ -1066,6 +1078,27 @@ fn add_benches(c: &mut Criterion) {
let mut group = c.benchmark_group("arrow_array_reader/BinaryViewArray");
+ // binary view, plain encoded, no NULLs, short string
+ let plain_byte_array_no_null_data = build_plain_encoded_byte_array_page_iterator_inner(
+ mandatory_binary_column_desc.clone(),
+ 0.0,
+ true,
+ );
+
+ // Short strings should not be slower than long strings, however, as discussed in https://github.com/apache/arrow-rs/issues/6034,
Review Comment:
This comment seems out of date. Doesn't this PR close https://github.com/apache/arrow-rs/issues/6034 ?
##########
arrow-array/src/builder/generic_bytes_view_builder.rs:
##########
@@ -420,23 +420,49 @@ pub type StringViewBuilder = GenericByteViewBuilder<StringViewType>;
/// [`GenericByteViewBuilder::append_null`] as normal.
pub type BinaryViewBuilder = GenericByteViewBuilder<BinaryViewType>;
+/// Creates a view from a fixed length input (the compiler can generate
+/// specialized code for this)
+fn make_inlined_view<const LEN: usize>(data: &[u8]) -> u128 {
+ let mut view_buffer = [0; 16];
+ view_buffer[0..4].copy_from_slice(&(LEN as u32).to_le_bytes());
+ view_buffer[4..4 + LEN].copy_from_slice(&data[..LEN]);
+ u128::from_le_bytes(view_buffer)
+}
+
/// Create a view based on the given data, block id and offset
-#[inline(always)]
+/// Note that the code below is carefully examined with x86_64 assembly code: <https://godbolt.org/z/685YPsd5G>
Review Comment:
❤️
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Faster `GenericByteView` construction [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #6102:
URL: https://github.com/apache/arrow-rs/pull/6102#issuecomment-2246055362
Thanks again @XiangpengHao and @Xuanwo for the review
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fast byte view construction [arrow-rs]
Posted by "XiangpengHao (via GitHub)" <gi...@apache.org>.
XiangpengHao commented on code in PR #6102:
URL: https://github.com/apache/arrow-rs/pull/6102#discussion_r1686837096
##########
arrow-array/src/builder/generic_bytes_view_builder.rs:
##########
@@ -420,23 +420,48 @@ pub type StringViewBuilder = GenericByteViewBuilder<StringViewType>;
/// [`GenericByteViewBuilder::append_null`] as normal.
pub type BinaryViewBuilder = GenericByteViewBuilder<BinaryViewType>;
+/// Creates a view from a fixed length input (the compiler can generate
+/// specialized code for this)
+fn make_view_inner<const LEN: usize>(data: &[u8]) -> u128 {
+ let mut view_buffer = [0; 16];
+ view_buffer[0..4].copy_from_slice(&(LEN as u32).to_le_bytes());
+ view_buffer[4..4 + LEN].copy_from_slice(&data[..LEN]);
+ u128::from_le_bytes(view_buffer)
+}
+
/// Create a view based on the given data, block id and offset
-#[inline(always)]
+/// Note that the code below is carefully examined with x86_64 assembly code: <https://godbolt.org/z/685YPsd5G>
+/// The goal is to avoid calling into `ptr::copy_non_interleave`, which makes function call (i.e., not inlined),
+/// which slows down things.
+#[inline(never)]
pub fn make_view(data: &[u8], block_id: u32, offset: u32) -> u128 {
- let len = data.len() as u32;
- if len <= 12 {
- let mut view_buffer = [0; 16];
- view_buffer[0..4].copy_from_slice(&len.to_le_bytes());
- view_buffer[4..4 + data.len()].copy_from_slice(data);
- u128::from_le_bytes(view_buffer)
- } else {
- let view = ByteView {
- length: len,
- prefix: u32::from_le_bytes(data[0..4].try_into().unwrap()),
- buffer_index: block_id,
- offset,
- };
- view.into()
+ let len = data.len();
+
+ // Generate specialized code for each potential small string length
+ // to improve performance
+ match len {
+ 0 => make_view_inner::<0>(data),
+ 1 => make_view_inner::<1>(data),
+ 2 => make_view_inner::<2>(data),
+ 3 => make_view_inner::<3>(data),
+ 4 => make_view_inner::<4>(data),
+ 5 => make_view_inner::<5>(data),
+ 6 => make_view_inner::<6>(data),
+ 7 => make_view_inner::<7>(data),
+ 8 => make_view_inner::<8>(data),
+ 9 => make_view_inner::<9>(data),
+ 10 => make_view_inner::<10>(data),
+ 11 => make_view_inner::<11>(data),
+ 12 => make_view_inner::<12>(data),
Review Comment:
> do we choose 12 because it's the maximum value that fits within a u128 (aka, (12 + 4) * 8)?
Exactly! Thanks for pointing out this! I've added a comment and renamed `make_view_inner` to `make_inlined_view` to make it clearer.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Faster `GenericByteView` construction [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb merged PR #6102:
URL: https://github.com/apache/arrow-rs/pull/6102
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org