For some background:
I wanted to reach out and ask if there was a strategy in Rust for handling the divide and conquer portion of the mergesort algorithm in a multithreaded scenario using only the standard Rust library. I've seen some cool takes on similar problems completed using the crossbeam and rayon crates, but I'm trying to keep my use of external crates to a minimum while I'm learning the ins and outs of the language (my current experiences stem mainly from C, C++ and C#).
For the actual issue:
While implementing the multithreaded version of the algorithm, I hit a wall with the compiler via lifetime differences between the function scope and the spawned threads. In the code block below, what would be the most appropriate course of action for abiding by the 'static lifetime required by the argument to thread::spawn?
I'm not dead set on the logic structure either, please do let me know if there's a more Rust-like way to achieve this like with iterators for instance.
use rand::{rngs::StdRng, Rng, SeedableRng};
use std::sync::{Arc, Mutex};
use std::thread;
/// implementation will not handle mutex lock failures or thread failures for brevity.
pub fn mergesort_mt(
collection: &mut [u8],
max_threads: usize,
thread_counter: Arc<Mutex<usize>>,
) -> Vec<u8> {
if collection.len() < 2 {
return collection.to_vec();
}
let pivot = collection.len() / 2;
let (mut left, mut right) = collection.split_at_mut(pivot);
let mut mutex_value = thread_counter.lock().unwrap();
let num_remaining = max_threads - *mutex_value;
if num_remaining >= 2 {
*mutex_value += 2;
drop(mutex_value);
let counter = Arc::clone(&thread_counter);
let handle_left = thread::spawn(move || mergesort_mt(&mut left, max_threads, counter));
let counter = Arc::clone(&thread_counter);
let handle_right = thread::spawn(move || mergesort_mt(&mut right, max_threads, counter));
let mut left = handle_left.join().unwrap();
let mut right = handle_right.join().unwrap();
return merge(&mut left[..], &mut right[..]);
} else if num_remaining == 1 {
*mutex_value += 1;
drop(mutex_value);
let counter = Arc::clone(&thread_counter);
let handle_left = thread::spawn(move || mergesort_mt(&mut left[..], max_threads, counter));
let mut left = handle_left.join().unwrap();
let mut right = mergesort_mt(&mut right[..], max_threads, thread_counter);
return merge(&mut left[..], &mut right[..]);
} else {
drop(mutex_value);
let mut left = mergesort_mt(&mut left[..], max_threads, Arc::clone(&thread_counter));
let mut right = mergesort_mt(&mut right[..], max_threads, Arc::clone(&thread_counter));
return merge(&mut left[..], &mut right[..]);
}
}
Thanks for reading and I appreciate the feedback!
