Atomic variable with locally non-atomic buffered updates

I was wondering if there's any crate doing this. Scenario: a paralell visit to a graph in which each visiting thread must update an atomic by adding a value to it, and you need to perform an update at every node. Contention is horrible. But sum is associative (modulo approximation errors), so each thread might update a local variable and all the local variables could be added to atomic variable. Contention would be in the order of the number of threads, not in the order of the number of nodes.

My ideal solution would be to have some kind of wrapper around an atomic variable. You can clone the wrapper, and a method add will increase a local variable inside the wrapper. When the wrapper is dropped, the local variable is added to the shared atomic variable.

You could do this with the threads returning a value and then folding it, but for a number of reasons in this case we would prefer to pass this "locally buffered atomic" to rayon methods of the type *_with and avoid the folding.

1 Like

In case anybody ends up here, please try our new mini-crate openmp-reducer.

UPDATE: this is actually a standard structure in OpenMP—it's called a reducer. Cilk (and thus Rayon) has reducer hyperobjects that are functional in nature and solve the same problem (you can find the reducers in Rayon's code), and they are used to implement folding on parallel iterators. But you cannot access them directly.

It is really a matter of two models of concurrency (OpenMP vs. Cilk). Most of the services provided by OpenMP are already available in Rust at the language level (sharing safely variable with threads, etc.), so it doesn't make much sense to have a version of OpenMP for Rust like Rayon is a Rust version of Cilk, but a few useful constructs of OpenMP are missing—in particular, reducers.

Link is dead, crates io claims there is no such crate.

It appears to have been renamed.

1 Like

Yep, I thought it would have been easier to find but I forgot to update the link.

1 Like