YUZHEthefool commented on code in PR #10605:
URL: https://github.com/apache/arrow-rs/pull/10605#discussion_r3892243867
##########
arrow-ord/src/rank.rs:
##########
@@ -106,16 +106,230 @@ fn byte_view_rank<T: ByteViewType>(
array: &GenericByteViewArray<T>,
options: SortOptions,
) -> Vec<u32> {
- let to_sort: Vec<(&[u8], u32)> = match array.nulls().filter(|n|
n.null_count() > 0) {
+ // An inline view already contains the complete value. Convert it once to
+ // a key whose integer ordering matches the byte ordering, as is done by
+ // `sort_byte_view`.
+ if array.data_buffers().is_empty() {
+ let to_sort: Vec<(u128, u32)> = match array.nulls().filter(|n|
n.null_count() > 0) {
+ Some(n) => n
+ .valid_indices()
+ .map(|idx| {
+ // SAFETY: `valid_indices` only yields indices in the
array.
+ let raw = unsafe { *array.views().get_unchecked(idx) };
+ (GenericByteViewArray::<T>::inline_key_fast(raw), idx as
u32)
+ })
+ .collect(),
+ None => array
+ .views()
+ .iter()
+ .enumerate()
+ .map(|(idx, raw)|
(GenericByteViewArray::<T>::inline_key_fast(*raw), idx as u32))
+ .collect(),
+ };
+ return rank_impl(
+ array.len(),
+ to_sort,
+ options,
+ |a, b| a.cmp(&b),
+ |a, b| a == b,
+ );
+ }
+
+ if has_high_byte_view_key_collision_rate(array) {
+ let to_sort: Vec<(&[u8], u32)> = match array.nulls().filter(|n|
n.null_count() > 0) {
+ Some(n) => n
+ .valid_indices()
+ .map(|idx| (array.value(idx).as_ref(), idx as u32))
+ .collect(),
+ None => (0..array.len())
+ .map(|idx| (array.value(idx).as_ref(), idx as u32))
+ .collect(),
+ };
+ return rank_impl(array.len(), to_sort, options, Ord::cmp,
PartialEq::eq);
+ }
+
+ // Cache a wider prefix than the 4 bytes stored in a non-inline view. This
+ // pays for the backing-buffer access once per value instead of once per
+ // comparison, and only resolves the complete value when two keys collide.
+ let to_sort: Vec<(u128, u32)> = match array.nulls().filter(|n|
n.null_count() > 0) {
Some(n) => n
.valid_indices()
- .map(|idx| (array.value(idx).as_ref(), idx as u32))
+ .map(|idx| {
+ // SAFETY: `valid_indices` only yields indices in the array.
+ let value: &[u8] = unsafe {
array.value_unchecked(idx).as_ref() };
+ (byte_view_key(value), idx as u32)
+ })
.collect(),
None => (0..array.len())
- .map(|idx| (array.value(idx).as_ref(), idx as u32))
+ .map(|idx| {
+ // SAFETY: `idx` is in `0..array.len()`.
+ let value: &[u8] = unsafe {
array.value_unchecked(idx).as_ref() };
+ (byte_view_key(value), idx as u32)
+ })
.collect(),
};
- rank_impl(array.len(), to_sort, options, Ord::cmp, PartialEq::eq)
+ rank_impl_by(
+ array.len(),
+ to_sort,
+ options,
+ |a, b| compare_view_key(array, a, b),
+ |a, b| equal_view_key(array, a, b),
+ )
+}
+
+const BYTE_VIEW_KEY_LEN: usize = 16;
+const BYTE_VIEW_KEY_SAMPLES_PER_WINDOW: usize = 4;
+const BYTE_VIEW_KEY_SAMPLE_SIZE: usize = 8;
+const BYTE_VIEW_KEY_MAX_PROBES_PER_WINDOW: usize = 32;
+const BYTE_VIEW_KEY_FALLBACK_COLLISION_RATIO: usize = 3;
+
+fn has_high_byte_view_key_collision_rate<T: ByteViewType>(array:
&GenericByteViewArray<T>) -> bool {
+ if array.len() < 2 {
Review Comment:
I'll find some time to do it later.
done.
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
