Does a threaded (quick)sort necessarily require unsafe and raw pointers?

help
#1

Hello!

I'm going through a Rust course on algorithms, and I've found some code that strucks me as odd.

Ignoring the choice of explaning threading on a quicksort implementation (later, Rayon is used), and ignoring the quicksort logic (which is not a problem), my question is: is it really necessary/optimal to use unsafe code and raw pointers?

This is the implementation:

pub struct RawSend<T>(*mut [T]);
unsafe impl<T> Send for RawSend<T> {}

pub fn threaded_quicksort<T: 'static + PartialOrd + Send>(collection: &mut [T]) {
    if collection.len() <= 1 {
        return;
    }

    let p = pivot(collection);

    let (collection_1, collection_2) = collection.split_at_mut(p);

    let collection_1 = collection_1 as *mut [T];
    let collection_1 = RawSend(collection_1);

    unsafe {
        let thread = std::thread::spawn(move || {
            threaded_quicksort(&mut *collection_1.0);
        });
        threaded_quicksort(&mut collection_2[1..]);

        thread.join().ok();
    }
}

Thanks!

#2

It looks like they're using the raw pointers to implement a primitive from of scoped threads, which require unsafe under the hood somewhere.

#3 
pub fn threaded_quicksort_safe<T: /* 'static + */ PartialOrd + Send>(collection: &mut [T]) {
    if collection.len() <= 1 {
        return;
    }

    let p = pivot(collection);

    let (collection_1, collection_2) = collection.split_at_mut(p);
    
    crossbeam::scope(|scope| {
        scope.spawn(|_| {
            threaded_quicksort_safe(collection_1);
        });
        threaded_quicksort_safe(&mut collection_2[1..]);
    }).unwrap(); // thread is also implicitly joined here
}
5 Likes
#4

Here is the same code rewritten with scoped threads:

pub fn threaded_quicksort<T: PartialOrd + Send>(collection: &mut [T]) {
    if collection.len() <= 1 {
        return;
    }

    let p = pivot(collection);

    let (collection_1, collection_2) = collection.split_at_mut(p);

    crossbeam::thread::scope(|s| {
        s.spawn(|_| threaded_quicksort(collection_1));
        threaded_quicksort(collection_2);
    }).unwrap();
}

In reality you'd never write this code because spawning so many threads is way too inefficient. If you wanted to parallelize it a threadpool is probably the way to go (where you only move it to another thread if there is a free thread).

Edit: darn, @steffahn beat me to it.

2 Likes
#5

This was one of the cases in the intro to rayon post. You'de probably need to adapt it, as the lib has changed between then and now.

#6

Rayon has since included par_sort* methods in the library too.

2 Likes