For some quick context, I'm fairly new to Rust and decided to give myself a difficult-but-attainable task of implementing a sorting algorithm. I chose bogosort (or stupid-sort, shuffle-sort, whatever your preference is) and got it working pretty quickly.

I then decided to make it faster by threading it lol.

This works pretty well and I can definitely tell there's a performance improvement. However I want to make sure I'm implementing it decently. My biggest concern is making sure all of the other threads die when one of them finishes (i.e. "sorted" the vector).

The way I have it implemented below uses a boolean Mutex within an Arc. My understanding is that this way allows every thread to have access to it but also allows it to be modified safely. I use this Mutex as the condition in my while loop. Once any thread "sorts" the vector, it will change the Mutex - effectively telling every other thread to stop.

My question is, have I implemented this correctly? Am I stopping the threads correctly? And is the best way to do it? Any feedback (including constructively roasting my code) is immensely appreciated as I'd like to learn as much as I can.

use rand::prelude::*;
use rand_chacha::ChaCha8Rng;
use std::time::Instant;
use std::sync::mpsc;
use std::sync::{Mutex,Arc};

const ELEMENT_COUNT: i32 = 5;

fn main() {
// Initialize a vector with <ELEMENT_COUNT> random numbers from 1-100
let mut rng = ChaCha8Rng::seed_from_u64(31);
let mut vec: Vec<i32> = (0..ELEMENT_COUNT).collect();
for x in &mut vec {
*x = rng.gen_range(1..100);
}

// Start a counter to track performance
let clock = Instant::now();
let (tx, rx) = mpsc::channel();
let mut handles = vec![];
let done = Arc::new(Mutex::new(true));

// Create a bunch of threads
let tx = tx.clone();
let done_shared = Arc::clone(&done);
let mut vec = Vec::clone(&vec);

let handle = thread::spawn(move || {
't_outer: while *done_shared.lock().unwrap() {
// println!("\nthread: {}\nvar: {:?}\n", i, *done_shared);
let mut counter = 1;
// Check if it's sorted
't_inner: for x in &vec {
// If the xth element is greater than the element after it: it's not sorted, so give up
if x > &vec[counter] {
break 't_inner;
}
counter = counter + 1;
// But, if this counter finds itself equal to the length of our vector, then we must be sorted
if counter == vec.len() {
tx.send(clock.elapsed()).unwrap();
// Set the while loop condition to false (effectively killing every other thread)
*done_shared.lock().unwrap() = false;
break 't_outer;
}
}
}
});
// handle.join();

handles.push(handle);

}
let b = rx.recv().unwrap();
println!("Took this long: {:?}", b);

// Join the handles in the vector
for i in handles {
i.join().unwrap();
}
}

• It's not quite clear what the goal of this review is. Your implementation does not transfer the sorted array back to the main thread, so the only output it produces is how long it took to find it. Then again, if you were really interested in the sorted array, you wouldn't be using Bogosort. There are lots of things I could comment on, but without a clear goal it's hard to tell what you are interested in – e.g. the recommendation "don't use Bogosort for sorting" likely isn't what you are looking for. Apr 25, 2022 at 12:19
• You're right, I have other code that does that that I didn't include here. My main goal is to make sure that I've handled the Mutex thing here in the best way. So when a thread "sorts" the vector and changes the Mutex so that the other threads see that their while condition is now false, is that the best way to shutdown threads or is there a better way to do this? Apr 25, 2022 at 12:53

List of improvements I would make:

• I'm uncertain why you use Arc::clone(...), just use .clone() directly. Same for Vec::clone().
• The initialization of the vector: you initialize it with an iterator, collect, and then iterate manually in a C-style for loop. Instead, just use the iterator you already have to iterate ;). This can be done with either .map(), or with the repeat().take() pattern.
• Name your variables more meaningful than tx and rx and vec. Don't name them by what their type is, but by what they represent.
• Like in the initialization, the join_handles vector could be an iterator instead. It doesn't make much of a difference, tbh, but leaves the vector to be non-mutable afterwards. I like it more with iterators, but this one is probably personal taste.
• Using a Arc<Mutex<bool>> to signal cancellation is kind of fine, but is VERY slow compared to the compiler-optimized Arc<AtomicBool>, which does the exact same thing. I think this is an important point to optimize, because that bool is the choke point of your otherwise embarrassingly parallel problem.
• I'm uncertain how much of a difference it makes, but I'd probably cache the thread_rng instead of querying it every iteration.
• The fact that the loops terminate when done becomes false is semantically confusing, I'd invert it
• The way you iterate through the vector to check if it's sorted is quite confusing. I think considering counter == data.len() the special case of the loop is confusing, and I'd make that the default case. The special case would then be that it's unsorted.
• Either way, the entire loop is written in a C/C++ style. In proper Rust style i'd rewrite it to be more functional, using iterators. The main reason is that direct array access via [] operator is discouraged as much as possible, as it is slow (rust does an out-of-range check every time) and error prone. To get the true performance potential of rust, you want to use iterators instead.
• Usually, I'd simply use the .sorted() operation of the vector. But as this is an exercise, you probably want to implement it yourself, so here I demonstrate you how it would be implemented with iterators. Again, iterator has a .is_sorted() operation, which we will ignore. This is the point where I'd usually pull in itertools, as the .tuple_windows() function is exactly what you would need here, to check two consecutive numbers. But if you want to only use normal Rust iterator operations, I would go with creating something similar myself. You can iterate over the vector multiple times in parallel, with an offset of one. You can use this to query pairs of numbers, which you can then check for order. Then you can iterate until you find the first pair that isn't ordered correctly. Performance wise this is comparable or even faster than doing it without iterators, so no worries.
• Use usize for size-related numbers.

