The Transition to Concurrency

Author: by Kristian Dupont Knudsen

Introduction

Concurrency is going to be crucial in the near future. The talk has been going for years, but now that Intel and AMD are actually starting to move that way too, you know there is something about it. A tremendous amount of articles such as this have been written on the subject lately, so I am not going to reiterate the evidence. Instead, I want to talk about what we are going to do - right now.

If you're a C++ programmer, you have surely been exposed to semaphore-based concurrency. Mutices and other kinds of locks are currently the most popular way of doing concurrency, despite the fact that it is one of the most difficult to use.

Furthermore, people often use them in a way that yields poor performance. Although you should not discard them completely, using semaphores should definitely not be the first and only option you consider when writing concurrent code.

Erlang and Friends

There are many ways to approach concurrency. Choosing an apt programming language is one. Erlang is a functional programming language designed specifically for concurrent programming.

Functional languages in general have the capability to excel in the concurrency area. A functional language such as OCaml is already famous for its optimizing compiler which makes it a language that is not just capable of achieving great performance - it actually does. This should make OCaml an obvious choice for concurrent programming.

But Why Change Language?

If you are interested in performance, chances are you are writing server code, embedded code or maybe game code like I am. And if that is the case, chances are that you are writing C or C++, and you are probably skeptical about other languages. In the end, they're all Turing-complete, right? So what could any language offer that you can't simulate?

Well you're right of course - there is nothing you can't achieve by simulating it. You can use or come up with design patterns that help you with everything. After all, design patterns are often described as language features that haven't (yet) been implemented. You can write object oriented code in C, simulating inheritance and virtual methods and everything but at the cost of increased complexity. Simulating functional programming in C is a pain. With C++ it is a slightly more bearable pain, but a pain nevertheless.

But even if you accept the fact that there may be better suited languages for the task, you may not have that option. No programmer is an island - you have to work with other programmers, you probably have management to respond to and changing languages is not a trivial decision. Plus, for many platforms, the C++ compiler is the only thing available.

At Flux Studios, we have been using C# for some scripting, assuming that Microsoft would provide support for the Xbox. Though they probably will, it seems unlikely that C++/CLI will be supported in the near future, which pretty much breaks the deal for C#.

