| 1 |
//! Parallel merge sort. |
| 2 |
//! |
| 3 |
//! This implementation is copied verbatim from `std::slice::sort` and then parallelized. |
| 4 |
//! The only difference from the original is that the sequential `mergesort` returns |
| 5 |
//! `MergesortResult` and leaves descending arrays intact. |
| 6 |
|
| 7 |
use crate::iter::*; |
| 8 |
use crate::slice::ParallelSliceMut; |
| 9 |
use crate::SendPtr; |
| 10 |
use std::mem; |
| 11 |
use std::mem::size_of; |
| 12 |
use std::ptr; |
| 13 |
use std::slice; |
| 14 |
|
| 15 |
unsafe fn get_and_increment<T>(ptr: &mut *mut T) -> *mut T { |
| 16 |
let old = *ptr; |
| 17 |
*ptr = ptr.offset(1); |
| 18 |
old |
| 19 |
} |
| 20 |
|
| 21 |
unsafe fn decrement_and_get<T>(ptr: &mut *mut T) -> *mut T { |
| 22 |
*ptr = ptr.offset(-1); |
| 23 |
*ptr |
| 24 |
} |
| 25 |
|
| 26 |
/// When dropped, copies from `src` into `dest` a sequence of length `len`. |
| 27 |
struct CopyOnDrop<T> { |
| 28 |
src: *const T, |
| 29 |
dest: *mut T, |
| 30 |
len: usize, |
| 31 |
} |
| 32 |
|
| 33 |
impl<T> Drop for CopyOnDrop<T> { |
| 34 |
fn drop(&mut self) { |
| 35 |
unsafe { |
| 36 |
ptr::copy_nonoverlapping(self.src, self.dest, self.len); |
| 37 |
} |
| 38 |
} |
| 39 |
} |
| 40 |
|
| 41 |
/// Inserts `v[0]` into pre-sorted sequence `v[1..]` so that whole `v[..]` becomes sorted. |
| 42 |
/// |
| 43 |
/// This is the integral subroutine of insertion sort. |
| 44 |
fn insert_head<T, F>(v: &mut [T], is_less: &F) |
| 45 |
where |
| 46 |
F: Fn(&T, &T) -> bool, |
| 47 |
{ |
| 48 |
if v.len() >= 2 && is_less(&v[1], &v[0]) { |
| 49 |
unsafe { |
| 50 |
// There are three ways to implement insertion here: |
| 51 |
// |
| 52 |
// 1. Swap adjacent elements until the first one gets to its final destination. |
| 53 |
// However, this way we copy data around more than is necessary. If elements are big |
| 54 |
// structures (costly to copy), this method will be slow. |
| 55 |
// |
| 56 |
// 2. Iterate until the right place for the first element is found. Then shift the |
| 57 |
// elements succeeding it to make room for it and finally place it into the |
| 58 |
// remaining hole. This is a good method. |
| 59 |
// |
| 60 |
// 3. Copy the first element into a temporary variable. Iterate until the right place |
| 61 |
// for it is found. As we go along, copy every traversed element into the slot |
| 62 |
// preceding it. Finally, copy data from the temporary variable into the remaining |
| 63 |
// hole. This method is very good. Benchmarks demonstrated slightly better |
| 64 |
// performance than with the 2nd method. |
| 65 |
// |
| 66 |
// All methods were benchmarked, and the 3rd showed best results. So we chose that one. |
| 67 |
let tmp = mem::ManuallyDrop::new(ptr::read(&v[0])); |
| 68 |
|
| 69 |
// Intermediate state of the insertion process is always tracked by `hole`, which |
| 70 |
// serves two purposes: |
| 71 |
// 1. Protects integrity of `v` from panics in `is_less`. |
| 72 |
// 2. Fills the remaining hole in `v` in the end. |
| 73 |
// |
| 74 |
// Panic safety: |
| 75 |
// |
| 76 |
// If `is_less` panics at any point during the process, `hole` will get dropped and |
| 77 |
// fill the hole in `v` with `tmp`, thus ensuring that `v` still holds every object it |
| 78 |
// initially held exactly once. |
| 79 |
let mut hole = InsertionHole { |
| 80 |
src: &*tmp, |
| 81 |
dest: &mut v[1], |
| 82 |
}; |
| 83 |
ptr::copy_nonoverlapping(&v[1], &mut v[0], 1); |
| 84 |
|
| 85 |
for i in 2..v.len() { |
| 86 |
if !is_less(&v[i], &*tmp) { |
| 87 |
break; |
| 88 |
} |
| 89 |
ptr::copy_nonoverlapping(&v[i], &mut v[i - 1], 1); |
| 90 |
hole.dest = &mut v[i]; |
| 91 |
} |
| 92 |
// `hole` gets dropped and thus copies `tmp` into the remaining hole in `v`. |
| 93 |
} |
| 94 |
} |
| 95 |
|
| 96 |
// When dropped, copies from `src` into `dest`. |
| 97 |
struct InsertionHole<T> { |
| 98 |
src: *const T, |
| 99 |
dest: *mut T, |
| 100 |
} |
| 101 |
|
| 102 |
impl<T> Drop for InsertionHole<T> { |
| 103 |
fn drop(&mut self) { |
| 104 |
unsafe { |
| 105 |
ptr::copy_nonoverlapping(self.src, self.dest, 1); |
| 106 |
} |
| 107 |
} |
| 108 |
} |
| 109 |
} |
| 110 |
|
| 111 |
/// Merges non-decreasing runs `v[..mid]` and `v[mid..]` using `buf` as temporary storage, and |
| 112 |
/// stores the result into `v[..]`. |
| 113 |
/// |
| 114 |
/// # Safety |
| 115 |
/// |
| 116 |
/// The two slices must be non-empty and `mid` must be in bounds. Buffer `buf` must be long enough |
| 117 |
/// to hold a copy of the shorter slice. Also, `T` must not be a zero-sized type. |
| 118 |
unsafe fn merge<T, F>(v: &mut [T], mid: usize, buf: *mut T, is_less: &F) |
| 119 |
where |
| 120 |
F: Fn(&T, &T) -> bool, |
| 121 |
{ |
| 122 |
let len = v.len(); |
| 123 |
let v = v.as_mut_ptr(); |
| 124 |
let v_mid = v.add(mid); |
| 125 |
let v_end = v.add(len); |
| 126 |
|
| 127 |
// The merge process first copies the shorter run into `buf`. Then it traces the newly copied |
| 128 |
// run and the longer run forwards (or backwards), comparing their next unconsumed elements and |
| 129 |
// copying the lesser (or greater) one into `v`. |
| 130 |
// |
| 131 |
// As soon as the shorter run is fully consumed, the process is done. If the longer run gets |
| 132 |
// consumed first, then we must copy whatever is left of the shorter run into the remaining |
| 133 |
// hole in `v`. |
| 134 |
// |
| 135 |
// Intermediate state of the process is always tracked by `hole`, which serves two purposes: |
| 136 |
// 1. Protects integrity of `v` from panics in `is_less`. |
| 137 |
// 2. Fills the remaining hole in `v` if the longer run gets consumed first. |
| 138 |
// |
| 139 |
// Panic safety: |
| 140 |
// |
| 141 |
// If `is_less` panics at any point during the process, `hole` will get dropped and fill the |
| 142 |
// hole in `v` with the unconsumed range in `buf`, thus ensuring that `v` still holds every |
| 143 |
// object it initially held exactly once. |
| 144 |
let mut hole; |
| 145 |
|
| 146 |
if mid <= len - mid { |
| 147 |
// The left run is shorter. |
| 148 |
ptr::copy_nonoverlapping(v, buf, mid); |
| 149 |
hole = MergeHole { |
| 150 |
start: buf, |
| 151 |
end: buf.add(mid), |
| 152 |
dest: v, |
| 153 |
}; |
| 154 |
|
| 155 |
// Initially, these pointers point to the beginnings of their arrays. |
| 156 |
let left = &mut hole.start; |
| 157 |
let mut right = v_mid; |
| 158 |
let out = &mut hole.dest; |
| 159 |
|
| 160 |
while *left < hole.end && right < v_end { |
| 161 |
// Consume the lesser side. |
| 162 |
// If equal, prefer the left run to maintain stability. |
| 163 |
let to_copy = if is_less(&*right, &**left) { |
| 164 |
get_and_increment(&mut right) |
| 165 |
} else { |
| 166 |
get_and_increment(left) |
| 167 |
}; |
| 168 |
ptr::copy_nonoverlapping(to_copy, get_and_increment(out), 1); |
| 169 |
} |
| 170 |
} else { |
| 171 |
// The right run is shorter. |
| 172 |
ptr::copy_nonoverlapping(v_mid, buf, len - mid); |
| 173 |
hole = MergeHole { |
| 174 |
start: buf, |
| 175 |
end: buf.add(len - mid), |
| 176 |
dest: v_mid, |
| 177 |
}; |
| 178 |
|
| 179 |
// Initially, these pointers point past the ends of their arrays. |
| 180 |
let left = &mut hole.dest; |
| 181 |
let right = &mut hole.end; |
| 182 |
let mut out = v_end; |
| 183 |
|
| 184 |
while v < *left && buf < *right { |
| 185 |
// Consume the greater side. |
| 186 |
// If equal, prefer the right run to maintain stability. |
| 187 |
let to_copy = if is_less(&*right.offset(-1), &*left.offset(-1)) { |
| 188 |
decrement_and_get(left) |
| 189 |
} else { |
| 190 |
decrement_and_get(right) |
| 191 |
}; |
| 192 |
ptr::copy_nonoverlapping(to_copy, decrement_and_get(&mut out), 1); |
| 193 |
} |
| 194 |
} |
| 195 |
// Finally, `hole` gets dropped. If the shorter run was not fully consumed, whatever remains of |
| 196 |
// it will now be copied into the hole in `v`. |
| 197 |
|
| 198 |
// When dropped, copies the range `start..end` into `dest..`. |
| 199 |
struct MergeHole<T> { |
| 200 |
start: *mut T, |
| 201 |
end: *mut T, |
| 202 |
dest: *mut T, |
| 203 |
} |
| 204 |
|
| 205 |
impl<T> Drop for MergeHole<T> { |
| 206 |
fn drop(&mut self) { |
| 207 |
// `T` is not a zero-sized type, so it's okay to divide by its size. |
| 208 |
unsafe { |
| 209 |
let len = self.end.offset_from(self.start) as usize; |
| 210 |
ptr::copy_nonoverlapping(self.start, self.dest, len); |
| 211 |
} |
| 212 |
} |
| 213 |
} |
| 214 |
} |
| 215 |
|
| 216 |
/// The result of merge sort. |
| 217 |
#[must_use] |
| 218 |
#[derive(Clone, Copy, PartialEq, Eq)] |
| 219 |
enum MergesortResult { |
| 220 |
/// The slice has already been sorted. |
| 221 |
NonDescending, |
| 222 |
/// The slice has been descending and therefore it was left intact. |
| 223 |
Descending, |
| 224 |
/// The slice was sorted. |
| 225 |
Sorted, |
| 226 |
} |
| 227 |
|
| 228 |
/// A sorted run that starts at index `start` and is of length `len`. |
| 229 |
#[derive(Clone, Copy)] |
| 230 |
struct Run { |
| 231 |
start: usize, |
| 232 |
len: usize, |
| 233 |
} |
| 234 |
|
| 235 |
/// Examines the stack of runs and identifies the next pair of runs to merge. More specifically, |
| 236 |
/// if `Some(r)` is returned, that means `runs[r]` and `runs[r + 1]` must be merged next. If the |
| 237 |
/// algorithm should continue building a new run instead, `None` is returned. |
| 238 |
/// |
| 239 |
/// TimSort is infamous for its buggy implementations, as described here: |
| 240 |
/// http://envisage-project.eu/timsort-specification-and-verification/ |
| 241 |
/// |
| 242 |
/// The gist of the story is: we must enforce the invariants on the top four runs on the stack. |
| 243 |
/// Enforcing them on just top three is not sufficient to ensure that the invariants will still |
| 244 |
/// hold for *all* runs in the stack. |
| 245 |
/// |
| 246 |
/// This function correctly checks invariants for the top four runs. Additionally, if the top |
| 247 |
/// run starts at index 0, it will always demand a merge operation until the stack is fully |
| 248 |
/// collapsed, in order to complete the sort. |
| 249 |
#[inline] |
| 250 |
fn collapse(runs: &[Run]) -> Option<usize> { |
| 251 |
let n = runs.len(); |
| 252 |
|
| 253 |
if n >= 2 |
| 254 |
&& (runs[n - 1].start == 0 |
| 255 |
|| runs[n - 2].len <= runs[n - 1].len |
| 256 |
|| (n >= 3 && runs[n - 3].len <= runs[n - 2].len + runs[n - 1].len) |
| 257 |
|| (n >= 4 && runs[n - 4].len <= runs[n - 3].len + runs[n - 2].len)) |
| 258 |
{ |
| 259 |
if n >= 3 && runs[n - 3].len < runs[n - 1].len { |
| 260 |
Some(n - 3) |
| 261 |
} else { |
| 262 |
Some(n - 2) |
| 263 |
} |
| 264 |
} else { |
| 265 |
None |
| 266 |
} |
| 267 |
} |
| 268 |
|
| 269 |
/// Sorts a slice using merge sort, unless it is already in descending order. |
| 270 |
/// |
| 271 |
/// This function doesn't modify the slice if it is already non-descending or descending. |
| 272 |
/// Otherwise, it sorts the slice into non-descending order. |
| 273 |
/// |
| 274 |
/// This merge sort borrows some (but not all) ideas from TimSort, which is described in detail |
| 275 |
/// [here](https://github.com/python/cpython/blob/main/Objects/listsort.txt). |
| 276 |
/// |
| 277 |
/// The algorithm identifies strictly descending and non-descending subsequences, which are called |
| 278 |
/// natural runs. There is a stack of pending runs yet to be merged. Each newly found run is pushed |
| 279 |
/// onto the stack, and then some pairs of adjacent runs are merged until these two invariants are |
| 280 |
/// satisfied: |
| 281 |
/// |
| 282 |
/// 1. for every `i` in `1..runs.len()`: `runs[i - 1].len > runs[i].len` |
| 283 |
/// 2. for every `i` in `2..runs.len()`: `runs[i - 2].len > runs[i - 1].len + runs[i].len` |
| 284 |
/// |
| 285 |
/// The invariants ensure that the total running time is *O*(*n* \* log(*n*)) worst-case. |
| 286 |
/// |
| 287 |
/// # Safety |
| 288 |
/// |
| 289 |
/// The argument `buf` is used as a temporary buffer and must be at least as long as `v`. |
| 290 |
unsafe fn mergesort<T, F>(v: &mut [T], buf: *mut T, is_less: &F) -> MergesortResult |
| 291 |
where |
| 292 |
T: Send, |
| 293 |
F: Fn(&T, &T) -> bool + Sync, |
| 294 |
{ |
| 295 |
// Very short runs are extended using insertion sort to span at least this many elements. |
| 296 |
const MIN_RUN: usize = 10; |
| 297 |
|
| 298 |
let len = v.len(); |
| 299 |
|
| 300 |
// In order to identify natural runs in `v`, we traverse it backwards. That might seem like a |
| 301 |
// strange decision, but consider the fact that merges more often go in the opposite direction |
| 302 |
// (forwards). According to benchmarks, merging forwards is slightly faster than merging |
| 303 |
// backwards. To conclude, identifying runs by traversing backwards improves performance. |
| 304 |
let mut runs = vec![]; |
| 305 |
let mut end = len; |
| 306 |
while end > 0 { |
| 307 |
// Find the next natural run, and reverse it if it's strictly descending. |
| 308 |
let mut start = end - 1; |
| 309 |
|
| 310 |
if start > 0 { |
| 311 |
start -= 1; |
| 312 |
|
| 313 |
if is_less(v.get_unchecked(start + 1), v.get_unchecked(start)) { |
| 314 |
while start > 0 && is_less(v.get_unchecked(start), v.get_unchecked(start - 1)) { |
| 315 |
start -= 1; |
| 316 |
} |
| 317 |
|
| 318 |
// If this descending run covers the whole slice, return immediately. |
| 319 |
if start == 0 && end == len { |
| 320 |
return MergesortResult::Descending; |
| 321 |
} else { |
| 322 |
v[start..end].reverse(); |
| 323 |
} |
| 324 |
} else { |
| 325 |
while start > 0 && !is_less(v.get_unchecked(start), v.get_unchecked(start - 1)) { |
| 326 |
start -= 1; |
| 327 |
} |
| 328 |
|
| 329 |
// If this non-descending run covers the whole slice, return immediately. |
| 330 |
if end - start == len { |
| 331 |
return MergesortResult::NonDescending; |
| 332 |
} |
| 333 |
} |
| 334 |
} |
| 335 |
|
| 336 |
// Insert some more elements into the run if it's too short. Insertion sort is faster than |
| 337 |
// merge sort on short sequences, so this significantly improves performance. |
| 338 |
while start > 0 && end - start < MIN_RUN { |
| 339 |
start -= 1; |
| 340 |
insert_head(&mut v[start..end], &is_less); |
| 341 |
} |
| 342 |
|
| 343 |
// Push this run onto the stack. |
| 344 |
runs.push(Run { |
| 345 |
start, |
| 346 |
len: end - start, |
| 347 |
}); |
| 348 |
end = start; |
| 349 |
|
| 350 |
// Merge some pairs of adjacent runs to satisfy the invariants. |
| 351 |
while let Some(r) = collapse(&runs) { |
| 352 |
let left = runs[r + 1]; |
| 353 |
let right = runs[r]; |
| 354 |
merge( |
| 355 |
&mut v[left.start..right.start + right.len], |
| 356 |
left.len, |
| 357 |
buf, |
| 358 |
&is_less, |
| 359 |
); |
| 360 |
|
| 361 |
runs[r] = Run { |
| 362 |
start: left.start, |
| 363 |
len: left.len + right.len, |
| 364 |
}; |
| 365 |
runs.remove(r + 1); |
| 366 |
} |
| 367 |
} |
| 368 |
|
| 369 |
// Finally, exactly one run must remain in the stack. |
| 370 |
debug_assert!(runs.len() == 1 && runs[0].start == 0 && runs[0].len == len); |
| 371 |
|
| 372 |
// The original order of the slice was neither non-descending nor descending. |
| 373 |
MergesortResult::Sorted |
| 374 |
} |
| 375 |
|
| 376 |
//////////////////////////////////////////////////////////////////////////// |
| 377 |
// Everything above this line is copied from `std::slice::sort` (with very minor tweaks). |
| 378 |
// Everything below this line is parallelization. |
| 379 |
//////////////////////////////////////////////////////////////////////////// |
| 380 |
|
| 381 |
/// Splits two sorted slices so that they can be merged in parallel. |
| 382 |
/// |
| 383 |
/// Returns two indices `(a, b)` so that slices `left[..a]` and `right[..b]` come before |
| 384 |
/// `left[a..]` and `right[b..]`. |
| 385 |
fn split_for_merge<T, F>(left: &[T], right: &[T], is_less: &F) -> (usize, usize) |
| 386 |
where |
| 387 |
F: Fn(&T, &T) -> bool, |
| 388 |
{ |
| 389 |
let left_len = left.len(); |
| 390 |
let right_len = right.len(); |
| 391 |
|
| 392 |
if left_len >= right_len { |
| 393 |
let left_mid = left_len / 2; |
| 394 |
|
| 395 |
// Find the first element in `right` that is greater than or equal to `left[left_mid]`. |
| 396 |
let mut a = 0; |
| 397 |
let mut b = right_len; |
| 398 |
while a < b { |
| 399 |
let m = a + (b - a) / 2; |
| 400 |
if is_less(&right[m], &left[left_mid]) { |
| 401 |
a = m + 1; |
| 402 |
} else { |
| 403 |
b = m; |
| 404 |
} |
| 405 |
} |
| 406 |
|
| 407 |
(left_mid, a) |
| 408 |
} else { |
| 409 |
let right_mid = right_len / 2; |
| 410 |
|
| 411 |
// Find the first element in `left` that is greater than `right[right_mid]`. |
| 412 |
let mut a = 0; |
| 413 |
let mut b = left_len; |
| 414 |
while a < b { |
| 415 |
let m = a + (b - a) / 2; |
| 416 |
if is_less(&right[right_mid], &left[m]) { |
| 417 |
b = m; |
| 418 |
} else { |
| 419 |
a = m + 1; |
| 420 |
} |
| 421 |
} |
| 422 |
|
| 423 |
(a, right_mid) |
| 424 |
} |
| 425 |
} |
| 426 |
|
| 427 |
/// Merges slices `left` and `right` in parallel and stores the result into `dest`. |
| 428 |
/// |
| 429 |
/// # Safety |
| 430 |
/// |
| 431 |
/// The `dest` pointer must have enough space to store the result. |
| 432 |
/// |
| 433 |
/// Even if `is_less` panics at any point during the merge process, this function will fully copy |
| 434 |
/// all elements from `left` and `right` into `dest` (not necessarily in sorted order). |
| 435 |
unsafe fn par_merge<T, F>(left: &mut [T], right: &mut [T], dest: *mut T, is_less: &F) |
| 436 |
where |
| 437 |
T: Send, |
| 438 |
F: Fn(&T, &T) -> bool + Sync, |
| 439 |
{ |
| 440 |
// Slices whose lengths sum up to this value are merged sequentially. This number is slightly |
| 441 |
// larger than `CHUNK_LENGTH`, and the reason is that merging is faster than merge sorting, so |
| 442 |
// merging needs a bit coarser granularity in order to hide the overhead of Rayon's task |
| 443 |
// scheduling. |
| 444 |
const MAX_SEQUENTIAL: usize = 5000; |
| 445 |
|
| 446 |
let left_len = left.len(); |
| 447 |
let right_len = right.len(); |
| 448 |
|
| 449 |
// Intermediate state of the merge process, which serves two purposes: |
| 450 |
// 1. Protects integrity of `dest` from panics in `is_less`. |
| 451 |
// 2. Copies the remaining elements as soon as one of the two sides is exhausted. |
| 452 |
// |
| 453 |
// Panic safety: |
| 454 |
// |
| 455 |
// If `is_less` panics at any point during the merge process, `s` will get dropped and copy the |
| 456 |
// remaining parts of `left` and `right` into `dest`. |
| 457 |
let mut s = State { |
| 458 |
left_start: left.as_mut_ptr(), |
| 459 |
left_end: left.as_mut_ptr().add(left_len), |
| 460 |
right_start: right.as_mut_ptr(), |
| 461 |
right_end: right.as_mut_ptr().add(right_len), |
| 462 |
dest, |
| 463 |
}; |
| 464 |
|
| 465 |
if left_len == 0 || right_len == 0 || left_len + right_len < MAX_SEQUENTIAL { |
| 466 |
while s.left_start < s.left_end && s.right_start < s.right_end { |
| 467 |
// Consume the lesser side. |
| 468 |
// If equal, prefer the left run to maintain stability. |
| 469 |
let to_copy = if is_less(&*s.right_start, &*s.left_start) { |
| 470 |
get_and_increment(&mut s.right_start) |
| 471 |
} else { |
| 472 |
get_and_increment(&mut s.left_start) |
| 473 |
}; |
| 474 |
ptr::copy_nonoverlapping(to_copy, get_and_increment(&mut s.dest), 1); |
| 475 |
} |
| 476 |
} else { |
| 477 |
// Function `split_for_merge` might panic. If that happens, `s` will get destructed and copy |
| 478 |
// the whole `left` and `right` into `dest`. |
| 479 |
let (left_mid, right_mid) = split_for_merge(left, right, is_less); |
| 480 |
let (left_l, left_r) = left.split_at_mut(left_mid); |
| 481 |
let (right_l, right_r) = right.split_at_mut(right_mid); |
| 482 |
|
| 483 |
// Prevent the destructor of `s` from running. Rayon will ensure that both calls to |
| 484 |
// `par_merge` happen. If one of the two calls panics, they will ensure that elements still |
| 485 |
// get copied into `dest_left` and `dest_right``. |
| 486 |
mem::forget(s); |
| 487 |
|
| 488 |
// Wrap pointers in SendPtr so that they can be sent to another thread |
| 489 |
// See the documentation of SendPtr for a full explanation |
| 490 |
let dest_l = SendPtr(dest); |
| 491 |
let dest_r = SendPtr(dest.add(left_l.len() + right_l.len())); |
| 492 |
rayon_core::join( |
| 493 |
move || par_merge(left_l, right_l, dest_l.get(), is_less), |
| 494 |
move || par_merge(left_r, right_r, dest_r.get(), is_less), |
| 495 |
); |
| 496 |
} |
| 497 |
// Finally, `s` gets dropped if we used sequential merge, thus copying the remaining elements |
| 498 |
// all at once. |
| 499 |
|
| 500 |
// When dropped, copies arrays `left_start..left_end` and `right_start..right_end` into `dest`, |
| 501 |
// in that order. |
| 502 |
struct State<T> { |
| 503 |
left_start: *mut T, |
| 504 |
left_end: *mut T, |
| 505 |
right_start: *mut T, |
| 506 |
right_end: *mut T, |
| 507 |
dest: *mut T, |
| 508 |
} |
| 509 |
|
| 510 |
impl<T> Drop for State<T> { |
| 511 |
fn drop(&mut self) { |
| 512 |
let size = size_of::<T>(); |
| 513 |
let left_len = (self.left_end as usize - self.left_start as usize) / size; |
| 514 |
let right_len = (self.right_end as usize - self.right_start as usize) / size; |
| 515 |
|
| 516 |
// Copy array `left`, followed by `right`. |
| 517 |
unsafe { |
| 518 |
ptr::copy_nonoverlapping(self.left_start, self.dest, left_len); |
| 519 |
self.dest = self.dest.add(left_len); |
| 520 |
ptr::copy_nonoverlapping(self.right_start, self.dest, right_len); |
| 521 |
} |
| 522 |
} |
| 523 |
} |
| 524 |
} |
| 525 |
|
| 526 |
/// Recursively merges pre-sorted chunks inside `v`. |
| 527 |
/// |
| 528 |
/// Chunks of `v` are stored in `chunks` as intervals (inclusive left and exclusive right bound). |
| 529 |
/// Argument `buf` is an auxiliary buffer that will be used during the procedure. |
| 530 |
/// If `into_buf` is true, the result will be stored into `buf`, otherwise it will be in `v`. |
| 531 |
/// |
| 532 |
/// # Safety |
| 533 |
/// |
| 534 |
/// The number of chunks must be positive and they must be adjacent: the right bound of each chunk |
| 535 |
/// must equal the left bound of the following chunk. |
| 536 |
/// |
| 537 |
/// The buffer must be at least as long as `v`. |
| 538 |
unsafe fn recurse<T, F>( |
| 539 |
v: *mut T, |
| 540 |
buf: *mut T, |
| 541 |
chunks: &[(usize, usize)], |
| 542 |
into_buf: bool, |
| 543 |
is_less: &F, |
| 544 |
) where |
| 545 |
T: Send, |
| 546 |
F: Fn(&T, &T) -> bool + Sync, |
| 547 |
{ |
| 548 |
let len = chunks.len(); |
| 549 |
debug_assert!(len > 0); |
| 550 |
|
| 551 |
// Base case of the algorithm. |
| 552 |
// If only one chunk is remaining, there's no more work to split and merge. |
| 553 |
if len == 1 { |
| 554 |
if into_buf { |
| 555 |
// Copy the chunk from `v` into `buf`. |
| 556 |
let (start, end) = chunks[0]; |
| 557 |
let src = v.add(start); |
| 558 |
let dest = buf.add(start); |
| 559 |
ptr::copy_nonoverlapping(src, dest, end - start); |
| 560 |
} |
| 561 |
return; |
| 562 |
} |
| 563 |
|
| 564 |
// Split the chunks into two halves. |
| 565 |
let (start, _) = chunks[0]; |
| 566 |
let (mid, _) = chunks[len / 2]; |
| 567 |
let (_, end) = chunks[len - 1]; |
| 568 |
let (left, right) = chunks.split_at(len / 2); |
| 569 |
|
| 570 |
// After recursive calls finish we'll have to merge chunks `(start, mid)` and `(mid, end)` from |
| 571 |
// `src` into `dest`. If the current invocation has to store the result into `buf`, we'll |
| 572 |
// merge chunks from `v` into `buf`, and vice versa. |
| 573 |
// |
| 574 |
// Recursive calls flip `into_buf` at each level of recursion. More concretely, `par_merge` |
| 575 |
// merges chunks from `buf` into `v` at the first level, from `v` into `buf` at the second |
| 576 |
// level etc. |
| 577 |
let (src, dest) = if into_buf { (v, buf) } else { (buf, v) }; |
| 578 |
|
| 579 |
// Panic safety: |
| 580 |
// |
| 581 |
// If `is_less` panics at any point during the recursive calls, the destructor of `guard` will |
| 582 |
// be executed, thus copying everything from `src` into `dest`. This way we ensure that all |
| 583 |
// chunks are in fact copied into `dest`, even if the merge process doesn't finish. |
| 584 |
let guard = CopyOnDrop { |
| 585 |
src: src.add(start), |
| 586 |
dest: dest.add(start), |
| 587 |
len: end - start, |
| 588 |
}; |
| 589 |
|
| 590 |
// Wrap pointers in SendPtr so that they can be sent to another thread |
| 591 |
// See the documentation of SendPtr for a full explanation |
| 592 |
let v = SendPtr(v); |
| 593 |
let buf = SendPtr(buf); |
| 594 |
rayon_core::join( |
| 595 |
move || recurse(v.get(), buf.get(), left, !into_buf, is_less), |
| 596 |
move || recurse(v.get(), buf.get(), right, !into_buf, is_less), |
| 597 |
); |
| 598 |
|
| 599 |
// Everything went all right - recursive calls didn't panic. |
| 600 |
// Forget the guard in order to prevent its destructor from running. |
| 601 |
mem::forget(guard); |
| 602 |
|
| 603 |
// Merge chunks `(start, mid)` and `(mid, end)` from `src` into `dest`. |
| 604 |
let src_left = slice::from_raw_parts_mut(src.add(start), mid - start); |
| 605 |
let src_right = slice::from_raw_parts_mut(src.add(mid), end - mid); |
| 606 |
par_merge(src_left, src_right, dest.add(start), is_less); |
| 607 |
} |
| 608 |
|
| 609 |
/// Sorts `v` using merge sort in parallel. |
| 610 |
/// |
| 611 |
/// The algorithm is stable, allocates memory, and `O(n log n)` worst-case. |
| 612 |
/// The allocated temporary buffer is of the same length as is `v`. |
| 613 |
pub(super) fn par_mergesort<T, F>(v: &mut [T], is_less: F) |
| 614 |
where |
| 615 |
T: Send, |
| 616 |
F: Fn(&T, &T) -> bool + Sync, |
| 617 |
{ |
| 618 |
// Slices of up to this length get sorted using insertion sort in order to avoid the cost of |
| 619 |
// buffer allocation. |
| 620 |
const MAX_INSERTION: usize = 20; |
| 621 |
// The length of initial chunks. This number is as small as possible but so that the overhead |
| 622 |
// of Rayon's task scheduling is still negligible. |
| 623 |
const CHUNK_LENGTH: usize = 2000; |
| 624 |
|
| 625 |
// Sorting has no meaningful behavior on zero-sized types. |
| 626 |
if size_of::<T>() == 0 { |
| 627 |
return; |
| 628 |
} |
| 629 |
|
| 630 |
let len = v.len(); |
| 631 |
|
| 632 |
// Short slices get sorted in-place via insertion sort to avoid allocations. |
| 633 |
if len <= MAX_INSERTION { |
| 634 |
if len >= 2 { |
| 635 |
for i in (0..len - 1).rev() { |
| 636 |
insert_head(&mut v[i..], &is_less); |
| 637 |
} |
| 638 |
} |
| 639 |
return; |
| 640 |
} |
| 641 |
|
| 642 |
// Allocate a buffer to use as scratch memory. We keep the length 0 so we can keep in it |
| 643 |
// shallow copies of the contents of `v` without risking the dtors running on copies if |
| 644 |
// `is_less` panics. |
| 645 |
let mut buf = Vec::<T>::with_capacity(len); |
| 646 |
let buf = buf.as_mut_ptr(); |
| 647 |
|
| 648 |
// If the slice is not longer than one chunk would be, do sequential merge sort and return. |
| 649 |
if len <= CHUNK_LENGTH { |
| 650 |
let res = unsafe { mergesort(v, buf, &is_less) }; |
| 651 |
if res == MergesortResult::Descending { |
| 652 |
v.reverse(); |
| 653 |
} |
| 654 |
return; |
| 655 |
} |
| 656 |
|
| 657 |
// Split the slice into chunks and merge sort them in parallel. |
| 658 |
// However, descending chunks will not be sorted - they will be simply left intact. |
| 659 |
let mut iter = { |
| 660 |
// Wrap pointer in SendPtr so that it can be sent to another thread |
| 661 |
// See the documentation of SendPtr for a full explanation |
| 662 |
let buf = SendPtr(buf); |
| 663 |
let is_less = &is_less; |
| 664 |
|
| 665 |
v.par_chunks_mut(CHUNK_LENGTH) |
| 666 |
.with_max_len(1) |
| 667 |
.enumerate() |
| 668 |
.map(move |(i, chunk)| { |
| 669 |
let l = CHUNK_LENGTH * i; |
| 670 |
let r = l + chunk.len(); |
| 671 |
unsafe { |
| 672 |
let buf = buf.get().add(l); |
| 673 |
(l, r, mergesort(chunk, buf, is_less)) |
| 674 |
} |
| 675 |
}) |
| 676 |
.collect::<Vec<_>>() |
| 677 |
.into_iter() |
| 678 |
.peekable() |
| 679 |
}; |
| 680 |
|
| 681 |
// Now attempt to concatenate adjacent chunks that were left intact. |
| 682 |
let mut chunks = Vec::with_capacity(iter.len()); |
| 683 |
|
| 684 |
while let Some((a, mut b, res)) = iter.next() { |
| 685 |
// If this chunk was not modified by the sort procedure... |
| 686 |
if res != MergesortResult::Sorted { |
| 687 |
while let Some(&(x, y, r)) = iter.peek() { |
| 688 |
// If the following chunk is of the same type and can be concatenated... |
| 689 |
if r == res && (r == MergesortResult::Descending) == is_less(&v[x], &v[x - 1]) { |
| 690 |
// Concatenate them. |
| 691 |
b = y; |
| 692 |
iter.next(); |
| 693 |
} else { |
| 694 |
break; |
| 695 |
} |
| 696 |
} |
| 697 |
} |
| 698 |
|
| 699 |
// Descending chunks must be reversed. |
| 700 |
if res == MergesortResult::Descending { |
| 701 |
v[a..b].reverse(); |
| 702 |
} |
| 703 |
|
| 704 |
chunks.push((a, b)); |
| 705 |
} |
| 706 |
|
| 707 |
// All chunks are properly sorted. |
| 708 |
// Now we just have to merge them together. |
| 709 |
unsafe { |
| 710 |
recurse(v.as_mut_ptr(), buf, &chunks, false, &is_less); |
| 711 |
} |
| 712 |
} |
| 713 |
|
| 714 |
#[cfg(test)] |
| 715 |
mod tests { |
| 716 |
use super::split_for_merge; |
| 717 |
use rand::distributions::Uniform; |
| 718 |
use rand::{thread_rng, Rng}; |
| 719 |
|
| 720 |
#[test] |
| 721 |
fn test_split_for_merge() { |
| 722 |
fn check(left: &[u32], right: &[u32]) { |
| 723 |
let (l, r) = split_for_merge(left, right, &|&a, &b| a < b); |
| 724 |
assert!(left[..l] |
| 725 |
.iter() |
| 726 |
.all(|&x| right[r..].iter().all(|&y| x <= y))); |
| 727 |
assert!(right[..r].iter().all(|&x| left[l..].iter().all(|&y| x < y))); |
| 728 |
} |
| 729 |
|
| 730 |
check(&[1, 2, 2, 2, 2, 3], &[1, 2, 2, 2, 2, 3]); |
| 731 |
check(&[1, 2, 2, 2, 2, 3], &[]); |
| 732 |
check(&[], &[1, 2, 2, 2, 2, 3]); |
| 733 |
|
| 734 |
let rng = &mut thread_rng(); |
| 735 |
|
| 736 |
for _ in 0..100 { |
| 737 |
let limit: u32 = rng.gen_range(1..21); |
| 738 |
let left_len: usize = rng.gen_range(0..20); |
| 739 |
let right_len: usize = rng.gen_range(0..20); |
| 740 |
|
| 741 |
let mut left = rng |
| 742 |
.sample_iter(&Uniform::new(0, limit)) |
| 743 |
.take(left_len) |
| 744 |
.collect::<Vec<_>>(); |
| 745 |
let mut right = rng |
| 746 |
.sample_iter(&Uniform::new(0, limit)) |
| 747 |
.take(right_len) |
| 748 |
.collect::<Vec<_>>(); |
| 749 |
|
| 750 |
left.sort(); |
| 751 |
right.sort(); |
| 752 |
check(&left, &right); |
| 753 |
} |
| 754 |
} |
| 755 |
} |