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

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!

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

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

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

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.

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

2 Likes