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.

I had the opportunity to attend the BBC’s live radio broadcast of “Any Questions” last night, which turned out to be an interesting experience (For those not in the know, Any Questions is a weekly political discussion show where the BBC round up politicians and other prominent public and business figures to have questions on recent news flung at them by the mob). On the practical side, it’s all very straightforward ; you’d never know the entire thing was being beamed live to millions of people. You arrive about an hour early and submit the questions you’d like to ask (if you don’t have any, that’s fine), sit and chat with your neighbours for 20 minutes then someone (in our case, a R4 continuity announcer) comes out to give pithy anecdotes and put everyone at ease.

After everyone’s actually listening, the producer comes out to explain how everything works and declares who’s questions were chosen - these people are then shuffled to the front row. Then the panel arrives, a test question is asked to make sure all the microphones work, and the show begins – they broadcast the news live into the room, and as soon as it ends, the panel and ambient microphones become live and the broadcast begins – all very simple really, and discreetly low tech.

It’s worth noting that if you don’t ask a question the most you can contribute is heckles or applause – the ambient mikes can’t pickup audience responses. Because my views on this week’s news are fairly commonplace, I didn’t bother to submit a question but rather strategically positioned myself at the back so I could observe the slice of the population that attended, and their reactions to the questions and answers. Alas, the demographic was exactly as I’d feared – the mean age must have been well over 60, and 95% conservative.

The height of the evening came when the woman who’d asked a reasonable question about increasing local resources before building new houses to solve the current house price crisis (whereby anyone who doesn’t already own a house can’t possibly afford one) got her right of reply. Her comments ran to the tone that “anyone without a house should just move north where the houses are cheaper” are so infuriatingly elitist and selfish that I almost ran down the aisle to cease the mike. Playing in local politics around here is such an exercise in frustration, it’s little wonder no few under 40 actually bother.

Regardless, it was a worthwhile slice of local political opinion, and my thanks go to the BBC for continuing to run this sort of program (in the face of “Celebrity Brothers Love XFactor live”).

In the vein of putting useful but obscure snippets here for Google to find, I’ve recently been having problems getting the excellent Boost C++ libraries to build under Windows. In short, bjam (the boost “make” style tool) crashes upon invocation, regardless of how you configure your environment.

After some digging, it transpires that this is a problem with the way Boost is using Microsoft’s C runtime (or a problem with the C runtime, take your pick). As part of the glob expansions, all files in your working directories are enumerated, which is (in general) fine. However, if you have a file outside of a “reasonable” date range, the MSCRT will assert, manifesting as a nice fiery explosion in the release build.

If you’re having this problem (and some mailing list archaeology indicates others were), check your working directories (current directory, c:\Windows etc) for files with daft dates; that is, earlier than 01/01/1970. It appears Blackbeard was stashing his looted files in my machine, as I had one lying around from the 1700’s in my Windows directory which was the ultimate cause of my build problems.

I’ve reported this issuelet to Boost, but doubt it’s severe enough to warrant code changes. Hopefully this post can save others some debugging time.