timburrell.net

I’ve noticed over the years that for the majority of computer scientists design is something we either love or hate. And however unfortunate it may be, I think either way design is usually a bit of an after thought, or at the least it’s a moving target. High level design can usually be done in advance, but for large projects the design almost always needs to be tweaked on the fly as new issues crop up.

I, personally, am in the camp that loves design. I have seen some beautifully elegant code written by crazy geniuses <cough>John Carmack</cough> that was… less than well designed, but most of the programs I admire (of which I also have access to the source code) generally have equally admirable design philosophies.

But, this isn’t a perfect world. It’s a bit sad that we still haven’t figured out a way to hook computers directly to our brains, so we’re left with using terribly inefficient and somewhat cumbersome programming languages to wrangle these computation machines into doing something close to what we wish them to. Of course they have the irritating habit of doing exactly what we tell them, rather than what we mean.

I bring this point up because although programmer skill is definitely one issue, languages themselves suffer from design issues, and I’d say a good majority of the time that’s spent struggling with design is actually spent struggling with a language’s design. It’s the same battle artists have fought for years: I’ve got a beautiful image in my head, now how do I get this paint brush to paint that image on this canvas?

For this series of of articles I’m going to pick on C++. Love it or hate it’s so prevalent that even if you’re one who spends most of your time with more modern languages like Ruby, Python, and Haskell, you’re still likely forced to bust out some C++ now and again. And for those of us who spend 40 hours a week (or more) with C++ and love it, I’m sure we’ve all got a fairly lengthy laundry list of problems that don’t necessary come out as clean as we’d like when we put them into the crazy kitchen sink that is C++. So basically, I’m going to pick on C++ because it’s easy — that and the fact that I’m a C++ compiler developer by day, so I may have a somewhat unique perspective on the language.

For this first Effective C++ installment I’m going to start off slow. I’ve got plans to dive into some more advanced things like template metaprogramming and some of the upcoming C++0x features down the road, but I thought first I’d tackle a problem that’s plagued me more than once, and in more languages than just C++ over the years. It’s also an issue that I’ve seen some fairly… wacky (I’m being nice)… solutions to by students and even in some open source code in the past: it’s the joyous design problem known as the cyclomatic dependency.

But before I begin let me just say: there’s no judging here. Say what you want, but I know as well as the next, given certain circumstances sometimes a goto, or a Duff’s device can actually be an elegant solution, so I’m not going to sit here and say “rethink your design”, I’m going to trust that you have, and move on. Fact is, you’ve run into an issue where you need to have class A depend on class B, and class B on A. Let’s look at an example:

Here is NetworkServer.hpp:

#include "NetworkConnection.hpp"
 
class NetworkServer {
        list<NetworkConnection> mConnections;
};

And here’s NetworkConnection.hpp:

#include "NetworkServer.hpp"
 
class NetworkConnection {
public:
	NetworkConnection(const NetworkServer& server) : mServer(server);
private:
	NetworkServer& mServer;
};

You can immediately spot the issue. Now, of course, this simplistic problem could be reworked in any number of ways to avoid the cyclical dependency, but real world problems are often much more complex and thus harder to refactor, yet often come down to some variation of the above.

Fortunately C++ actually has a fairly decent solution to this problem: the forward declaration. It’s simple, and it works well, but before looking at it, let me say that I’ve seen enough work arounds to know there’s plenty of C++ programmers out there who don’t know what a forward declaration is, or if they do, why it’s useful, or what the C++ compiler actually does with it.

One of the solutions I’ve seen to this is to use generic programming, or in C++ speak: templates. We could define NetworkConnection like so:

template <typename T>
class NetworkConnection {
public:
	NetworkConnection(const T& server) : mServer(server);
private:
	T& mServer;
};

This works, but what if someone instantiates NetworkConnection with a type that doesn’t provide the same methods as NetworkServer — broken design! Not only that but if you’re using NetworkConnection as a base class it might not make sense to have it templated because you might need to cast from it to a super class, and you might not know what it was instantiated with at casting time. This is actually a design flaw with C++, and is being addressed with the upcoming C++0x language feature known as concepts (which I intend to look at in detail in a future installment).

There’s also a non-template way to deal with this issue, however, and it’s something I’ve seen used a lot, especially by students (who are, through no fault of their own, ingrained in the java-single-inheritance-heavy-on-the-interface style of design). You simply make class A inherit from an abstract base class that provides pure virtual function interfaces to the methods needed by the other class caught in the cyclical loop. Then pass the abstract class around rather than its implementation and voila, dependency avoided:

NetworkServerInterface.hpp:

struct NetworkServerInterface {
	virtual void someFuncA() = 0;
	virtual bool someFuncB() = 0;
	...
};

NetworkServer.hpp:

#include "NetworkServerInterface.hpp"
#include "NetworkConnection.hpp"
 
class NetworkServer : public NetworkServerInterface {
public:
	void someFuncA();
	bool SomeFuncB();
private:
	list<NetworkConnection> mConnections;
};

NetworkConnection.hpp:

#include "NetworkServerInterface.hpp"
 
