We are already aware from previous tests that Mercury's current runtime parallelism system is not ideal. So the outcome if this test is not very useful and it should be re-evaluated later once the runtime system has been improved. That said the test is still interesting and the outcome was not what I was expecting.

This is part one, in a (probably) three part series. In this post I introduce the problem, the background information and the hypothesis

Mercury's parallel conjunction operator is declaratively commutative, but operationally it is not. The second argument is potentially executed in a new context and the first is executed immediately by the current context.

So a conjunction of independent conjuncts A and B such as 'A & B' has the same answer as 'B & A' except that in the first B is potentially executed in a new context while in the second A is potentially executed in a new context. This becomes important when one of these goals is recursive and the other one is not. If the first argument (the one to the left of the operator) is recursive it creates a call tree that branches to the left. Similarly if the rightmost call is recursive and the left isn't then the call tree branches to the right.

Right (default) recursion:
Left recursion:

Because most logic and functional programmers are trained to use tail recursion wherever they can most call trees branch to the right. However if the recursive goal is within a parallel conjunction then tail recursion cannot be used anyway, so we have the choice of making the call tree left-recursive if we think that there is a good reason to do so. Such a choice is important because it is recursive code that can consume non-trivial amounts of computational time in pure logic or functional languages.

The rationale and hypothesis goes like this: The parent context will be blocked after it executes the left conjunct but before the right conjunct finishes executing in parallel. This is unfortunate, because if we need to do some parallel evaluation later on we can not use this existing blocked context. Instead we have to create a new one. This new context will probably have the same problem as it may be created to execute the same procedure as a recursive step, it will fork of some work, finish its left-most goal and be blocking on the completion of the recursive goal.

At best the amount of parallelism used is simply limited by the number of contexts the program may be allowed to create. At worst, if we do not limit the number of contexts that a program may create, the program will very quickly run out of memory for the contexts' stacks.

Alternatively, by recursing to the left. The left conjunct very quickly forks off a lot of parallel work before blocking on the completion of that work. In this case only one context is blocked, N other contexts are created to handle the forked off work where N is the number of operating-system threads used. This is much more desirable because N is limited, and it does not limit the amount of parallelism that can be achieved.

Later we'll show the results and explain why this currently does not work as desired.