The recursive fork/join pattern (Concurrent programming in the Chemical Machine)

I show how to implement the recursive fork/join pattern in the Chemical Machine, using the Chymyst library, and compare this implementation with a standard Scala Future-based code.

I show two Chemical Machine recursive fork/join implementations, which are concise and very similar in their approach.

The first implementation is derived from straightforward reasoning about usage of molecules for handling concurrent data. However, this implementation creates a large number of new reaction sites (one per fork branch point), which leads to slow performance since the Chymyst library incurs significant overhead when creating a new reaction site. Nevertheless, this example illustrates how Chemical Machine code can declare new molecules and reaction sites within a reaction, which results in a recursively defined concurrent logic.

The second implementation of fork/join is based on the idea of replacing one of the molecules with a _continuation_, a function having the same type as the molecule emitter call. In this way, we avoid having to declare new reaction sites, and also avoid thread-switching: all reactions are scheduled through a single molecule within a single reaction site, and the "join" stage is executed on the same thread as the last of the "forked" subtasks. This implementation turns out to be significantly faster than the Scala Future-based benchmark.

Code for this presentation: https://github.com/Chymyst/Chymyst/blob/master/src/test/scala/io/chymyst/lab/ChymystForkJoin.scala

See also "Concurrency in Reactions", a tutorial book on `Chymyst` and Chemical Machine programming: https://winitzki.gitbooks.io/concurrency-in-reactions-declarative-multicore-in/content/

Main repository for the `Chymyst` library: https://github.com/Chymyst/chymyst-core/