Many words, let's see code! Here's my attempt to improve your code:

use rand::prelude::*;
use rand_chacha::ChaCha8Rng;
use std::sync::atomic::AtomicBool;
use std::sync::atomic::Ordering;
use std::sync::mpsc;
use std::sync::Arc;
use std::time::Instant;

const ELEMENT_COUNT: usize = 5;

fn main() {
// Initialize a vector with <ELEMENT_COUNT> random numbers from 1-100
let mut rng = ChaCha8Rng::seed_from_u64(31);
let data_to_sort: Vec<i32> = std::iter::repeat_with(|| rng.gen_range(1..100))
.take(ELEMENT_COUNT)
.collect();

// Start a counter to track performance
let clock = Instant::now();
let (set_duration, duration) = mpsc::channel();
let done = Arc::new(AtomicBool::new(false));

// Create a bunch of threads
.map(|_| {
let set_duration = set_duration.clone();
let done = done.clone();
let mut data = data_to_sort.clone();

data.shuffle(&mut rng);

let elements_left = data.iter();
let elements_right = data.iter().skip(1);
let sorted = elements_left
.zip(elements_right)
.all(|(left, right)| left <= right);

if sorted {
set_duration.send(clock.elapsed()).unwrap();
// Set the done condition to true (effectively killing every other thread)
done.store(true, Ordering::Release);
break;
}
}
})
})
.collect::<Vec<_>>();

let b = duration.recv().unwrap();
println!("Took this long: {:?}", b);

// Join the handles in the vector
for i in handles {
i.join().unwrap();
}
}

• AtomicBool is non-blocking. In most architectures, writing/reading an 1-byte value (or even 4/8-byte in most 32/64-bit systems) is a already atomic, so synchronization around it is a noop. The entire logic of aquiring a lock, waiting in a loop until others release the lock etc gets completely compiled out. Further, lock() has the chance to panic, while AtomicBool cannot panic. Just do demonstrate HOW much more overhead a Mutex creates: rust.godbolt.org/z/3nGY533a9 Apr 25, 2022 at 14:17
• Well, in the bool case it's still 2 more assembly instructions, as it seems that Rust internally does an int-to-bool conversion for 8-bit integers it didn't verify to be a bool before (or something similar). But for u32, it's literally a single instruction compared to all that mess for mutexes. Apr 25, 2022 at 14:40
• There is different kinds of multi-threading problems. Atomics are not susceptible to concurrent read/writes, but are still susceptible to read-copy-write problems. Look at this code that should demonstrate the problem: play.rust-lang.org/…. For more information, keywords to search are Atomics Non-blocking data structures, CAS, Read-modify-write, race conditions in parallel programming or similar. Apr 25, 2022 at 14:52
• @LambBrainz: You definitely want access to shared stuff to be read-only in the normal case so multiple threads can do it in parallel. Reading a lock-free atomic simply works that way, unlike taking a lock around reading a non-atomic. When changing a variable, if multiple threads write it with true, it will definitely become true because no threads ever write a false value. That's fully allowed, and part of the point of atomics. Apr 26, 2022 at 3:25
• @LambBrainz: In your real use-case, you might want to make sure only one thread actually does the copying work even if multiple threads find the sorted order at the same time. To do that, atomically exchange with true. The thread that saw the old value as false is the one that "won the race", and should do the work. The other threads should just exit, since they can see that some other thread had already indicated the search was done and is in the process of doing the cleanup. This is using bool exchange as a test-and-set. You can equivalently use compare_exchange (not _weak I think) Apr 26, 2022 at 3:29

You definitely want access to shared stuff to be read-only in the normal case so multiple threads can do it in parallel. Reading a lock-free atomic simply works that way, unlike taking a lock around reading a non-atomic.

As @Finomnis answered, the most critical thing here is to use a lock-free atomic variable as a flag to see if its time to exit.

Your implementation does not transfer the sorted array back to the main thread, so the only output it produces is how long it took to find it. - Sven

You're right, I have other code that does that that I didn't include here.

In your real use-case, you might want to make sure only one thread actually does the copying work even if multiple threads find the sorted order at the same time.

To do that, atomically exchange with true. The thread that saw the old value as false is the one that "won the race" and should do the work.

The other threads should just exit, since they can see that some other thread had already indicated the search was done and is in the process of doing the cleanup.

This is using bool exchange as a test-and-set. You can equivalently use compare_exchange (not compare_exchange_weak; that could fail spuriously leaving no thread doing the work.)

