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.

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.

Microsoft MVP Phil Weber is running a competition with licences for VS 2005 combined with one year of MSDN Premium as the prizes. My now student status rather rules out a purchase of the VS magnitude (espcially not Team System!) and whilst the express editions are nice, the features missing cut rather close to home (why, oh why, is unit testing only in the top of the range release?). “Well”, I thought “why not give this a go?”.

He’s after 100 words on why an entrant is a worthy winner. So, without further ado, here’s a poem. Hah! How many people saw that coming?

A Short Ode to the Trials of an Programmers Outmoded Toolkit

Whilst coding one day, to my great dismay,
I found myself growing nonplussed.
In mounting frustration,
I grabbed my workstation
and hurled it away in disgust!
“How much better”, I cried,
“could my work be inside
if my tools weren’t so covered with rust!”

“With version control, I could go take a stroll,
whilst continuous builds catch my quirks.
With more unit testing,
I could spend time investing
in specifications that work!
I might again feel
full of programming zeal
and less like a mechanical turk!”

Traditionalists (well, those even more traditional than myself) will note that this is a pretty poor “ode”, and it’s missing an entire stanza that should sit on the end (I had to cut it to get it into 100 words, you’ll be pleased to hear). I didn’t want to spend hours on it, so it also lacks some of the refinement I’d normally like to include (such as “quality” :)). Nonetheless, a fun exercise; if one can’t be eminently silly sometimes, real gravitas is much harder to reach.

Alas, I’ve not had time to write another article just yet but I’ll get around to it soon. I did, however, compile some statistics about the Decal project that you might find interesting. Everything here is likely an underestimate, as the project grows continuously.

Ah, the power of a committed community.

Well, the total of received answers to the questions in the last part was 2 which, whilst somewhat less than I hoped, just makes it more of an achievement to those that tried. I’m sure lots of you are sitting at home using your solutions as some form of abstract modern art, rather than wasting them on this site, and you’re right to do so!

Ahem. Let’s see what we got.

Bonus question 1 - What changes would you make to print “Hello Hello”?

This one isn’t too great a leap from what we did in the article – rather than call both our functions in succession, we’ll call the same one twice. The only minor roadblock is working out the offset to the function, which is 013 (extra credit if you just read it from the original source!). Hence the change you wanted (using the original “helloWorld.exe”) was to change byte 0409 to “13”.

Bonus question 2 - What changes would you make to print “Hello Decal”?

Another short intuitive hop, and one for the adventurous. We reason that if we can change the code, why can’t we change the data? Indeed, “Decal” has exactly the same number of letters as “World”, so one can just use the editor to replace the “World” in the data section (address 0838) with “Decal” and voila – success!

Bonus question 3 - We know the printing functions were generated from an object in our source C++. Which of the 3 blocks in the given assembly do you think belonged to that object originally?

The 3 given blocks were basically identified as being “The start of the big list”, “Print Hello function” and “Print World Function”. From our past discussion we know that objects “know about” one single concept – in our case, the concept of printing “Hello World”. As such, it’s unlikely that the object contained the original code that makes up the whole big list, and as such the last 2 of the 3 functions are the best candidates for being part of the object. End result, the functions beginning at addresses “00401020” and “00401040” are the right answer.

Anyone who deduced that, full marks! Anyone who read up to Q5 then used that information, also full marks (plus a nod for having excellent exam technique)!

Bonus question 4 - …Use the nop instruction to stop the program from waiting for enter before exiting, and explain what you did.

More deductive reasoning, the staple of the sport. We know the code prints “Hello”, then prints “World” before finally waiting for a keystroke. We can see in the big list that the call to print “Hello” is followed by the call to print “World” – and both are followed by another call that we didn’t discuss! This being the last call in the program, we can guess with good accuracy that it’s this function performing the wait.

Taking nop, we replace all the bytes of the call and the address it’s calling with the nop instruction code (starting at 040d, replace 5 bytes with “90”) and run the result. Did you see that? No more waiting! Fantastic!

Advanced bonus question 5 - …Produce a single C++ file that will compile to the given “helloWorld.exe” program.

Well, I can’t do too much explaining on this one – you’d have to have a solid understanding of C++ to even try it. The overall concept is that one sets up some source code using the hints in question 5 and populates it with the simplest code that performs the job. Then, by analysing the original “helloWorld.exe” assembly, you alter your code to use the external objects and functions that I used. Finally, a combination of binary comparison and detailed examination of both assembly dumps can be used to “tweak” your code to match.

The winner by a country mile is Portaren, who’s question 5 answer even caught the curve ball of a 32 byte buffer when a 1 byte would have been more logical. Ignoring formatting and minor (basically stylistic) differences, his code is so perfectly identical as to warrant full marks. Portaren, leave a comment or drop me an email if you want to pick your prize! An honourable mention also goes to “Long Duk Bill” for being the only other person to submit a solution. Everyone else who didn’t send anything or who’s just curious can now download the original project files and source from here (GPG signature file here). I’ve bundled in the compiled libctiny I used, but you can make your own from the original sources at this site.

Before we finish this series, I’d like to thank everyone for playing – despite growing more complex in nature, I hope what we went through was instructive and interesting. I’d love to have your comments on the style in general as well as what could be improved as I’d imagine I’ll write at least one more Decal focused article. Whilst I have the time, I also plan to start a series on the basic reasons for the existence of numbers (take that, newly increased visitor count!), as well as finishing my previous run on software design at some point.

Vade in pace,

Adam Wright (as Asriel)