class NetworkConnection {
public:
	NetworkConnection(const NetworkServerInterface& server) : mServer(server) { mServer.someFuncA(); }
private:
	NetworkServerInterface& mServer;
};

This works, and can be a good technique to enforece certain design principles (it’s easy to only allow specific objects to use the NetworkServer in exactly the way you want by only providing a subset of functions in the abstract class definition), but it’s not without its shortcomings. Firstly, significant development effort is wasted by requiring the interface class and main class be kept in sync. Then there’s the overhead of virtual function calls that should be considered. For a time critical section of code this scenario should be avoided like the plague.

Another possible solution is the dreaded void *. It’s a holdover from the days of C programming, and much like the goto, is generally frowned upon in modern OO design. The problem with using a void pointer is if you need to use the member variable as its actual type then you have to cast it back and you’re left with the same cyclical dependency because then you need to include the casted type’s header file again.

Fortunately with C++, since the headers no longer include one another, and the translation unit is often broken into separate header and source files, you’re free to include any headers you wish in the parts of the translation unit that contain the implementation definitions (the cpp files). So, you could store the variable as a void pointer and cast from it whenever you need to access its actual type’s methods, ie:

NetworkConnection.hpp

class NetworkConnection {
public:
	NetworkConnection(void* server);
private:
	void* mpServer;
};

NetworkConnection.cpp:

#include "NetworkConnection.hpp"
#include "NetworkServer.hpp"
 
NetworkConnection::NetworkConnection(void* server) {
	mpServer = server;
	static_cast<NetworkServer*>(server)->someFuncA();
}

Yep, this works, but it’s nasty ugly, and kills proper design because you can’t really return the void pointer from public facing functions in any safe way. Normally I wouldn’t even bring this up, but it is an option, and it’s also a precursor to the forward declaration.

Essentially with forward declarations you’re telling the compiler that you want to use a class without knowing anything about it. In compiler terminology basically you’re doing namelookup, and that’s about it. You can’t use any objects of that type until you give the compiler the details it needs. This is fine though, because you can make sure to only use the variable after its class definition is available (ie in out of line member functions, or in the implementation part of the translation unit). Here’s an example:

NetworkServer.hpp:

#include "NetworkConnection.hpp"
 
class NetworkServer {
public:
	int someFuncA() { return 0; }
private:
	list<NetworkConnection> mConnections;
};

NetworkConnection.hpp:

class NetworkServer; // Foward declaration
 
class NetworkConnection {
public:
	NetworkConnection(const NetworkServer& server);
private:
	NetworkServer& mServer;
};

NetworkConnection.cpp:

#include "NetworkConnection.hpp"
#include "NetworkServer.hpp"
 
NetworkConnection::NetworkConnection(const NetworkServer& server) : mServer(server) {
	mServer.someFuncA();
}

Not only does this solve the cyclical dependency issue, but it speeds up compilation times as well. I’d even go as far as to say it’s good practice to use forward declarations wherever possible, which is in most header files if you’re writing a traditional application or a library that’s not meant to be completely header based.

So there you have it, a look at how to deal with cyclical dependencies in C++.

I’m thinking that the next topic will be a multi-part series on the upcoming variadic templates feature of C++0x since you can already play with them via gcc >= 4.3. Plus my goal is to eventually focus on more metaprogramming type stuff, and variadics are going to make that a lot more fun.

It’s been about a year and half since I started actively using D — I’ve written (and maintained) a couple of small commercial applications in it, and taken maintainership over a couple of D related open source projects, but most of my experience with the language comes from using it to write my thesis project in — around 30,000 lines of code spread over 100 source files. Not exactly a huge project, but large enough to get a good feel for the language.

First of all the good: the bottom line is, D is a great little language, and I say little because in many ways it’s a lot simpler, and less complicated than any of the other system level object-oriented languages that it competes with (C++). This doesn’t mean that D is any less valuable though — in fact much the opposite. D’s inherent simplicity is by design. It’s pretty clear by looking at the language spec that the idea was to take the best elements of some languages, throw out the rest, and add some of the missing features that we all wish we had (built in strings, optional garbage collection, modern language features, etc).

And by modern language features, this is the kind of stuff I’m talking about: mixins, lambdas, variadic templates, lazy evaluation, delegates, nested functions, anonymous unions, array slicing, contract programming, handy statements. Basically, much of C++0x’s upcoming feature set, and more.

So does D deliver? The answer yes, a resounding yes in fact. In terms of core language design and features, D provides exactly what many of us have been yearning for for years — a system level language that is on par with (or better than) modern scripting languages (such as Python, and Ruby) in terms of development speed, provides the language features we all should have by now, yet compiles to native code that can be as efficient as C++.

The panacea of programming languages? Well… no, not quite. Unfortunately the story doesn’t end there.

The first problem is a major one, and I don’t want to downplay it because as it stands it’s enough of an issue that no development house could even consider D as a prospective language, but fortunately it’s something that should get better over time. The issue: compiler bugs, and plenty of them. Some of them are small, some of them are huge, but there’s enough that they add up to a serious problem.

