The second part of building Suru is constructing a build graph. A build graph is almost certainly necessary in the context of multithreading because of the presence of diamond dependencies. Constructing a graph in Rust isn’t too bad, but does require a little big of fandangling.
Rc, Arc, Refcell, Mutex, RwLock???
I’ve seen some people get confused between the various constructs Rust has surrounding multithreading, but if you have a context in C++ multithreading it’s not very complicated.
Arc (Atomic Reference counted) and Mutex (read-write lock) are roughly
analogous to std::shared_ptr and std::mutex. An Arc object is shared
amongst various threads and objects, and is only destructed when all references
to it have been destroyed. A Mutex prevents multiple threads from accessing an
object. The difference between Mutex and std::mutex is that Mutex comes
with a RAII guard built in.
The code I have actually uses a RwLock, which permits multiple threads to read
at once instead of a Mutex, which would only allow one reader. Strictly speaking,
none of my program actually requires multithreading. By the time threads come
into play, the graph is already well defined and will not be mutated. Moreover,
by bounding the lifetime of the threads, it can be guaranteed that the graph
outlives the threads.
Unfortunately, there’s no decent threadpool library that supports thread scoping, so I decided to solve my issue by just leaking the memory of everything I need to share.
Build Graph
To construct a build graph, I go through every task and add the dependents as children. Tasks can get listed multiple times, making this a Directed Acyclic Graph. Currently I don’t have any code to detect dependency cycles, so any cycles will result in deadlocking.
After that, a build job is run for every task. Then it tries to build every dependent after that, and aborts if not all of the dependencies are built. By default all of the dependency roots are built first, so every dependency will be built eventually.
OnceFallible
Normally in Rust when you want to run something once over multiple threads, you
use the Once object. Unfortunately, Once does not permit rerunning depending
on if the function succeeded or not. Because of that, I had to write my own
lock called OnceFallible.
As the name would imply, OnceFallible is similar to Once, except the function
is permitted to be fallible and fail. If the function returns false, it does not
lock up, unlike Once.
Unfortunately, Rust’s standard library doesn’t expose a portable futex abstraction, unlike C++. This means that I had to use an OS mutex, which was less than ideal. When writing this I found the atomic_wait crate, but at this point it’s too late.
Conclusion
Building a graph in Rust isn’t that hard as long as you’re willing to accept some inefficiencies. Basic cases of multithreading such as mine aren’t too difficult as long as you wrap everything inside of thread-safe data structures.