@Finomnis suggested a further refinement of this idea: instead of a bool and having to actually join the thread to get synchronization, combine this done coordination with passing the data.

Use an atomic pointer (to a container I guess) that's initially null, which threads (try to) CAS from null to point at their sorted buffer. The one that wins thus passes ownership of the container to whatever thread reads it.

(If there could be a race for claiming ownership, readers could exchange it back to null, perhaps after a read-only check sees non-null to avoid contention, although that would lead to some sort thread never seeing non-null and not stopping if you actually have those readers spinning in parallel with sort worker threads.)

I only know a tiny amount of Rust, but in C++ you'd want std::atomic< std::array<int,n>* > sorted_data; (or with just int* or even std::vector<int>* if the size isn't a compile-time constant.)

This means the sorter threads need to dynamically allocate memory they can pass off ownership of, so when they find a correct sort it's already sitting in a container they can give away.

So when a sort worker finds a correct sort, it does something like this, but probably in a more modern way that avoids manually delete. I'm just showing the simplistic way without smart pointers so there's less going on besides the algorithm I'm talking about, not as an actual recommendation for C++ style, since this is a Rust question anyway. This is not good modern C++ style either, I don't think; I assume there's an idiomatic way to keep the buffer owned by a shared_ptr or unique_ptr.

// C++ sort of pseudo-code

// global shared var
std::atomic< std::array<int,n>* > shared_sorted_data;  // initialized to nullptr by default

void worker()
{
auto local_buffer = new std::array<int,n>;
do{
bogosort into local_buffer
if (locally_sorted) break;

if (locally_sorted) {

// upon finding a valid sort, do one CAS attempt and either return without deleting,
// or fall through to the normal end of function deletion.

std::array<int,n>* oldval = nullptr;
if (sorted_data.compare_exchange_strong(oldval, local_buffer, std::memory_order_release)) {
// we won the race, successfully handed off ownership
// oldval is still null
return;   // without deleteing
} else {
// oldval is non-null; CAS_strong doesn't have spurious failure
// if we'd used a memory order including acquire in our CAS,
// we could read the other thread's sorted data from  *oldval  if we wanted
// fall through to delete, like if we hadn't found a sort at all
}
}

delete local_buffer;   // delete our own, another thread found a sort.  (And won the race, or we never found a valid sort.)
}


(The memory order needs to be at least release so readers that see the pointer are also guaranteed to see the pointed-to data. The default seq_cst includes that and more, and is fine.)

Another way to combine passing the data with coordinating stopping other threads would be to use an integer instead of a boolean as part of a struct. So when a thread discovers a correct sort order, it (tries to) CAS the integer from 0 to 1, and if successful it copies the data or passes ownership of a reference into another member of the struct. And when that's done, does a release-store of 2. When any other thread sees a 2 (with an acquire load), it can access the data.

That might make sense if you were actually copying a bunch of data, instead of just passing a reference to a dynamic allocation.

BTW, you might find https://preshing.com/20120612/an-introduction-to-lock-free-programming useful; Preshing's articles from the early 2010s are still great, and the concepts are mostly language-independent.

(Some of his stuff predates ISO C++ std::atomic being widespread, so there are some hand-rolled atomics in C++ examples, and compiler-specific stuff, but the way he explains it actually helps understanding vs. just considering it opaque, at least for me since I like to understand in terms of what really happens at a lower level. Many of his articles are conceptual in nature, about how computers work more than language formalism. Especially in terms of memory order, which is actually a non-problem for you where you just have an exit_now flag. And synchronization for the copied sorted data given by join, once you get around to doing that in a thread that exits. I'm assuming Rust threads have similar rules to ISO C and C++ where thread exit and join have release/acquire semantics and create a happens-before relationship.)

• (This is mostly a copy/paste of my comments on another answer, kind of addressing future design ideas, except for the atomic vs. mutex for bool which is a critical performance problem in the current implementation and bears more discussion.) Apr 26, 2022 at 15:45
• It would probably even be good to go one step further. So far everyone treated the shutdown detection and the delivery of the result as two separate items, while in reality, I'm sure those could be combined in one object. This would make it less error-prone if someone ever had to change the code later on. Apr 26, 2022 at 23:27
• @Finomnis: Oh, like with an integer instead of a boolean as part of a struct? So when a thread discovers a correct sort order, it (tries to) CAS the integer from 0 to 1, and if successful it copies the data or passes ownership of a reference into another member of the struct. And when that's done, does a release-store of 2. When any other thread sees a 2 (with an acquire load), it can access the data. Apr 27, 2022 at 2:13
• @Finomnis: Or if we have an atomic reference (to a container), we can CAS or exchange that from null to non-null. The thread that succeeds no longer has ownership of the buffer, but any other threads should free their shuffle buffer just like they would if they saw another thread report done without having found a sort themselves. Apr 27, 2022 at 2:14
• @PeterCordes I meant a class that provides "finishAndSetTime", "is Finished" and "waitForFinishAndGetTime". That would combine shutdown and time propagation. Apr 27, 2022 at 16:11