The bugs I ran into ranged from little things like floating point printing errors, all the way to compiler segfaults. Being that D is so young and the compilers aren’t close to maturity yet, any project complex enough is basically guaranteed to run into problems with either of the existing compilers, and my thesis project was no exception. Fortunately there are two major compilers that use separate optimization paths (a frequent culprit in the official digitalmars compiler) so one at least has a contingency option, but unfortunately, they share the same front-end, so they tend to exhibit some of the same bugs as well.

There’s also some serious performance issues with both compilers. For example, if you look at the assembler output of either of the compilers you can see them doing the same wasteful, redundant memory copies when doing something simple like returning a struct from a function. The only work around to this compiler bug is to do ugly things like return values from functions using by-reference function parameters.

Take a moment to think about the case where you can’t return values from functions — design goes out the window, along with readability and maintainability, not to mention ease of porting to other languages (should the desire arise). It extends further than that though — it means, for example, using custom foreach iterators to do a simple iteration over a collection of stack allocated structs becomes so inefficient that you end up having to put regular for loops in places where they really shouldn’t be.

Basically these “little” compiler issues make it difficult to consistently employ OO design principles, and use all of the nice modern language features that made the language so attractive in the first place. And after discovering these issues, along with their associated workarounds (wasting time discovering that your program’s poor performance is due to the compiler and not your code), you’re basically left with either a slow, inefficient executable, or ugly, unmaintainable code written in a language that was specifically designed to produce clear, concise, elegant code.

It’s a terrible shame to have a few minor problems result in such broad consequences, but these issues are all things that can be fixed, and they’re not nearly as prevalent as this post makes them seem. In fairness, given how new D is, the overall stability and quality of the available compilers is actually quite impressive. The language itself shouldn’t be judged on these compiler issues, but it’s important that people who may be considering adopting D be aware that there are problems with the compilers before forging ahead.

The next big issue isn’t technically related to the language itself, but is still a problem because it’s one of the root causes of much of what’s stopping D from living up to its potential. The heart of the matter is that D is currently going through some growing pains, and project leadership isn’t keeping up with the community.

Right now the D community is split between two incompatible standard libraries (Tango, and Phobos) that offer up different design philosophies, and although the majority of the community uses one library (Tango), it’s not the official standard library. This tends to create confusion for new users, and forces people to adopt one library or another, or library designers to write and maintain two sets of sources — neither being optimal solutions.

To come back to the issue of the compiler bugs — in other projects such a situation might not be as much of an issue, but many of the compiler bugs have been sitting idle in the D bug tracker for many months, and many releases. It appears as though the project is transitioning between a small niche language, to something that might even be getting close to being considered mainstream (D is currently 12^th on the programming language popularity list, and still moving up), so it’s understandable that some project leadership issues might crop up along the way.

Regardless of how understandable these growing pains may be, it’s still something that the project maintainers, and the D user community, are going to have to deal with before the language can really take the next step in terms of public acceptance.

There’s also one final problem with the language, or rather, the upcoming D2 language spec, and as big as all the other issues are this is actually the biggest thing that’s keeping me from continuing to use D on future projects. We all know that multi-core systems are the defacto standard these days, and although we’re starting to get a handle on developing tools to help programmers deal with the almost always non-trivial task of writing parallel code, we’ve barely even scratched the surface of what compilers and runtimes can do to help regular joe-six-pack-programmer effectively, and easily, design algorithms that take advantage of today’s processors.

Given the current state of affairs in terms of SMP and distributed development, and that there’s a new revision of the D language in the works, D has a great opportunity to assert its intent to be a player in the upcoming multiprogramming language war. But nothing is in the works. The D team isn’t actively working on providing any inclusion of a modern parallel programming paradigm for D2, which means it will likely be pushed back to some future release of D. This is unfortunate, because I know a great many developers are waiting for tools to help them deal with parallel programming (even if they don’t know they are).

Aside from Erlang and other more obscure functional languages, right now C++ is still one of the best choices around for parallel development. With the resounding success OpenMP has seen in the last few years, and with C++0x on the horizon and the new OpenMP 3 being recently released it looks like C++ is going to continue to be the language of choice for most system level and computationally expensive tasks.

Neither D, nor the upcoming D2 spec, give developers anything beyond raw threading (plus some critical section synchronization and resource locking type mechanisms, along with a controversial const system), but definitely nothing in the way of a modern parallel programming methodology. It’s another unfortunate oversight that takes a language that should be an ultramodern successor to nearly all current languages in its class and puts it years behind C++, and even Fortran (both of which have OpenMP at their disposal), and let’s not even try to make a comparison to other languages like Erlang, JoCaml, Parallel Haskell, and friends.

I really wish I could recommend D as a natural successor to C++, but given all the issues it’s currently facing, I just can’t. It’s simply not there yet, and I fear, given it’s current direction, that it never will be. I still think it’s a great project, and I hope that it works out because I’d like very much to see it succeed, because I think a strong competitor to the multi-paradigm system-level language would be a great boon to the software development and computer science communities.

I’ll definitely keep watching D to see what happens in the future, but I likely won’t be using it for any more projects until they can iron out the compiler stability and efficiency issues, and implement some reasonable multiprogramming method.