use std::sync::atomic::{AtomicU64, Ordering};
use rayon::prelude::*;
pub type IndexRanges = Vec<(u64, u64)>;
pub type OrderedIndexRanges = (Vec<u64>, IndexRanges);
const NULL_TIMESTAMP: i64 = i64::MIN;
const PARALLEL_GROUP_LEN: usize = 1 << 16;
const INSERTION_SORT_LEN: usize = 24;
const MAX_GROUPS_TO_ORDER_BY_LENGTH: usize = 1 << 13;
const SCATTER_HISTOGRAM_BUDGET: usize = 64 << 20;
const MIN_SCATTER_CHUNK: usize = 1 << 14;
const CANDIDATE_DIVISORS: [i64; 4] = [1_000_000_000, 1_000_000, 1_000, 1];
pub fn split_ordered_index_ranges((indices, ranges): OrderedIndexRanges) -> (Vec<u64>, Vec<u64>) {
(indices, ranges.into_iter().map(|(_, end)| end).collect())
}
pub fn run_boundaries<T: PartialEq + Sync>(values: &[T]) -> (Vec<u64>, Vec<u64>) {
let n = values.len();
if n == 0 {
return (Vec::new(), Vec::new());
}
let boundaries: Vec<u64> = values
.par_windows(2)
.enumerate()
.filter_map(|(idx, window)| (window[0] != window[1]).then_some((idx + 1) as u64))
.collect();
let mut starts = Vec::with_capacity(boundaries.len() + 1);
starts.push(0);
starts.extend_from_slice(&boundaries);
let mut ends = boundaries;
ends.push(n as u64);
(starts, ends)
}
pub fn presorted_ranges_for_u32_codes(codes: &[u32]) -> (Vec<u64>, Vec<u64>) {
run_boundaries(codes)
}
const VALIDATE_SEQUENTIAL_BELOW: usize = 1 << 15;
const VALIDATE_MIN_CHUNK: usize = 1 << 13;
const VALIDATE_CHUNKS_PER_THREAD: usize = 16;
#[inline]
fn validate_chunk_bounds(n: usize, chunk: usize, index: usize) -> (usize, usize) {
((index * chunk).max(1), ((index + 1) * chunk).min(n))
}
pub fn validate_non_decreasing_timestamps(timestamps: &[i64]) -> bool {
let n = timestamps.len();
if n < 2 {
return true;
}
if n < VALIDATE_SEQUENTIAL_BELOW {
return non_decreasing(timestamps, 1, n);
}
let threads = rayon::current_num_threads().max(1);
let chunk = (n / (threads * VALIDATE_CHUNKS_PER_THREAD).max(1)).max(VALIDATE_MIN_CHUNK);
(0..n.div_ceil(chunk)).into_par_iter().all(|index| {
let (from, to) = validate_chunk_bounds(n, chunk, index);
non_decreasing(timestamps, from, to)
})
}
pub fn validate_non_decreasing_within_ends(timestamps: &[i64], ends: &[u64]) -> bool {
let n = timestamps.len();
if ends.last().is_some_and(|&last| last as usize > n) {
return false;
}
ends.par_iter().enumerate().all(|(position, &end)| {
let start = if position == 0 {
0
} else {
ends[position - 1] as usize
};
let end = end as usize;
start >= end || non_decreasing(timestamps, start + 1, end)
})
}
#[inline]
fn non_decreasing(timestamps: &[i64], from: usize, to: usize) -> bool {
if from >= to {
return true;
}
let (previous, next) = (×tamps[from - 1..to - 1], ×tamps[from..to]);
let mut bad = 0u8;
for (&a, &b) in previous.iter().zip(next) {
bad |= (b < a) as u8;
}
bad == 0
}
#[derive(Clone, Copy, Debug)]
struct TimeRange {
min: i64,
max: i64,
has_null: bool,
}
impl TimeRange {
fn empty() -> Self {
Self {
min: i64::MAX,
max: i64::MIN,
has_null: false,
}
}
fn merge(self, other: Self) -> Self {
Self {
min: self.min.min(other.min),
max: self.max.max(other.max),
has_null: self.has_null || other.has_null,
}
}
fn is_empty(&self) -> bool {
self.min > self.max
}
}
fn scan_time_range(timestamps: &[i64]) -> TimeRange {
timestamps
.par_chunks(1 << 14)
.map(|chunk| {
let mut range = TimeRange::empty();
for &value in chunk {
let is_null = value == NULL_TIMESTAMP;
range.has_null |= is_null;
let for_min = if is_null { i64::MAX } else { value };
range.min = range.min.min(for_min);
range.max = range.max.max(value);
}
range
})
.reduce(TimeRange::empty, TimeRange::merge)
}
fn all_divisible_by(timestamps: &[i64], divisor: i64) -> bool {
timestamps.par_chunks(1 << 14).all(|chunk| {
chunk
.iter()
.all(|&value| value == NULL_TIMESTAMP || value % divisor == 0)
})
}
#[derive(Clone, Copy, Debug)]
struct TimeKeyPlan {
base: i64,
idx_bits: u32,
null_offset: u64,
}
impl TimeKeyPlan {
#[inline(always)]
fn pack<const DIVISOR: u64>(&self, timestamp: i64, row: usize) -> u64 {
let offset = if timestamp == NULL_TIMESTAMP {
0
} else {
timestamp.wrapping_sub(self.base) as u64 / DIVISOR + self.null_offset
};
(offset << self.idx_bits) | row as u64
}
}
fn index_bits(n: usize) -> u32 {
u64::BITS - (n as u64).saturating_sub(1).leading_zeros()
}
fn plan_time_keys(timestamps: &[i64], n: usize) -> Option<(TimeKeyPlan, u64)> {
let idx_bits = index_bits(n);
if idx_bits >= u64::BITS {
return None;
}
let offset_limit = 1u64.checked_shl(u64::BITS - idx_bits).unwrap_or(u64::MAX);
let range = scan_time_range(timestamps);
if range.is_empty() {
return Some((
TimeKeyPlan {
base: 0,
idx_bits,
null_offset: 0,
},
1,
));
}
let null_offset = u64::from(range.has_null);
let span = (range.max as i128 - range.min as i128) as u64;
for &divisor in &CANDIDATE_DIVISORS {
if (span / divisor as u64) + null_offset >= offset_limit {
continue;
}
if divisor == 1 || all_divisible_by(timestamps, divisor) {
return Some((
TimeKeyPlan {
base: range.min,
idx_bits,
null_offset,
},
divisor as u64,
));
}
}
None
}
macro_rules! with_divisor {
($divisor:expr, |$name:ident| $body:expr) => {
match $divisor {
1_000_000_000 => {
const $name: u64 = 1_000_000_000;
$body
}
1_000_000 => {
const $name: u64 = 1_000_000;
$body
}
1_000 => {
const $name: u64 = 1_000;
$body
}
_ => {
const $name: u64 = 1;
$body
}
}
};
}
fn zeroed_atomic_u64(len: usize) -> Vec<AtomicU64> {
let zeros = vec![0u64; len];
let (pointer, length, capacity) = {
let mut zeros = std::mem::ManuallyDrop::new(zeros);
(zeros.as_mut_ptr(), zeros.len(), zeros.capacity())
};
unsafe { Vec::from_raw_parts(pointer.cast::<AtomicU64>(), length, capacity) }
}
fn atomics_into_u64(values: Vec<AtomicU64>) -> Vec<u64> {
let (pointer, length, capacity) = {
let mut values = std::mem::ManuallyDrop::new(values);
(values.as_mut_ptr(), values.len(), values.capacity())
};
unsafe { Vec::from_raw_parts(pointer.cast::<u64>(), length, capacity) }
}
fn scatter_chunk_len(n: usize, num_groups: usize) -> usize {
let threads = rayon::current_num_threads().max(1);
let by_budget = (SCATTER_HISTOGRAM_BUDGET / (num_groups.max(1) * size_of::<u32>())).max(1);
let by_bookkeeping = (n / num_groups.max(1)).max(1);
let chunks = threads.min(by_budget).min(by_bookkeeping).max(1);
n.div_ceil(chunks).max(MIN_SCATTER_CHUNK)
}
fn scatter_by_group<F>(
codes: &[u32],
num_groups: usize,
value_at: F,
) -> Result<(Vec<u64>, IndexRanges), String>
where
F: Fn(usize) -> u64 + Sync,
{
let n = codes.len();
if let Some(&highest) = codes.par_iter().max()
&& highest as usize >= num_groups
{
return Err("uid code must be less than num_groups".to_string());
}
let chunk_len = scatter_chunk_len(n, num_groups);
let mut histograms: Vec<Vec<u32>> = codes
.par_chunks(chunk_len)
.map(|chunk| {
let mut counts = vec![0u32; num_groups];
for &code in chunk {
counts[code as usize] += 1;
}
counts
})
.collect();
let mut running = vec![0u32; num_groups];
for counts in histograms.iter_mut() {
for (group, count) in counts.iter_mut().enumerate() {
let offset = running[group];
running[group] = offset + *count;
*count = offset;
}
}
let mut ranges = Vec::with_capacity(num_groups);
let mut starts = vec![0u32; num_groups];
let mut current = 0u32;
for (group, &total) in running.iter().enumerate() {
starts[group] = current;
if total != 0 {
ranges.push((current as u64, (current + total) as u64));
current += total;
}
}
for counts in histograms.iter_mut() {
for (group, cursor) in counts.iter_mut().enumerate() {
*cursor += starts[group];
}
}
let slots = zeroed_atomic_u64(n);
codes
.par_chunks(chunk_len)
.zip(histograms.par_iter_mut())
.enumerate()
.for_each(|(chunk_index, (chunk, cursors))| {
let base = chunk_index * chunk_len;
for (offset, &code) in chunk.iter().enumerate() {
let row = base + offset;
let cursor = &mut cursors[code as usize];
slots[*cursor as usize].store(value_at(row), Ordering::Relaxed);
*cursor += 1;
}
});
Ok((atomics_into_u64(slots), ranges))
}
fn split_groups<'a>(buf: &'a mut [u64], ranges: &[(u64, u64)]) -> Vec<&'a mut [u64]> {
let mut groups = Vec::with_capacity(ranges.len());
let mut rest = buf;
let mut consumed = 0u64;
for &(start, end) in ranges {
let tail = std::mem::take(&mut rest);
let (_, tail) = tail.split_at_mut((start - consumed) as usize);
let (group, tail) = tail.split_at_mut((end - start) as usize);
groups.push(group);
rest = tail;
consumed = end;
}
groups
}
fn sort_group_packed(group: &mut [u64], _solo: bool) {
if group.len() <= 1 || group.is_sorted() {
return;
}
if group.len() <= INSERTION_SORT_LEN {
for position in 1..group.len() {
let value = group[position];
let mut hole = position;
while hole > 0 && group[hole - 1] > value {
group[hole] = group[hole - 1];
hole -= 1;
}
group[hole] = value;
}
} else if group.len() >= PARALLEL_GROUP_LEN {
group.par_sort_unstable();
} else {
group.sort_unstable();
}
}
fn sort_group_indirect(group: &mut [u64], timestamps: &[i64], solo: bool) {
let compare = |&left: &u64, &right: &u64| {
timestamps[left as usize]
.cmp(×tamps[right as usize])
.then(left.cmp(&right))
};
if group.len() <= 1 {
return;
}
if group.len() < PARALLEL_GROUP_LEN {
group.sort_unstable_by(compare);
} else if solo {
group.par_sort_by(compare);
} else {
group.par_sort_unstable_by(compare);
}
}
fn sort_all_groups<F>(buf: &mut [u64], ranges: &[(u64, u64)], sort_one: F)
where
F: Fn(&mut [u64], bool) + Sync + Send,
{
let mut groups = split_groups(buf, ranges);
let solo = groups.len() == 1;
if groups.len() <= MAX_GROUPS_TO_ORDER_BY_LENGTH {
groups.sort_unstable_by_key(|group| std::cmp::Reverse(group.len()));
}
groups
.par_iter_mut()
.for_each(|group| sort_one(group, solo));
}
fn unpack_rows(keys: &mut [u64], idx_bits: u32) {
if idx_bits >= u64::BITS {
return;
}
let mask = (1u64 << idx_bits) - 1;
keys.par_iter_mut().for_each(|key| *key &= mask);
}
pub fn time_ordered_indices_single_user(timestamps: &[i64]) -> OrderedIndexRanges {
let n = timestamps.len();
if n == 0 {
return (Vec::new(), Vec::new());
}
let ranges = vec![(0u64, n as u64)];
if let Some((plan, divisor)) = plan_time_keys(timestamps, n) {
let mut keys: Vec<u64> = with_divisor!(divisor, |DIVISOR| timestamps
.par_iter()
.enumerate()
.map(|(row, ×tamp)| plan.pack::<DIVISOR>(timestamp, row))
.collect());
sort_all_groups(&mut keys, &ranges, sort_group_packed);
unpack_rows(&mut keys, plan.idx_bits);
return (keys, ranges);
}
let mut indices: Vec<u64> = (0..n as u64).collect();
sort_all_groups(&mut indices, &ranges, |group, solo| {
sort_group_indirect(group, timestamps, solo)
});
(indices, ranges)
}
pub fn time_ordered_indices_for_u32_codes(
codes: &[u32],
timestamps: &[i64],
num_groups: usize,
) -> Result<OrderedIndexRanges, String> {
let n = codes.len();
if n == 0 {
return Ok((Vec::new(), Vec::new()));
}
if timestamps.len() != n {
return Err(format!(
"uid codes and timestamps must have the same length (got {n} and {})",
timestamps.len()
));
}
if num_groups == 0 {
return Err(
"num_groups must be greater than zero when uid codes are not empty".to_string(),
);
}
match plan_time_keys(timestamps, n) {
Some((plan, divisor)) => {
let (mut keys, ranges) = with_divisor!(divisor, |DIVISOR| scatter_by_group(
codes,
num_groups,
|row| plan.pack::<DIVISOR>(timestamps[row], row)
))?;
sort_all_groups(&mut keys, &ranges, sort_group_packed);
unpack_rows(&mut keys, plan.idx_bits);
Ok((keys, ranges))
}
None => {
let (mut indices, ranges) = scatter_by_group(codes, num_groups, |row| row as u64)?;
sort_all_groups(&mut indices, &ranges, |group, solo| {
sort_group_indirect(group, timestamps, solo)
});
Ok((indices, ranges))
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn finds_the_boundaries_of_every_equal_run() {
assert_eq!(run_boundaries::<u32>(&[]), (vec![], vec![]));
assert_eq!(run_boundaries(&[7u32]), (vec![0], vec![1]));
assert_eq!(
run_boundaries(&[5u32, 5, 9, 9, 9, 1]),
(vec![0, 2, 5], vec![2, 5, 6])
);
assert_eq!(
run_boundaries(&[1u32, 2, 1]),
(vec![0, 1, 2], vec![1, 2, 3])
);
assert_eq!(
run_boundaries(&[1u32, 2, 3]),
(vec![0, 1, 2], vec![1, 2, 3])
);
assert_eq!(run_boundaries(&[4u32, 4, 4]), (vec![0], vec![3]));
}
#[test]
fn run_boundaries_partition_the_input_exactly() {
let values: Vec<u32> = (0..300_000u32).map(|row| row / (row % 7 + 1)).collect();
let (starts, ends) = run_boundaries(&values);
assert_eq!(starts.len(), ends.len());
assert_eq!(starts[0], 0);
assert_eq!(*ends.last().unwrap(), values.len() as u64);
for (position, (&start, &end)) in starts.iter().zip(&ends).enumerate() {
assert!(start < end);
if position > 0 {
assert_eq!(start, ends[position - 1]);
assert_ne!(values[start as usize], values[start as usize - 1]);
}
let run = &values[start as usize..end as usize];
assert!(run.iter().all(|value| *value == run[0]));
}
}
#[test]
fn validates_timestamps_against_supplied_run_ends() {
assert!(validate_non_decreasing_within_ends(&[1, 2, 0, 5], &[2, 4]));
assert!(!validate_non_decreasing_within_ends(&[1, 2, 0, 5], &[4]));
assert!(validate_non_decreasing_within_ends(&[], &[]));
assert!(!validate_non_decreasing_within_ends(&[1, 2], &[5]));
}
#[test]
fn validates_single_group_timestamps() {
assert!(validate_non_decreasing_timestamps(&[]));
assert!(validate_non_decreasing_timestamps(&[3]));
assert!(validate_non_decreasing_timestamps(&[1, 1, 2, 9]));
assert!(!validate_non_decreasing_timestamps(&[1, 0]));
let mut rising: Vec<i64> = (0..(VALIDATE_SEQUENTIAL_BELOW as i64 * 4)).collect();
assert!(validate_non_decreasing_timestamps(&rising));
for at in [1usize, VALIDATE_MIN_CHUNK, rising.len() - 1] {
let saved = rising[at];
rising[at] = -1;
assert!(
!validate_non_decreasing_timestamps(&rising),
"break at {at}"
);
rising[at] = saved;
}
}
}