Multithreaded bogosort in Rust

Question

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 rand::thread_rng;
use std::time::Instant;
use std::thread;
use std::sync::mpsc;
use std::sync::{Mutex,Arc};

const ELEMENT_COUNT: i32 = 5;
const THREAD_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
    for _i in 0..THREAD_COUNT {
        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() {
                    vec.shuffle(&mut thread_rng());
                    // 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();
    }
}

Answer 1

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::thread_rng;
use rand_chacha::ChaCha8Rng;
use std::sync::atomic::AtomicBool;
use std::sync::atomic::Ordering;
use std::sync::mpsc;
use std::sync::Arc;
use std::thread;
use std::time::Instant;

const ELEMENT_COUNT: usize = 5;
const THREAD_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
    let handles = (0..THREAD_COUNT)
        .map(|_| {
            let set_duration = set_duration.clone();
            let done = done.clone();
            let mut data = data_to_sort.clone();

            thread::spawn(move || {
                let mut rng = thread_rng();

                while !done.load(Ordering::Acquire) {
                    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();
    }
}

Answer 2

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

// in a worker thread
void worker()
{
  auto local_buffer = new std::array<int,n>;
  do{
      bogosort into local_buffer
      if (locally_sorted) break;
  } while (shared_sorted_data.load(relaxed) != nullptr)

  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.)