zhuqi-lucas commented on code in PR #7860:
URL: https://github.com/apache/arrow-rs/pull/7860#discussion_r2184245205
##########
arrow-ord/src/sort.rs:
##########
@@ -295,12 +295,89 @@ fn sort_bytes<T: ByteArrayType>(
options: SortOptions,
limit: Option<usize>,
) -> UInt32Array {
- let mut valids = value_indices
+ // 1. construct a list of (index, raw_bytes, length)
+ let mut valids: Vec<(u32, &[u8], usize)> = value_indices
.into_iter()
- .map(|index| (index, values.value(index as usize).as_ref()))
- .collect::<Vec<(u32, &[u8])>>();
+ .map(|idx| {
+ let slice: &[u8] = values.value(idx as usize).as_ref();
+ (idx, slice, slice.len())
+ })
+ .collect();
- sort_impl(options, &mut valids, &nulls, limit, Ord::cmp).into()
+ // 2. compute the number of non-null entries to partially sort
+ let vlimit = match (limit, options.nulls_first) {
+ (Some(l), true) => l.saturating_sub(nulls.len()).min(valids.len()),
+ _ => valids.len(),
+ };
+
+ // 3. comparator function for mixed byte views
+ let cmp_bytes = |a: &(u32, &[u8], usize), b: &(u32, &[u8], usize)| {
+ let (_, a_bytes, a_len) = *a;
+ let (_, b_bytes, b_len) = *b;
+ let min_len = a_len.min(b_len);
+
+ // 3. compare the prefix of the first 4 bytes
+ let pref = min_len.min(4);
+ let mut pa = 0u32;
+ let mut pb = 0u32;
+ for i in 0..pref {
+ pa = (pa << 8) | (a_bytes[i] as u32);
+ pb = (pb << 8) | (b_bytes[i] as u32);
+ }
+ if pa != pb {
+ return pa.cmp(&pb);
+ }
+
+ // 3.2 Use 8 bytes to compare one by one if the prefix is equal
+ let mut i = pref;
+ while i + 8 <= min_len {
+ let raw_a = unsafe {
std::ptr::read_unaligned(a_bytes.as_ptr().add(i) as *const u64) };
Review Comment:
Thank you @alamb for this good point, i will try to only keep one prefix
compare and testing the result, the 8 byte boundary following should not
improve too much and it's not clear for 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-unsubscr...@arrow.apache.org
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
