Archgrove - Implicit Definition

Writing code that makes good use of parallel execution techniques in most mainstream languages is not an easy task. Not only must you specifically write code that is safe for such execution, but then you have to manually deal with the laborious task of making it parallel – spinning up threads, waiting for them to finish, synchronising your results and generally making sure that thread A doesn’t tread on thread Bs toes, or that A and B don’t end up waiting for each other.

The upshot of this is that most people just don’t bother, an attitude that whilst understandable will shortly become untenable. The year on year advance in the speed of linear processing is dropping off, and most CPU architectures are leaning towards so called “multi-core” designs (i.e. cramming several processors on one chip). If you want your code to actually run any faster on these processors it darn well be better threaded, or you’re throwing away a large speed increase.

The change in attitudes will take time – oddly for a high tech field, most programmers have great inertia and many are reluctant to absorb new techniques. Inevitably, we’ll need gradual changes to help the transition so how can we make the tedious task of writing multithreaded code easier?

We could change language – systems like Erlang are naturally concurrent, and after a mindset change, your code suddenly takes advantage of parallel execution where possible without the labour involved in manually demanding it. We can also try and retrofit this sort of ability into existing languages through pre-processors and extra libraries – OpenMP is an example that’s making the rounds at the moment.

Alas, these techniques do require a mindset or architecture change (which we already know will take years). Designing for parallelism is not easy, and a good linear program rarely becomes a good parallel program just by wedging in a new library and crossing your fingers. This doesn’t mean we’re defeated though – surely we can think up a few tricks to get some easy freebies in our current systems. So in the spirit of finding one of these tricks, let’s diverge for a moment and consider what happens when you pass a parameter to a function.

“Mainstream languages” (by which I mean C(++), C#, VB.net, Java) provide direct support two parameter evaluation strategies – Call by reference, and Call by value. You know them both – if I call a function int a = 5; Foo(a);, by default the value of 5 is passed to the function as the first parameter – int is a so called “value” type. If I say String a = “Hello World”; Foo(a); then a reference to the string is passed in, rather than the value of the string itself. Whether reference or value types are employed depends on the types being used and hints from programmer but in both cases, the parameters are evaluated before the function is called. So, if I say Foo(ComputeSomething()), the result of the expression ComputeSomething() will first be calculated, then Foo invoked.

If we head off to less popular (but just as valid, and indeed arguably “better”) languages like Haskell, we gain Call by need. In this case, parameters are only evaluated when they are needed. If I said “Foo(ComputeSomething())”, then never used the parameter, “ComputeSomething()” would never be called. This is not only an optimisation (no wasted evaluation), but a significant property. I could pass in expressions that can never successfully evaluate and as long as they are never used, no problem will arise.

How does this fit into a little method for making parallel execution more accessible? Well, let’s introduce another strategy - Call by future. What if, rather than parameters being evaluated before they were called, they were evaluated whilst the call was going on? Of course, when the result of the evaluation was needed the function would have to sit and wait for it to finish, but if the function was working on something else before it needed the parameter, then the evaluation can continue in the background whilst the function is working. Graphically, we can view the execution sequences as follows.

It’s not a panacea – one still has to design for some of the problems concurrency introduces. However, it is easy to add to existing systems, and can be used safely without much effort.

So, how can we introduce this to our mainstream languages? After all, there doesn’t seem to be anything too special going on – the evaluation of the parameter is just run in a separate thread, and then the result is retrieved and used when needed. If we can claim control of parameter evaluation and then find a syntactically friendly way to wrap this concept, we’ll have a useful tool in the arsenal of weapons helping us fight the “cheap route to currency” battle. Tune in next time to see how we’ll add a version of Call-By-Future support to .Net 2.0.