Struggling with concurrency, value dropped while borrowed compiler error

I'm attempting to write some code to calculate the Collatz Conjecture/3n+1 problem for my first attempt at concurrent programming in Rust. Moving from Python I am still new to ownership, borrowing, and concurrency, so I apologise in advance for this messy implementation.

My idea is I have a vector, values, over which I will calculate the iterations required/taken and maximum value of the 3n+1 problem for each given number. The order of each number calculated isn't important, so I've attempted to split the array into chunks according to the number of CPUs of the system, as I want to be able to run this on various hardware without altering the code. For each chunk I want to spawn a new thread to iterate through the vector slices, and use message passing to pass the results downstream as described in the Rust book. A snippet of the code I have written is as follows:

fn collatz(start_value: usize) -> (u16, usize) {
    // --snip-- applying 3n+1 problem logic
    (iterations, max_value)
}

fn run_multithread(values: Vec<usize>) {
    let (tx, rx) = mpsc::channel();
    let num_cpus = num_cpus::get();

    for slice in values.chunks(num_cpus) { // error points to here: `argument requires that `values` is borrowed for `'static``
        let tx = tx.clone(); // not sure if this is necessary or correct?
        thread::spawn(move || {
            for value in slice {
                let (iterations, max_value) = collatz(*value);
                let out = (*value, iterations, max_value);
                tx.send(out).unwrap();
            }
        });
    }
    for _ in 0..num_cpus {
        // --snip-- unwrap the output and do something with it
    }
} // error points to here: ``values` dropped here while still borrowed`

The compiler is giving error E0597: value dropped while it was still borrowed. I don't fully understand this, since values isn't needed (or used?) at the end of the run_multithread() function. I think an issue may come from chunking the vector since the chunks become the &[usize] slice type, though I couldn't think of a cleaner way to dynamically split up the list of numbers to be calculated (according to number of threads available). I think the fact I'm passing references to a vector into different spawned threads might be the issue.

I think move is necessary when spawning each new thread so that the sender, tx can be shared safely. I was playing about with the idea of creating a vector of senders (iterating through a range of 0..num_cpus and pushing to the vector) but I got nowhere with that method.

Do I need to apply some kind of atomic reference counting to protect the chunks from being shared unsafely? If so, how would I attempt that? If anyone has suggestions on cleaner methods of sharing/chunking a vector between threads—or if anyone has a better solution overall—I would be more than happy to hear them. Apologies for the verbose post, and thanks in advance.

The problem here seems to be that the slice you produce borrows the values, and then you move the slice into the closure being spawned on the threadpool. The borrow checker can't reason about when that closure will finish executing and be disposed of, and particularly, it can't tell that that will happen before run_multithread terminates and drops the Vec. If that were to happen, the slice references would be dangling, so it requires that the lifetime of values be "static", which in this context can be read as equivalent to, "forever."

possible solution: Rust Playground

Explanation: I think what you're trying to do is a case of "apply this function to each element in this vec and get the results", also known as the map operation. The rayon crate with its parallel iteration primitives is commonly used for this. Rayon's par_iter method will automatically and efficiently parallelize the task to the available cores, so you don't need to do the channels/atomics/synchronization stuff yourself every time.

1 Like

You may now wonder how rayon accomplishes what seems to be impossible: making disjoint slices of a vector accessible to multiple threads when that should not be possible as per borrowing rules.

The answer, I think, is unsafe code, most notably std::slice::from_raw_parts. This function allows you recreate a slice from a part of a Vec provided you managed to smuggle a raw pointer to the Vec's slice to the thread. Although raw pointers don't implement Send, you can wrap them in a struct you declare does.

Here's a playground that shows the idea. You are now responsible for ensuring that the vector stays put while the threads are operating on the subslices created via the raw pointer.

1 Like

They're not mutating, so it's perfectly fine to have multiple shared references everywhere.

That said, all you need for the mutable case is split_at_mut, or anything else that gives out disjoint parts of the vector (like any iterator over mutable references/subslices).

Plus scoped threads so the references can't outlive your Vec (for both cases).

2 Likes

Thank you all, both for the explanations and the playgrounds to demonstrate how such code works. It has greatly helped my understanding. Thanks @godmar for showing how to implement such a parallelisation using my current (unsafe) method.

I wasn't aware of the rayon crate. The neat implementation in @mmmmib's playground makes my use case appear embarrassingly easy. I'm excited to try it out!

1 Like

You may have overlooked that the example was in the context of multithreaded code where the reference was moved into a thread function's closure. This won't work even if immutable for the reason that the underlying object may be deallocated when it goes out of scope once the calling function returns.

In the playground I wrote I avoid this by ensuring that the exact number of messages is received so I know that none of the threads still accesses the slices.

That was the part about scoped threads. You don't need unsafe.

Interesting. How does crossbeam implement this without using unsafe?

Perhaps I should have been more precise -- the end user, the consumer of crossbeam (and std), doesn't need unsafe. The libraries take care of the guarantees, encapsulate the unsafe used to do so, and present a safe interface around them. Crossbeam will probably be part of std eventually.

I only skimmed the code, but it looks like they use dyn FnOnce with (an unsafe) transmute to extend the lifetime.

Is it conceptually possible to extend the borrow lifetime of the shared resource (Vec in this case) using Box::leak?

Yes, you could soundly leak the memory and end up with a static slice, if you don't mind the leak.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.