Dandandan commented on code in PR #7860:
URL: https://github.com/apache/arrow-rs/pull/7860#discussion_r2183266280
##########
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
Review Comment:
What is the performance without this non-prefix fallback @zhuqi-lucas ?
--
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
