Episode Four: Going safely parallel

So far we have incrementally developed

  • a general solution for playing board games with mutual moves,

  • a specialization for the rules of tic-tac-toe, and

  • an extra forecast feature to see how the computer thinks that the game will develop.

All that code turns out to be purely functional. There is not an assignment in the code, no state that needs to get updated, and therefore also no shared mutable state that could impose any issues when going parallel. Furthermore, there are no side effects in the code.

Since we have just written the code, we remember that we have not written anything impure. But we can even be sure about the purity characteristic without any prior knowledge of the implementation: the type system tells us so!

Map is pure

And this comes so: the main entry point to our solution is a call to the map function and the type signature of map is

The signature of map
map :: ( α -> β ) -> [α] -> [β]

Let’s start with the first argument ( α → β ).

It means that the first argument to map is a function from any unconstrained type α to any unconstrained type β. Let’s call that function f. The map function applies its argument function f to all elements of a list of α values to produce a list of β values, not knowing any specifics about f.

In our case f happens to be (probe lookahead). We are probing each board, looking no further than the given lookahead where probing can be either the valuation of the board or the detection of the forecast.

Mapping any function f over a list of α values cannot possibly perform a side effect. The closest possibility would be a specific function f that returns an IO action as type β. But even in that case, the IO action is only created, not performed. No implementation of map would ever be able to perform such an action since map cannot assume anything about β - particularly it cannot assume that β is an action.

In other words: the signature of map asserts purity of map f and the Frege type system enforces this down the whole call chain! We do not have to go back and check the code ourselves for possible purity breaches nor can any maintainer accidentally undermine our foundation through subsequent changes.

Now, what happens if we go parallel and use mapP (the parallel version of map) instead of map? Here is the type signature of mapP:

The signature of mapP
mapP :: ( α -> β ) -> [α] -> [β]

That is exactly the same! The whole line of argumentation about purity of map f equally applies to mapP f!

Let that sink in for a minute.

Parallelism as an increment

With Frege, we can again apply a non-intrusive increment: from sequential to parallel execution in an absolutely safe manner. Purity and its handling in the type system makes that possible. In all other popular JVM languages this would have been an immensely intrusive change (even if old code was not edited at all - changing its mode of operation is intrusive) with a huge potential to introduce hard-to-detect errors.

And again, we were able to apply this non-intrusive increment without having planned for it. We just did what is usual in Frege and it turned out to just fit.

We can almost always safely go from map to mapP.

There are two considerations, however, that we should apply before blindly making all calls to map parallel:

1) Granularity We applied parallel execution on the top-most layer of the evaluation only, not down to all splits of possible boards. That is a usual performance concern for data-parallel code where we weigh the relative overhead of thread scheduling against the size of the unit of work.

2) Infinite data structures Parallel execution makes usually no sense to work lazily since new threads should start working eagerly to have the result ready when requested. But that approach would never finish when applied to infinite data structures.

But those considerations are fully inside our mental context when applying our increment. We are in the position to decide about granularity and we know that possibleMoves is a finite list. It is a reasoning that is local to one single increment.

For the geeks

The parallel execution in mapP would have no effect at all if the usual lazy evaluation strategy was applied. Each parallel function application would return immediately, leaving an unevaluated expression behind - for later, lazy execution.
The implementation of mapP avoids this trap by enforcing the weak-head-normal-form (WHNF) of each element in the result list.

My personal experience was very strange when I applied parallelism to the tic tac toe game. I went from map to mapP,  let the code run, and enjoyed the speedup. Then I fell back into my old habit of paranoid concurrency thinking: what could possibly go wrong?

And for the first time ever in such a situation, I couldn’t think of any possible issue.

results matching ""

    No results matching ""