ivy’s page

The free lunch is over! Herb Sutter writes an interesting and predictive article in the freshly arrived Dr.Dobbs Journal, claiming that computer programs won’t just go faster every year for free. Not anymore. Up until now, processor speed, harddisk space, memory capacity, everything about computers has doubled every one-and-a-half year (somewhere related to Moore’s law). But while we were all already anticipating our programs would run twice as fast in the near future, we won’t get this lunch for free.

While we were not really paying attention, the exponential increase in processor speed has already ended. There already was a 2 GHz Pentium in 2001, but right now we’re not passing the 3,6 Ghz instead of the expected 10GHz. Instead of increasing clock speed an important growth factor will be multi-core processors. To utilize this modern type of computing power in a single application, it should be multi-threaded. Multiple threads working together means watching out for concurrency issues (like race conditions, dead lock, and so on). So concurrency is going to be more important than ever.

In fact, Sutter believes that concurrency will become a first class concern for more developers and language designers. An “efficient language” will maximize cpu utilization of modern multicore cpu’s. I certainly don’t hope this will resurect Fortran. That medieval programming language requires you to type 7 spaces or so on every line, before you can write anything serious (sounds like assembler to me). And if you do, the compiler stops reading what you wrote after you typed 70 characters on that line, no matter how important.

But to keep to the point. I once followed a course called concurrency. We had a look at the correctness of multithreaded programs, looking at fairness and avoiding deadlocks. If you think that program verification doesn’t scale beyond 100 lines of code, you should try verifying concurrent programs. It is terribly complicated!

Luckily, most programmers don’t verify their programs for correctness (you would never get past 100 lines of code anyway) because a lot of things are “obviously correct”. Well, I can warn you: in multi-threaded programs, nothing obvious is as correct as it seems. Concurrency (and its implications) is a hard problem (NP hard ). Even if you understand all issues involved in concurrency, you should know the semantic memory model of the virtual machine you’re working with, or the write- and read instruction reordering of your cpu (which hopes it didn’t change the semantics too much). If programmers can’t “intellectually grasp” a program containing goto statements, multi threaded programs should never have been invented.

For instance, I will show you a piece of code I thought was completely correct:

class Singleton {
	private static Singleton instance;
	private Singleton() {
	}

	public static Singleton getInstance() {
		if (instance == null) {
			synchronized (Singleton.class) {
				if (instance == null) {
					instance = new Singleton();
				}
			}
		}
		return instance;
	}

This is a “smart” implementation of the singleton pattern. It is supposed to only create one instance while the class is in the JVM, and it does it the first time any thread calls getInstance(). The advantage of this implementation over one that just makes the whole method synchronized, is that it avoids the overhead associated with synchronizing all subsequent calls. By also checking for null within the synchronized code, it still avoids more than one instance creation. Isn’t that nice?

But it’s wrong!

It’s called double checked locking, and it does not work correctly for reasons we can’t intellectually grasp. A lot has been written about it, and it does not work.

To keep you from reading the details, some of the problems are:

• The compiler / JVM can rearrange code within synchronized blocks for optimisation.
• The compiler / JVM can move code into a synchronized block for optimisation.
• The compiler / JVM cannot move code out of a synchronized block.
• Threads can store local copies of variables that are not declared volatile or protected by a synchronized block, so may not see changes made by other threads. (And volatile has a known bug – it doesn’t appear to actually do anything).

There isn’t a real sollution to this problem, but maybe we can avoid some concurrency problems by reassuring:

• support for first-class concurrency-related language concepts (like in Java 1.5)
• libraries that are inherently thread safe
• and most importantly: system and programming frameworks that are set up to execute computations as independant as possible (like J2EE, or service based computing)

I’m sure we will here a lot about this subject in the coming years.