0

I have written a simple slice-based quick sort function in rust but am facing some difficulties making it multi-threaded.

Here's the quicksort function:

fn quicksort<
    T: PartialOrd + Clone + Copy + Send,
>(
    arr: &mut [T],
) {
    let (low,high) = partition(arr);

    let len = arr.len();

    // Splitting the array into two parts so they can be safely moved into the thread closures.
    let (mut first, mut second) = arr.split_at_mut(low);

    let mut handles: Vec<std::thread::JoinHandle<()>> = vec![];
    
    if low > 0 {
        handles.push(thread::spawn(move || {
            quicksort(first);
        }));
    }

    if high < len {
        handles.push(thread::spawn(move || {
            quicksort(second);
        }));
    }

    for handle in handles {
        handle.join();
    }
}

With the following partition function:

fn partition<T: PartialOrd + Clone + Copy + std::fmt::Debug + std::fmt::Display>(
    arr: &mut [T],
) -> (usize, usize) {
    let len = arr.len();
    let pivot_index = len / 2;
    let pivot = arr[pivot_index];
    arr.swap(pivot_index, len);
    let mut low = 0;
    let mut high = 0;
    let mut i = 0;
   
    while i < len {
        if arr[i] < pivot {
            if i > low {
                arr.swap(i, low);
                if high != low {
                    arr.swap(i, high);
                }
            }
            low += 1;
            high += 1
        } else if arr[i] == pivot {
            if i > high {
                arr.swap(i, high);
            }
            high += 1
        }
        i += 1;
    }
 
    (low, high)
}

Upon trying to compile the program, I get the following error:

error[E0621]: explicit lifetime required in the type of `arr`
   --> main.rs:180:22
    |
164 |     arr: &mut [T],
    |          -------- help: add explicit lifetime `'static` to the type of `arr`: `&'static mut [T]`
...
180 |         handles.push(thread::spawn(move || {
    |                      ^^^^^^^^^^^^^ lifetime `'static` required

The 'static lifetime annotation is not viable since I want to be able to use the function inside function scopes without having to define arr in the main() function.

If I understand correctly, because I am calling handle.join() for both threads, lifetime 'static should not be required, since &arr would only go out of scope once the two threads had finished. What can I do to fix this?

I would also like to add that I am still extremely new to rust and that any insight into rust's ownership and lifetime system will be greatly appreciated.

Gionikva
  • 3
  • 3
  • 4
    Does this answer your question? [How can I pass a reference to a stack variable to a thread?](https://stackoverflow.com/questions/32750829/how-can-i-pass-a-reference-to-a-stack-variable-to-a-thread) – MaxV Sep 11 '20 at 17:50
  • [Here's the `crossbeam` suggestion from the other Q&A applied to your problem](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=b5ec0ddc598dae87a3a2cc37c228ee71). It looks like there are still some bugs (for instance, `arr.swap(pivot_index, len)` is never going to work) but I'll let you track those down. – trent Sep 11 '20 at 18:32
  • The crossbeam suggestion seems to have solved the problem. I guess for now this task is impossible with just the standard library. @trentcl Thanks for the suggestion, I was using an index-based quicksort algorithm before this (which can not be used here because of rust's single mutable reference at a time restiction) and seems like I still have a few things to change to get this one to work. Anyways, thanks for the help. – Gionikva Sep 12 '20 at 08:26

0 Answers0