(If your target platform is the VM of Java or .NET however, you could experiment with one of these hybrid languages: Scala, Nemerle or F#. They look quite interesting yet not too alien to Java or C# programmers).

Initiatives such an OpenMP may actually bring C++ somewhat up to the challenge, but even with that in your toolbox, you are best off understanding some of these paradigms that are well suited for concurrency.

Avoid State: Immutable Types

The key to functional programming, which happens to be a very good policy to enforce in general, is avoiding state. Mutable state, that is. Mutable state in software is like moving parts in hardware. It makes your code more vulnerable to external conditions, and it makes it harder to maintain.

To people with no experience with functional programming languages, this can be hard to grasp. Or rather, it can be hard to realize that there is a difference (it was for me, anyway).

In pure functional programs everything is immutable. This basically means that every variable isn't - it's a constant. There is no way to declare a C++ type immutable but what you can do is declare a variable const, which basically means that the type of the given variable is an immutable version of the type specified.

A Simple Example

Consider this simple color class:

class Color
{
private:
double red_;
double green_;
double blue_;
public:
Color(double red, double green, double blue) : 
red_(red), green_(green), blue_(blue) {}
double GetRed() const { return red_; }
double GetGreen() const { return green_; }
double GetBlue() const { return blue_; }
double SetRed(double red) { red_ = red; }
double SetGreen(double green) { green_ = green; }
double SetBlue(double blue) { blue_ = blue; }
void Multiply(double factor)
{
red_ *= factor;
green_ *= factor;
blue_ *= factor;
}
};

Fairly common style, I would say. Nice encapsulation even though you can read and write all private fields. But if you wanted to, you could easily introduce a contract by adding checks in the accessors and the multiply method.

To make this class immutable, we could change it like this:

class Color
{
private:
double const red_;
double const green_;
double const blue_;
public:
Color(double red, double green, double blue) : 
red_(red), green_(green), blue_(blue) {}
double GetRed() const { return red_; }
double GetGreen() const { return green_; }
double GetBlue() const { return blue_; }
Color Multiply(double factor) const
{
return Color(red_ * factor, green_ * factor, blue_ * factor);
}
private:
Color& operator = (Color const& a) {}
};

At first glance, the difference may not seem important. The Set* methods are gone and the Multiply method has changed a little. No biggie. But the real change is in the fact that this class is now immutable.

Once instantiated, you have no way to change the contents of the object. You can multiply the color by a factor, but this gives you a new instance. Also, the assignment operator has been declared private which means that it cannot be invoked from the outside, not even implicitly. This makes the class thread-safe even though it contains no semaphores.

You are forced to use it in a way that will work in multiple threads and you can be sure that it will never produce deadlocks or become corrupted by simultaneous access. Introducing a contract in this version means checking the invariant in the constructor - that's all.

Complex Classes and Data Structures

"You're asking me to copy everything every time I want to modify some value? I thought this was about gaining performance?!"

It is obviously costly to make deep copies, especially if you have complex classes and rely on classic mutable data structures. This is why you should consider using immutable data structures, sometimes referred to as persistent data structures.

Imperative programmers use arrays a lot but functional programmers tend to favor linked lists. If you have experience with functional programming, you have probably noticed that these guys seem obsessed with heads and tails, or CAR and CDR. Head simply means the first element in a linked list, and tail means the rest of the list.

Now, these simple operations have a great characteristic, namely that they give you a new value simply by copying a pointer, and without ruining the old value. The tail of an immutable list is another immutable list. And if you append this tail to a new head, you have a list with a new element without breaking the old one.

Of course, linked lists have well known disadvantages as well, such as the lack of random access. There are a number of tree structures such as red-black trees that come in handy in such cases. Currently, the standards have no concept of persistent containers and I haven't yet seen general-purpose libraries that supply them for C++, so you are somewhat on your own here. I expect this field to see a lot of action in the imminent years.

The Next Best Thing: Active Objects

If a piece of data needs to be shared, we need to make sure that access to it is sequential, even though it is accessed by parallel threads.

Erlang achieves this by the use of messages, which we can simulate in C++ with active objects. Active objects is a design pattern that merges the object and thread concepts into one. The object creates a new thread when instantiated, much like Erlang processes.

Instead of invoking methods on it, you send a message to it which goes into a FIFO queue. The object has a scheduler that continuously handles messages in the queue. Hence, the only thread actually accessing (or writing to, at least) the data is the owner thread. Other threads only tell it to do so.

If a return value is required, this is done using a future. A future is an object that will contain the result when ready. Paul Bridget has written a decent description of the active object design pattern with C++ implementation examples which can be found here.

Exception Safety

You may have noticed that besides opening up to concurrency, these coding styles share another property: they increase exception safety.

Making guarantees about exception safety is far from trivial. Also, game developers tend to avoid exceptions because of the performance overhead. This is a reasonable concern even though the inlining mechanisms in C++ help minimize it.

However, when you can form a reasonable invariant and convince yourself that it is maintained everywhere, you are not only on the way to exception safety but to more stabile code in general. Also, you will find that it lends itself to unit testing much better. Concurrent code, I find, is where unit testing generally fails to be of much help - at least for code based on semaphores.

However, an immutable class is easily tested and if it is really immutable, it will work concurrently as well. The same goes more or less for an active object.

Smells

"Ok, I kinda buy it. But in my current project though, that conversion could be done to maybe one or two percent of the classes", you may be thinking. (Why is it that without exception, when hearing of some interesting new paradigm or system you think "yeah, that makes sense. But it wouldn't apply to what I am working on right now"?)

Transforming imperative code into functional code is a major task and it may not be feasible for you. But you could have the ideas in mind next time you are going to write a class from scratch. There are a number of smells that you should be aware of.

1. Initialize Functions

I used to write these all the time. My idea was that an ideal class would have an initialize function which was called by the constructor but which you could also call yourself if you had to re-initialize it later on. I guess I thought of the class as a sort of container of contents, whereas I now see it more as a representation of the contents themselves.

Try to write your class so that it can only be initialized once: during construction. If you're writing C++, this also means that you don't lose the power of references which are immutable themselves (the actual reference, that is - not the referred variable). References can only be initialized with constructors.

2. Default Constructers

A default constructor means that the class is initialized with no information at all. This is rarely useful, and it usually means that you have an initialize function or a number of set-functions etc. for later initialization. An object that has been instantiated but not initialized is a zombie object and a liability to have lying around. Supply all required information to the constructor.

If your class is complex, the constructor parameter list might grow long. This is in itself a smell that your class is probably too complex, but there are situations where that's just the way things are. If you are in that kind of situation, you might be able to benefit from the Essence design pattern.

3. Public Validity Status Functions

If your class has a public bool IsValid() function or something similar, you are effectively leaving contract enforcement up to the user. This is bad for several reasons. A class with no mutable state needn't such checks except during construction. If the check fails there, an exception should be thrown so that the class is never instantiated. If you don't use exceptions, make an assertion and check the contents before constructing your object. This way, your class never violates the invariant.

If, however, your class has mutable state, adding such checks can be a good idea, only they should remain private. Read up on contract programming for in-depth discussion.

4. NULL-Pointer Checks

Don't code defensively. Many null pointer checks are just a form of contract validation which means that entry #3 applies here as well. If you feel that a null-pointer might have slipped in somehow, make an assertion. Not an if-statement. (Note that people often use null pointers as a valid "none" value which is perfectly fine).

5. Inheritance

There is no problem with inheritance itself. There may be uses for it in your design, but in general, it doesn't fit very well into a functional system. If a class is immutable, subclassing it would either violate this or simply supply more read-only methods.

6. Large Classes

Besides the obvious fact that a large class is probably also a complex class, large classes are an even greater problem if they are to be used in a concurrent environment. If your class is immutable, there is more information to copy around (but if your class is large, it is probably not immutable. The two things seem almost mutually exclusive). If not, there is a greater chance that the invariant can be broken and there is more data to keep consistent during transactions or semaphore locks.

StateAid

Even without semaphores, concurrent code is hard to debug and verify, mostly because you cannot determine the order of events by inspecting the code.

For this purpose, we have developed a small tool called StateAid that enables you to visualize execution in a non-linear fashion.

Conclusion

Concurrency is going to be part of most developers' lives in the future. C++ and languages like it are poorly suited for concurrency as it is today.

Developers have so far been spoiled by the fact that compilers have done a pretty good job of optimizing code for the evolving cpu architectures. However, traditional imperative code is hard to parallelize automatically so we cannot expect the same to happen with the new shift in hardware trends.

Semaphores are common and well-known, but using them correctly is difficult. If you want to prepare for concurrency, you could start the transition by becoming familiar with immutability, persistent data structures and active objects.