You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "zhuqi-lucas (via GitHub)" <gi...@apache.org> on 2025/06/23 14:42:29 UTC
[PR] Perf: Change use of inline_value to inline it to a u128 [arrow-rs]
zhuqi-lucas opened a new pull request, #7748:
URL: https://github.com/apache/arrow-rs/pull/7748
# Which issue does this PR close?
Closes [#7743](https://github.com/apache/arrow-rs/issues/7743)
# Rationale for this change
Change the fast path to use u128 to compare for lt case, also for inline <12 case to use u128 to compare.
# What changes are included in this PR?
Change the fast path to use u128 to compare for lt case, also for inline <12 case to use u128 to compare.
# Are there any user-facing changes?
No
--
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] Perf: Add prefix compare for inlined compare and change use of inline_value to inline it to a u128 [arrow-rs]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #7748:
URL: https://github.com/apache/arrow-rs/pull/7748#discussion_r2165810324
##########
arrow-array/src/array/byte_view_array.rs:
##########
@@ -545,9 +545,41 @@ impl<T: ByteViewType + ?Sized> GenericByteViewArray<T> {
let r_len = *r_view as u32;
if l_len <= 12 && r_len <= 12 {
- let l_data = unsafe { GenericByteViewArray::<T>::inline_value(l_view, l_len as usize) };
- let r_data = unsafe { GenericByteViewArray::<T>::inline_value(r_view, r_len as usize) };
- return l_data.cmp(r_data);
+ // Directly load the 16-byte view as an u128 (little-endian)
+ let l_bits: u128 = *l_view;
+ let r_bits: u128 = *r_view;
+
+ // The lower 32 bits encode the length (little-endian),
+ // the upper 96 bits hold the actual data
+ let l_len = (l_bits as u32) as usize;
+ let r_len = (r_bits as u32) as usize;
+
+ // Mask to keep only the upper 96 bits (data), zeroing out the length
+ // 0xFFFF_FFFF_0000_0000_..._0000
+ const DATA_MASK: u128 = !0u128 << 32;
+
+ // Remove the length bits, leaving only the data
+ let l_data = (l_bits & DATA_MASK) >> 32;
Review Comment:
I wonder if we can avoid some of the bit masking by using `ByteView` here ?
--
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] Perf: Change use of inline_value to inline it to a u128 [arrow-rs]
Posted by "zhuqi-lucas (via GitHub)" <gi...@apache.org>.
zhuqi-lucas commented on PR #7748:
URL: https://github.com/apache/arrow-rs/pull/7748#issuecomment-2996776729
Peformance result:
**2.53 faster for lt StringViewArray StringViewArray inlined bytes**
**1.16 faster for lt scalar StringViewArray**
```rust
critcmp main issue_7743 --filter "iew"
group issue_7743 main
----- ---------- ----
StringViewArray: regexp_matches_utf8view scalar benchmarks/regexp_matches_utf8view scalar complex 1.00 1250.8±16.53µs ? ?/sec 1.02 1270.1±34.61µs ? ?/sec
StringViewArray: regexp_matches_utf8view scalar benchmarks/regexp_matches_utf8view scalar contains 1.01 1224.8±12.97µs ? ?/sec 1.00 1218.6±18.65µs ? ?/sec
StringViewArray: regexp_matches_utf8view scalar benchmarks/regexp_matches_utf8view scalar ends with 1.00 673.7±3.52µs ? ?/sec 1.00 676.2±6.47µs ? ?/sec
StringViewArray: regexp_matches_utf8view scalar benchmarks/regexp_matches_utf8view scalar starts with 1.00 615.0±6.85µs ? ?/sec 1.00 614.5±6.27µs ? ?/sec
eq StringViewArray StringViewArray 1.04 6.0±0.05ms ? ?/sec 1.00 5.8±0.06ms ? ?/sec
eq StringViewArray StringViewArray inlined bytes 1.00 2.7±0.03ms ? ?/sec 1.01 2.7±0.05ms ? ?/sec
eq long same prefix strings StringViewArray 1.02 512.6±8.67µs ? ?/sec 1.00 503.9±9.59µs ? ?/sec
eq scalar StringViewArray 13 bytes 1.00 3.6±0.04ms ? ?/sec 1.02 3.7±0.03ms ? ?/sec
eq scalar StringViewArray 4 bytes 1.02 3.9±0.03ms ? ?/sec 1.00 3.8±0.04ms ? ?/sec
eq scalar StringViewArray 6 bytes 1.02 3.9±0.03ms ? ?/sec 1.00 3.8±0.04ms ? ?/sec
like_utf8view scalar complex 1.01 81.0±0.86ms ? ?/sec 1.00 80.3±0.62ms ? ?/sec
like_utf8view scalar contains 1.00 76.5±0.59ms ? ?/sec 1.00 76.3±0.95ms ? ?/sec
like_utf8view scalar ends with 13 bytes 1.01 19.0±0.25ms ? ?/sec 1.00 18.9±0.26ms ? ?/sec
like_utf8view scalar ends with 4 bytes 1.00 19.0±0.22ms ? ?/sec 1.00 19.0±0.23ms ? ?/sec
like_utf8view scalar ends with 6 bytes 1.00 18.9±0.18ms ? ?/sec 1.00 19.0±0.24ms ? ?/sec
like_utf8view scalar equals 1.01 14.0±0.15ms ? ?/sec 1.00 13.9±0.16ms ? ?/sec
like_utf8view scalar starts with 13 bytes 1.01 18.3±0.24ms ? ?/sec 1.00 18.2±0.27ms ? ?/sec
like_utf8view scalar starts with 4 bytes 1.00 10.7±0.18ms ? ?/sec 1.00 10.7±0.23ms ? ?/sec
like_utf8view scalar starts with 6 bytes 1.00 18.5±0.22ms ? ?/sec 1.00 18.4±0.24ms ? ?/sec
long same prefix strings like_utf8view scalar complex 1.01 617.5±11.35µs ? ?/sec 1.00 610.9±7.55µs ? ?/sec
long same prefix strings like_utf8view scalar contains 1.01 1834.8±21.26µs ? ?/sec 1.00 1810.7±21.24µs ? ?/sec
long same prefix strings like_utf8view scalar ends with 1.00 605.1±9.37µs ? ?/sec 1.00 603.2±6.33µs ? ?/sec
long same prefix strings like_utf8view scalar equals 1.01 196.9±5.64µs ? ?/sec 1.00 194.2±4.78µs ? ?/sec
long same prefix strings like_utf8view scalar starts with 1.00 669.1±5.56µs ? ?/sec 1.00 666.8±5.22µs ? ?/sec
lt StringViewArray StringViewArray inlined bytes 1.00 19.0±0.39ms ? ?/sec 2.53 48.1±1.10ms ? ?/sec
lt long same prefix strings StringViewArray 1.00 485.9±8.31µs ? ?/sec 1.04 504.3±8.39µs ? ?/sec
lt scalar StringViewArray 1.00 22.3±1.39ms ? ?/sec 1.16 25.8±1.28ms ? ?/sec
neq long same prefix strings StringViewArray 1.00 506.5±7.39µs ? ?/sec 1.00 506.4±10.21µs ? ?/sec
```
--
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] Perf: Add prefix compare for inlined compare and change use of inline_value to inline it to a u128 [arrow-rs]
Posted by "zhuqi-lucas (via GitHub)" <gi...@apache.org>.
zhuqi-lucas commented on code in PR #7748:
URL: https://github.com/apache/arrow-rs/pull/7748#discussion_r2166454165
##########
arrow-ord/src/cmp.rs:
##########
@@ -571,7 +572,7 @@ impl<'a, T: ByteViewType> ArrayOrd for &'a GenericByteViewArray<T> {
let r_view = unsafe { r.0.views().get_unchecked(r.1) };
if l.0.data_buffers().is_empty() && r.0.data_buffers().is_empty() {
// For eq case, we can directly compare the inlined bytes
- return l_view.cmp(r_view).is_eq();
+ return l_view.eq(r_view);
Review Comment:
Good suggestion!
--
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] Perf: Add prefix compare for inlined compare and change use of inline_value to inline it to a u128 [arrow-rs]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #7748:
URL: https://github.com/apache/arrow-rs/pull/7748#discussion_r2166444824
##########
arrow-array/src/array/byte_view_array.rs:
##########
@@ -545,9 +545,41 @@ impl<T: ByteViewType + ?Sized> GenericByteViewArray<T> {
let r_len = *r_view as u32;
if l_len <= 12 && r_len <= 12 {
- let l_data = unsafe { GenericByteViewArray::<T>::inline_value(l_view, l_len as usize) };
- let r_data = unsafe { GenericByteViewArray::<T>::inline_value(r_view, r_len as usize) };
- return l_data.cmp(r_data);
+ // Directly load the 16-byte view as an u128 (little-endian)
+ let l_bits: u128 = *l_view;
+ let r_bits: u128 = *r_view;
+
+ // The lower 32 bits encode the length (little-endian),
+ // the upper 96 bits hold the actual data
+ let l_len = (l_bits as u32) as usize;
+ let r_len = (r_bits as u32) as usize;
+
+ // Mask to keep only the upper 96 bits (data), zeroing out the length
+ // 0xFFFF_FFFF_0000_0000_..._0000
+ const DATA_MASK: u128 = !0u128 << 32;
+
+ // Remove the length bits, leaving only the data
+ let l_data = (l_bits & DATA_MASK) >> 32;
Review Comment:
I think the compiler might be smart enough to see it is actually the same (I changed it somewhere else, but couldn't detect performance difference).
--
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] Perf: Add prefix compare for inlined compare and change use of inline_value to inline it to a u128 [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #7748:
URL: https://github.com/apache/arrow-rs/pull/7748#issuecomment-3039032956
I believe this PR introduced a bug in comparisons, see
- https://github.com/apache/arrow-rs/issues/7874
--
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] Perf: Add prefix compare for inlined compare and change use of inline_value to inline it to a u128 [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #7748:
URL: https://github.com/apache/arrow-rs/pull/7748#issuecomment-3016153350
> The integration CI seems flaky recently, i am not sure why.
Yeah, @etseidl and I have seen that too -- I filed a ticket
- https://github.com/apache/arrow-rs/issues/7817
--
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] Perf: Add prefix compare for inlined compare and change use of inline_value to inline it to a u128 [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb merged PR #7748:
URL: https://github.com/apache/arrow-rs/pull/7748
--
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] Perf: Add prefix compare for inlined compare and change use of inline_value to inline it to a u128 [arrow-rs]
Posted by "zhuqi-lucas (via GitHub)" <gi...@apache.org>.
zhuqi-lucas commented on PR #7748:
URL: https://github.com/apache/arrow-rs/pull/7748#issuecomment-3005034666
Updated @Dandandan @jhorstmann , amazing result for latest PR:
6.x faster for lt inlined bytes
and
1.3x faster for lt scalar StringViewArray
```rust
lt StringViewArray StringViewArray inlined bytes 1.00 7.8±0.29ms ? ?/sec 6.21 48.7±0.71ms ? ?/sec
lt scalar StringViewArray 1.00 19.5±1.97ms ? ?/sec 1.32 25.8±1.28ms ? ?/sec
```
```rust
critcmp main issue_7743 --filter "iew"
group issue_7743 main
----- ---------- ----
StringViewArray: regexp_matches_utf8view scalar benchmarks/regexp_matches_utf8view scalar complex 1.00 1208.3±22.24µs ? ?/sec 1.05 1270.1±34.61µs ? ?/sec
StringViewArray: regexp_matches_utf8view scalar benchmarks/regexp_matches_utf8view scalar contains 1.00 1221.9±32.61µs ? ?/sec 1.00 1218.6±18.65µs ? ?/sec
StringViewArray: regexp_matches_utf8view scalar benchmarks/regexp_matches_utf8view scalar ends with 1.00 677.7±9.00µs ? ?/sec 1.00 676.2±6.47µs ? ?/sec
StringViewArray: regexp_matches_utf8view scalar benchmarks/regexp_matches_utf8view scalar starts with 1.03 629.9±17.64µs ? ?/sec 1.00 614.5±6.27µs ? ?/sec
eq StringViewArray StringViewArray 1.00 5.7±0.06ms ? ?/sec 1.02 5.8±0.06ms ? ?/sec
eq StringViewArray StringViewArray inlined bytes 1.00 2.7±0.01ms ? ?/sec 1.00 2.7±0.03ms ? ?/sec
eq long same prefix strings StringViewArray 1.00 503.7±9.42µs ? ?/sec 1.00 503.9±9.59µs ? ?/sec
eq scalar StringViewArray 13 bytes 1.02 3.8±0.03ms ? ?/sec 1.00 3.7±0.03ms ? ?/sec
eq scalar StringViewArray 4 bytes 1.01 3.9±0.03ms ? ?/sec 1.00 3.8±0.04ms ? ?/sec
eq scalar StringViewArray 6 bytes 1.00 3.8±0.03ms ? ?/sec 1.00 3.8±0.04ms ? ?/sec
like_utf8view scalar complex 1.01 81.2±1.62ms ? ?/sec 1.00 80.3±0.62ms ? ?/sec
like_utf8view scalar contains 1.00 75.7±0.91ms ? ?/sec 1.01 76.3±0.95ms ? ?/sec
like_utf8view scalar ends with 13 bytes 1.00 18.8±0.23ms ? ?/sec 1.00 18.9±0.26ms ? ?/sec
like_utf8view scalar ends with 4 bytes 1.00 18.7±0.24ms ? ?/sec 1.01 19.0±0.23ms ? ?/sec
like_utf8view scalar ends with 6 bytes 1.00 18.8±0.24ms ? ?/sec 1.01 19.0±0.24ms ? ?/sec
like_utf8view scalar equals 1.00 13.9±0.11ms ? ?/sec 1.01 13.9±0.16ms ? ?/sec
like_utf8view scalar starts with 13 bytes 1.02 18.5±0.37ms ? ?/sec 1.00 18.2±0.27ms ? ?/sec
like_utf8view scalar starts with 4 bytes 1.00 10.5±0.16ms ? ?/sec 1.02 10.7±0.23ms ? ?/sec
like_utf8view scalar starts with 6 bytes 1.00 18.3±0.17ms ? ?/sec 1.01 18.4±0.24ms ? ?/sec
long same prefix strings like_utf8view scalar complex 1.00 601.3±2.97µs ? ?/sec 1.02 610.9±7.55µs ? ?/sec
long same prefix strings like_utf8view scalar contains 1.00 1786.0±21.54µs ? ?/sec 1.01 1810.7±21.24µs ? ?/sec
long same prefix strings like_utf8view scalar ends with 1.00 591.8±4.87µs ? ?/sec 1.02 603.2±6.33µs ? ?/sec
long same prefix strings like_utf8view scalar equals 1.00 193.7±4.41µs ? ?/sec 1.00 194.2±4.78µs ? ?/sec
long same prefix strings like_utf8view scalar starts with 1.00 667.8±5.49µs ? ?/sec 1.00 666.8±5.22µs ? ?/sec
lt StringViewArray StringViewArray inlined bytes 1.00 7.8±0.29ms ? ?/sec 6.21 48.7±0.71ms ? ?/sec
lt long same prefix strings StringViewArray 1.00 486.2±12.05µs ? ?/sec 1.04 504.3±8.39µs ? ?/sec
lt scalar StringViewArray 1.00 19.5±1.97ms ? ?/sec 1.32 25.8±1.28ms ? ?/sec
neq long same prefix strings StringViewArray 1.00 502.9±12.25µs ? ?/sec 1.01 506.4±10.21µs ? ?/sec
```
--
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] Perf: Add prefix compare for inlined compare and change use of inline_value to inline it to a u128 [arrow-rs]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #7748:
URL: https://github.com/apache/arrow-rs/pull/7748#discussion_r2165814101
##########
arrow-ord/src/cmp.rs:
##########
@@ -589,15 +589,45 @@ impl<'a, T: ByteViewType> ArrayOrd for &'a GenericByteViewArray<T> {
#[inline(always)]
fn is_lt(l: Self::Item, r: Self::Item) -> bool {
+ // If both arrays use only the inline buffer
if l.0.data_buffers().is_empty() && r.0.data_buffers().is_empty() {
- let l_view = unsafe { l.0.views().get_unchecked(l.1) };
- let r_view = unsafe { r.0.views().get_unchecked(r.1) };
- let l_len = *l_view as u32 as usize;
- let r_len = *r_view as u32 as usize;
- let l_bytes = unsafe { GenericByteViewArray::<T>::inline_value(l_view, l_len) };
- let r_bytes = unsafe { GenericByteViewArray::<T>::inline_value(r_view, r_len) };
- return l_bytes.cmp(r_bytes).is_lt();
+ // Directly load the 16-byte view as an u128 (little-endian)
+ let l_bits: u128 = unsafe { *l.0.views().get_unchecked(l.1) };
+ let r_bits: u128 = unsafe { *r.0.views().get_unchecked(r.1) };
+
+ // The lower 32 bits encode the length (little-endian),
+ // the upper 96 bits hold the actual data
+ let l_len = (l_bits as u32) as usize;
+ let r_len = (r_bits as u32) as usize;
+
+ // Mask to keep only the upper 96 bits (data), zeroing out the length
+ // 0xFFFF_FFFF_0000_0000_..._0000
+ const DATA_MASK: u128 = !0u128 << 32;
+
+ // Remove the length bits, leaving only the data
+ let l_data = (l_bits & DATA_MASK) >> 32;
+ let r_data = (r_bits & DATA_MASK) >> 32;
Review Comment:
Same here :)
--
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] Perf: Add prefix compare for inlined compare and change use of inline_value to inline it to a u128 [arrow-rs]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #7748:
URL: https://github.com/apache/arrow-rs/pull/7748#issuecomment-3016437616
Thanks again @zhuqi-lucas and @Dandandan
--
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] Perf: Add prefix compare for inlined compare and change use of inline_value to inline it to a u128 [arrow-rs]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #7748:
URL: https://github.com/apache/arrow-rs/pull/7748#discussion_r2166441174
##########
arrow-ord/src/cmp.rs:
##########
@@ -571,7 +572,7 @@ impl<'a, T: ByteViewType> ArrayOrd for &'a GenericByteViewArray<T> {
let r_view = unsafe { r.0.views().get_unchecked(r.1) };
if l.0.data_buffers().is_empty() && r.0.data_buffers().is_empty() {
// For eq case, we can directly compare the inlined bytes
- return l_view.cmp(r_view).is_eq();
+ return l_view.eq(r_view);
Review Comment:
```suggestion
return l_view == r_view;
```
--
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] Perf: Add prefix compare for inlined compare and change use of inline_value to inline it to a u128 [arrow-rs]
Posted by "zhuqi-lucas (via GitHub)" <gi...@apache.org>.
zhuqi-lucas commented on code in PR #7748:
URL: https://github.com/apache/arrow-rs/pull/7748#discussion_r2166362006
##########
arrow-array/src/array/byte_view_array.rs:
##########
@@ -545,9 +545,41 @@ impl<T: ByteViewType + ?Sized> GenericByteViewArray<T> {
let r_len = *r_view as u32;
if l_len <= 12 && r_len <= 12 {
- let l_data = unsafe { GenericByteViewArray::<T>::inline_value(l_view, l_len as usize) };
- let r_data = unsafe { GenericByteViewArray::<T>::inline_value(r_view, r_len as usize) };
- return l_data.cmp(r_data);
+ // Directly load the 16-byte view as an u128 (little-endian)
+ let l_bits: u128 = *l_view;
+ let r_bits: u128 = *r_view;
+
+ // The lower 32 bits encode the length (little-endian),
+ // the upper 96 bits hold the actual data
+ let l_len = (l_bits as u32) as usize;
+ let r_len = (r_bits as u32) as usize;
+
+ // Mask to keep only the upper 96 bits (data), zeroing out the length
+ // 0xFFFF_FFFF_0000_0000_..._0000
+ const DATA_MASK: u128 = !0u128 << 32;
+
+ // Remove the length bits, leaving only the data
+ let l_data = (l_bits & DATA_MASK) >> 32;
Review Comment:
Thank you @Dandandan , reduce the bit masking in latest PR, i think ByteView from will use all convert to the struct field, so i just use part of logic in latest PR.
--
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] Perf: Add prefix compare for inlined compare and change use of inline_value to inline it to a u128 [arrow-rs]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on PR #7748:
URL: https://github.com/apache/arrow-rs/pull/7748#issuecomment-3003380190
> lt StringViewArray StringViewArray inlined bytes 1.00 19.0±0.39ms ? ?/sec 2.53 48.1±1.10ms ? ?/sec
Amazing 😎 !! Perhaps we can use some less manual bit masking/shifting while still producing roughly the same code?
--
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] Perf: Add prefix compare for inlined compare and change use of inline_value to inline it to a u128 [arrow-rs]
Posted by "zhuqi-lucas (via GitHub)" <gi...@apache.org>.
zhuqi-lucas commented on code in PR #7748:
URL: https://github.com/apache/arrow-rs/pull/7748#discussion_r2166391955
##########
arrow-array/src/array/byte_view_array.rs:
##########
@@ -537,17 +538,46 @@ impl<T: ByteViewType + ?Sized> GenericByteViewArray<T> {
left_idx: usize,
right: &GenericByteViewArray<T>,
right_idx: usize,
- ) -> std::cmp::Ordering {
+ ) -> Ordering {
let l_view = left.views().get_unchecked(left_idx);
let l_len = *l_view as u32;
let r_view = right.views().get_unchecked(right_idx);
let r_len = *r_view as u32;
if l_len <= 12 && r_len <= 12 {
- let l_data = unsafe { GenericByteViewArray::<T>::inline_value(l_view, l_len as usize) };
- let r_data = unsafe { GenericByteViewArray::<T>::inline_value(r_view, r_len as usize) };
- return l_data.cmp(r_data);
+ // Directly load the 16-byte view as an u128 (little-endian)
+ let l_bits: u128 = unsafe { *left.views().get_unchecked(left_idx) };
+ let r_bits: u128 = unsafe { *right.views().get_unchecked(right_idx) };
+
+ // The lower 32 bits encode the length (little-endian),
+ // the upper 96 bits hold the actual data
+ let l_len = l_bits as u32;
+ let r_len = r_bits as u32;
+
+ // Remove the length bits, leaving only the data
+ let l_data = l_bits >> 32;
+ let r_data = r_bits >> 32;
+
+ // The data is stored in little-endian order. To compare lexicographically,
+ // convert to big-endian:
+ let l_be = l_data.swap_bytes();
+ let r_be = r_data.swap_bytes();
+
+ // Compare only the first min_len bytes
+ let min_len = l_len.min(r_len);
+ // We have all 12 bytes in the high bits, but only want the top min_len
+ let shift = (12 - min_len) * 8;
+ let l_partial = l_be >> shift;
Review Comment:
Thank you @jhorstmann for review, good suggestion, i will address it!
--
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] Perf: Add prefix compare for inlined compare and change use of inline_value to inline it to a u128 [arrow-rs]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #7748:
URL: https://github.com/apache/arrow-rs/pull/7748#discussion_r2166438292
##########
arrow-ord/src/cmp.rs:
##########
@@ -642,17 +669,42 @@ pub fn compare_byte_view<T: ByteViewType>(
left_idx: usize,
right: &GenericByteViewArray<T>,
right_idx: usize,
-) -> std::cmp::Ordering {
+) -> Ordering {
assert!(left_idx < left.len());
assert!(right_idx < right.len());
if left.data_buffers().is_empty() && right.data_buffers().is_empty() {
- let l_view = unsafe { left.views().get_unchecked(left_idx) };
- let r_view = unsafe { right.views().get_unchecked(right_idx) };
- let l_len = *l_view as u32 as usize;
- let r_len = *r_view as u32 as usize;
- let l_bytes = unsafe { GenericByteViewArray::<T>::inline_value(l_view, l_len) };
- let r_bytes = unsafe { GenericByteViewArray::<T>::inline_value(r_view, r_len) };
- return l_bytes.cmp(r_bytes);
+ // Directly load the 16-byte view as an u128 (little-endian)
+ let l_bits: u128 = unsafe { *left.views().get_unchecked(left_idx) };
+ let r_bits: u128 = unsafe { *right.views().get_unchecked(right_idx) };
+
+ // The lower 32 bits encode the length (little-endian),
+ // the upper 96 bits hold the actual data
+ let l_len = l_bits as u32;
+ let r_len = r_bits as u32;
+
+ // Remove the length bits, leaving only the data
+ let l_data = l_bits >> 32;
+ let r_data = r_bits >> 32;
+
+ // The data is stored in little-endian order. To compare lexicographically,
+ // convert to big-endian:
+ let l_be = l_data.swap_bytes();
+ let r_be = r_data.swap_bytes();
+
+ // Compare only the first min_len bytes
+ let min_len = l_len.min(r_len);
+ // We have all 12 bytes in the high bits, but only want the top min_len
+ let shift = (12 - min_len) * 8;
+ let l_partial = l_be >> shift;
+ let r_partial = r_be >> shift;
+ if l_partial < r_partial {
Review Comment:
this can be written as `l_partial.cmp(r_partial).then_with(|| { l_len.cmp(&r_len) })
##########
arrow-ord/src/cmp.rs:
##########
@@ -642,17 +669,42 @@ pub fn compare_byte_view<T: ByteViewType>(
left_idx: usize,
right: &GenericByteViewArray<T>,
right_idx: usize,
-) -> std::cmp::Ordering {
+) -> Ordering {
assert!(left_idx < left.len());
assert!(right_idx < right.len());
if left.data_buffers().is_empty() && right.data_buffers().is_empty() {
- let l_view = unsafe { left.views().get_unchecked(left_idx) };
- let r_view = unsafe { right.views().get_unchecked(right_idx) };
- let l_len = *l_view as u32 as usize;
- let r_len = *r_view as u32 as usize;
- let l_bytes = unsafe { GenericByteViewArray::<T>::inline_value(l_view, l_len) };
- let r_bytes = unsafe { GenericByteViewArray::<T>::inline_value(r_view, r_len) };
- return l_bytes.cmp(r_bytes);
+ // Directly load the 16-byte view as an u128 (little-endian)
+ let l_bits: u128 = unsafe { *left.views().get_unchecked(left_idx) };
+ let r_bits: u128 = unsafe { *right.views().get_unchecked(right_idx) };
+
+ // The lower 32 bits encode the length (little-endian),
+ // the upper 96 bits hold the actual data
+ let l_len = l_bits as u32;
+ let r_len = r_bits as u32;
+
+ // Remove the length bits, leaving only the data
+ let l_data = l_bits >> 32;
+ let r_data = r_bits >> 32;
+
+ // The data is stored in little-endian order. To compare lexicographically,
+ // convert to big-endian:
+ let l_be = l_data.swap_bytes();
+ let r_be = r_data.swap_bytes();
+
+ // Compare only the first min_len bytes
+ let min_len = l_len.min(r_len);
+ // We have all 12 bytes in the high bits, but only want the top min_len
+ let shift = (12 - min_len) * 8;
+ let l_partial = l_be >> shift;
+ let r_partial = r_be >> shift;
+ if l_partial < r_partial {
Review Comment:
this can be written as `l_partial.cmp(r_partial).then_with(|| { l_len.cmp(&r_len) })`
--
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] Perf: Add prefix compare for inlined compare and change use of inline_value to inline it to a u128 [arrow-rs]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #7748:
URL: https://github.com/apache/arrow-rs/pull/7748#discussion_r2166493183
##########
arrow-array/src/array/byte_view_array.rs:
##########
@@ -537,17 +538,37 @@ impl<T: ByteViewType + ?Sized> GenericByteViewArray<T> {
left_idx: usize,
right: &GenericByteViewArray<T>,
right_idx: usize,
- ) -> std::cmp::Ordering {
+ ) -> Ordering {
let l_view = left.views().get_unchecked(left_idx);
let l_len = *l_view as u32;
let r_view = right.views().get_unchecked(right_idx);
let r_len = *r_view as u32;
if l_len <= 12 && r_len <= 12 {
- let l_data = unsafe { GenericByteViewArray::<T>::inline_value(l_view, l_len as usize) };
- let r_data = unsafe { GenericByteViewArray::<T>::inline_value(r_view, r_len as usize) };
- return l_data.cmp(r_data);
+ // Remove the length bits, leaving only the data
+ let l_data = *l_view >> 32;
+ let r_data = *r_view >> 32;
+
+ // The data is stored in little-endian order. To compare lexicographically,
+ // convert to big-endian:
+ let l_be = l_data.swap_bytes();
+ let r_be = r_data.swap_bytes();
+
+ // Compare only the first min_len bytes
+ let min_len = l_len.min(r_len);
+ // We have all 12 bytes in the high bits, but only want the top min_len
+ let shift = (12 - min_len) * 8;
+ let l_partial = l_be >> shift;
+ let r_partial = r_be >> shift;
+ if l_partial < r_partial {
+ return Ordering::Less;
+ } else if l_partial > r_partial {
+ return Ordering::Greater;
+ }
+
+ // If the prefixes are equal, the shorter one is considered smaller
+ return l_len.cmp(&r_len);
}
// one of the string is larger than 12 bytes,
Review Comment:
You can change this code below to use `(l_view >> 32) as u32` as well (or ByteView if it generates the same code). It seems that is a bit faster for the prefix comparison:
```
lt scalar StringViewArray
time: [34.533 ms 34.567 ms 34.601 ms]
change: [−11.030% −10.827% −10.620%] (p = 0.00 < 0.05)
Performance has improved.
Found 4 outliers among 100 measurements (4.00%)
```
--
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] Perf: Add prefix compare for inlined compare and change use of inline_value to inline it to a u128 [arrow-rs]
Posted by "jhorstmann (via GitHub)" <gi...@apache.org>.
jhorstmann commented on code in PR #7748:
URL: https://github.com/apache/arrow-rs/pull/7748#discussion_r2166381695
##########
arrow-array/src/array/byte_view_array.rs:
##########
@@ -537,17 +538,46 @@ impl<T: ByteViewType + ?Sized> GenericByteViewArray<T> {
left_idx: usize,
right: &GenericByteViewArray<T>,
right_idx: usize,
- ) -> std::cmp::Ordering {
+ ) -> Ordering {
let l_view = left.views().get_unchecked(left_idx);
let l_len = *l_view as u32;
let r_view = right.views().get_unchecked(right_idx);
let r_len = *r_view as u32;
if l_len <= 12 && r_len <= 12 {
- let l_data = unsafe { GenericByteViewArray::<T>::inline_value(l_view, l_len as usize) };
- let r_data = unsafe { GenericByteViewArray::<T>::inline_value(r_view, r_len as usize) };
- return l_data.cmp(r_data);
+ // Directly load the 16-byte view as an u128 (little-endian)
+ let l_bits: u128 = unsafe { *left.views().get_unchecked(left_idx) };
+ let r_bits: u128 = unsafe { *right.views().get_unchecked(right_idx) };
+
+ // The lower 32 bits encode the length (little-endian),
+ // the upper 96 bits hold the actual data
+ let l_len = l_bits as u32;
+ let r_len = r_bits as u32;
+
+ // Remove the length bits, leaving only the data
+ let l_data = l_bits >> 32;
+ let r_data = r_bits >> 32;
+
+ // The data is stored in little-endian order. To compare lexicographically,
+ // convert to big-endian:
+ let l_be = l_data.swap_bytes();
+ let r_be = r_data.swap_bytes();
+
+ // Compare only the first min_len bytes
+ let min_len = l_len.min(r_len);
+ // We have all 12 bytes in the high bits, but only want the top min_len
+ let shift = (12 - min_len) * 8;
+ let l_partial = l_be >> shift;
Review Comment:
It might be possible to OR the length back into the lower bits, which would then allow getting a result with a single u128 comparison. I think it would also be beneficial to extract this code block into a shared helper function, and add some unit tests for it. The generic code here might not be well convered by tests because of the fast path for inline buffers elsewhere.
--
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] Perf: Add prefix compare for inlined compare and change use of inline_value to inline it to a u128 [arrow-rs]
Posted by "zhuqi-lucas (via GitHub)" <gi...@apache.org>.
zhuqi-lucas commented on PR #7748:
URL: https://github.com/apache/arrow-rs/pull/7748#issuecomment-3004256549
> > lt StringViewArray StringViewArray inlined bytes 1.00 19.0±0.39ms ? ?/sec 2.53 48.1±1.10ms ? ?/sec
>
> Amazing 😎 !! Perhaps we can use some less manual bit masking/shifting while still producing roughly the same code?
Thank you @Dandandan for review, i polished the code, now the performance is even better:
```rust
lt StringViewArray StringViewArray inlined bytes 1.00 16.4±0.50ms ? ?/sec 2.98 48.7±0.71ms ? ?/sec
```
--
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] Perf: Add prefix compare for inlined compare and change use of inline_value to inline it to a u128 [arrow-rs]
Posted by "zhuqi-lucas (via GitHub)" <gi...@apache.org>.
zhuqi-lucas commented on PR #7748:
URL: https://github.com/apache/arrow-rs/pull/7748#issuecomment-3015077130
The integration CI seems flaky recently, i am not sure why.
--
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] Perf: Change use of inline_value to inline it to a u128 [arrow-rs]
Posted by "zhuqi-lucas (via GitHub)" <gi...@apache.org>.
zhuqi-lucas commented on PR #7748:
URL: https://github.com/apache/arrow-rs/pull/7748#issuecomment-2996781652
Note:
I still don't change the 4 bytes inline compare, because if one is < 4 bytes, because this case we still need to get the prefix for both, it will not benefit a lot since we will at most has 4 bytes to compare for this inline compare.
--
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] Perf: Add prefix compare for inlined compare and change use of inline_value to inline it to a u128 [arrow-rs]
Posted by "zhuqi-lucas (via GitHub)" <gi...@apache.org>.
zhuqi-lucas commented on code in PR #7748:
URL: https://github.com/apache/arrow-rs/pull/7748#discussion_r2166540945
##########
arrow-array/src/array/byte_view_array.rs:
##########
@@ -537,17 +538,37 @@ impl<T: ByteViewType + ?Sized> GenericByteViewArray<T> {
left_idx: usize,
right: &GenericByteViewArray<T>,
right_idx: usize,
- ) -> std::cmp::Ordering {
+ ) -> Ordering {
let l_view = left.views().get_unchecked(left_idx);
let l_len = *l_view as u32;
let r_view = right.views().get_unchecked(right_idx);
let r_len = *r_view as u32;
if l_len <= 12 && r_len <= 12 {
- let l_data = unsafe { GenericByteViewArray::<T>::inline_value(l_view, l_len as usize) };
- let r_data = unsafe { GenericByteViewArray::<T>::inline_value(r_view, r_len as usize) };
- return l_data.cmp(r_data);
+ // Remove the length bits, leaving only the data
+ let l_data = *l_view >> 32;
+ let r_data = *r_view >> 32;
+
+ // The data is stored in little-endian order. To compare lexicographically,
+ // convert to big-endian:
+ let l_be = l_data.swap_bytes();
+ let r_be = r_data.swap_bytes();
+
+ // Compare only the first min_len bytes
+ let min_len = l_len.min(r_len);
+ // We have all 12 bytes in the high bits, but only want the top min_len
+ let shift = (12 - min_len) * 8;
+ let l_partial = l_be >> shift;
+ let r_partial = r_be >> shift;
+ if l_partial < r_partial {
+ return Ordering::Less;
+ } else if l_partial > r_partial {
+ return Ordering::Greater;
+ }
+
+ // If the prefixes are equal, the shorter one is considered smaller
+ return l_len.cmp(&r_len);
}
// one of the string is larger than 12 bytes,
Review Comment:
Good point @Dandandan , i will change to ByteView prefix.
--
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] Perf: Add prefix compare for inlined compare and change use of inline_value to inline it to a u128 [arrow-rs]
Posted by "zhuqi-lucas (via GitHub)" <gi...@apache.org>.
zhuqi-lucas commented on code in PR #7748:
URL: https://github.com/apache/arrow-rs/pull/7748#discussion_r2166362006
##########
arrow-array/src/array/byte_view_array.rs:
##########
@@ -545,9 +545,41 @@ impl<T: ByteViewType + ?Sized> GenericByteViewArray<T> {
let r_len = *r_view as u32;
if l_len <= 12 && r_len <= 12 {
- let l_data = unsafe { GenericByteViewArray::<T>::inline_value(l_view, l_len as usize) };
- let r_data = unsafe { GenericByteViewArray::<T>::inline_value(r_view, r_len as usize) };
- return l_data.cmp(r_data);
+ // Directly load the 16-byte view as an u128 (little-endian)
+ let l_bits: u128 = *l_view;
+ let r_bits: u128 = *r_view;
+
+ // The lower 32 bits encode the length (little-endian),
+ // the upper 96 bits hold the actual data
+ let l_len = (l_bits as u32) as usize;
+ let r_len = (r_bits as u32) as usize;
+
+ // Mask to keep only the upper 96 bits (data), zeroing out the length
+ // 0xFFFF_FFFF_0000_0000_..._0000
+ const DATA_MASK: u128 = !0u128 << 32;
+
+ // Remove the length bits, leaving only the data
+ let l_data = (l_bits & DATA_MASK) >> 32;
Review Comment:
Thank you @Dandandan , reduce the bit masking in latest PR, i think ByteView from will use all convert to the struct field, we only use part of them, so i just use part of logic in latest PR.
```rust
impl From<u128> for ByteView {
#[inline]
fn from(value: u128) -> Self {
Self {
length: value as u32,
prefix: (value >> 32) as u32,
buffer_index: (value >> 64) as u32,
offset: (value >> 96) as u32,
}
}
}
```
--
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] Perf: Add prefix compare for inlined compare and change use of inline_value to inline it to a u128 [arrow-rs]
Posted by "zhuqi-lucas (via GitHub)" <gi...@apache.org>.
zhuqi-lucas commented on code in PR #7748:
URL: https://github.com/apache/arrow-rs/pull/7748#discussion_r2166453844
##########
arrow-array/src/array/byte_view_array.rs:
##########
@@ -545,9 +545,41 @@ impl<T: ByteViewType + ?Sized> GenericByteViewArray<T> {
let r_len = *r_view as u32;
if l_len <= 12 && r_len <= 12 {
- let l_data = unsafe { GenericByteViewArray::<T>::inline_value(l_view, l_len as usize) };
- let r_data = unsafe { GenericByteViewArray::<T>::inline_value(r_view, r_len as usize) };
- return l_data.cmp(r_data);
+ // Directly load the 16-byte view as an u128 (little-endian)
+ let l_bits: u128 = *l_view;
+ let r_bits: u128 = *r_view;
+
+ // The lower 32 bits encode the length (little-endian),
+ // the upper 96 bits hold the actual data
+ let l_len = (l_bits as u32) as usize;
+ let r_len = (r_bits as u32) as usize;
+
+ // Mask to keep only the upper 96 bits (data), zeroing out the length
+ // 0xFFFF_FFFF_0000_0000_..._0000
+ const DATA_MASK: u128 = !0u128 << 32;
+
+ // Remove the length bits, leaving only the data
+ let l_data = (l_bits & DATA_MASK) >> 32;
Review Comment:
Interesting @Dandandan , let me try using ByteView and compare performance!
--
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