Allow concurrent evaluation

[jwiegley]

Right now parsing is our slowest task, and yet parsing occurs during evaluation all the time due to import expressions. It would be nice if we could assign a pool of N workers (using the async-pool library), and perform these slow evaluations concurrently since none of them can have interfering side-effects. This should speed up the evaluation of nixpkgs considerably if there are many capabilities available.

To do this will need a few steps:

• Make Thunk.hs thread-safe by introducing a variable that causes other threads to wait for pending evaluations to complete. Right now there is a boolean flag in an IORef; it might be sufficient to just turn this into a trinary flag in a TVar.

• Create MonadConcurrent to abstract when concurrent evaluation is possible. It wouldn't be for the symbolic evaluator, for example, but would for an evaluator that runs in IO, such as Lazy.

• Replace the calls to traverse that happen in Exec.hs for NList and NSet to instead use a new concurrentTraverse method defined in MonadConcurrent, which for IO would be implemented by calling Control.Concurrent.Async.Pool.mapTasks <group> and for pure evaluation would just call traverse as before.

Pinging @ryantrinkle, who requested this feature.

[Anton-Latukha]

Linking the #804 here, Obsidian guys seems got a better idea of achieving non-blocking parallelism, their Scopes and Standart Thunk relates to the question.

And I also started to look at the question as to non-blocking parallelism, which I expressed in: #879 (comment)
The gist of it: Nix is pure language - hence referential transparency, hence naturality for its diagram chasing - paths of evaluation always commute if the end point for them exists. Since what is evaluated (pure language) - gives is locally and globally referential transparency - it gives a lattice of actions that always commute. In other words - it is a propagator.
So expression in parsing & evaluation stages represent lattices that are stages for propagator processes.

Additionally, expression blocks as long as they parsed semantically correct - are an abelian (commutative) monoid (also because of the language). All those guarantees are already provided for us and kept by the reference implementation.

The only thing that is not provided for us - is the definite termination, but it unsolvable anyway for the HNix case, so the best that we can do is 1. some basic termination rules for abnormal computations, aka the opaque rules that already currently in place.

And after all that maybe additionally pick some minor windmills fights, why windmill - since of the halting problem and Edsger Dijkstra already talked about the complexity of loop detection, loop detection is famously complex & nonfull thing - so maybe doing some basic loop detection mechanism on the side, while well, opaque runes must be enough in this case anyway. Maybe have some sort of action connections matrix built (Adjacency matrix) during evaluations and as CPUs are good at matrice multiplication - & multiply it with itself several times, to see if it loops inside itself. But I think we should go into associative-commutative parallelism and rely on opaque termination rules, tune them and live like that until more work on termination detection would be needed (if any).

Because all guarantees are already provided - we need to think about how to manage the position to gracefully lay the code on that unseen guarantees structure and allow those already existing kept guarantees to show the proper design of the algorithm, I currently have no idea how to do it, probably when HNix would be open for parallelism - possibility would reveal itself.

⬆️ But that is a look into the future currently.

---

Create MonadConcurrent to abstract when concurrent evaluation is possible. It wouldn't be for the symbolic evaluator, for example, but would for an evaluator that runs in IO, such as Lazy.

Replace the calls to traverse that happen in Exec.hs for NList and NSet to instead use a new concurrentTraverse method defined in MonadConcurrent, which for IO would be implemented by calling Control.Concurrent.Async.Pool.mapTasks <group> and for pure evaluation would just call traverse as before.

Also falls into concurrency/parallelism. Also, currently, a number of approaches were developed, as monoid-subclasses, abelian, STM, and other concurrency/parallelism solutions.

As Nix is an abelian monoid - I'd looked into what law properties can be established through monoid-subclasses and abelian and others before thinking about implementations, as even in doing custom implementations - it is easier to rely on already provided basis properties, moreover quality of the code and its maintenance over time.

---

Currenly:

• what Obsidian implemented is important in this regard WIP: Improvements to make it easier to implement runners other than StandardT #804 and onward.
• it is an associative & commutative monoid propagator. Find and implement the properties. And onward field already established & provided the approaches already think about cross-thread results sharing.