Amdahl's law and the root of all evil

Introduction

In the blog post "Why shared mutable state is the root of all evil." I was trying to explaining why it is important to use proper synchronization while accessing shared-mutable state in your concurrent programs to make sure they behave like expected. What I didn't get around to was talking about reasons why this synchronisation is so bad for performance and therefore the root of all evil for performance optimization.

Speedup

One performance measure is the speed-up of a programme. The speed-up basically compares the time a programme takes when executed one a single core to the time it takes to execute on multiple cores.

To calculate the speed-up (S2) on a dual core system simply measure the time to execute on a single core (T1) and divide to the execution time of on a dual core (T2).

For example if you are running a single-threaded program it doesn't matter how many cores your host system will have. The execution time will stay roughly constant and additional available cores will remain unused and idle. The speed-up therefore will be always one.

If you are running a perfectly parallelizable program on a dual core system the execution time will be exactly half the time than for a single processor system. In this case the program has a speed-up of 2. In cases where the program speed-up grows linear with the number of cores you add to the system we call it a "linear speed-up". That kind of speed-ups are the ideal.

In practise these kind of speed-ups are really rare and this is due to Amdahl's law.

Amdahl's law

What Amdahl's law basically says is that the maximal possible speed-up of a is determined by the part of the program which cannot run in parallel. For example this means if 50% of your algorithm are structured in a way they can't run by multiple threads then the maximal speed-up you will ever be able to achieve is 2. Say this algorithm would take 1 minute to execute on a single threaded system. If you optimize the heck out of your host system and let the algorithm run on with 100 threads you would be able to reduce the timing for the parallel (50%) part of the algorithm by factor 100. You still would be stuck with the single-threaded (50%) part of the algorithm which doesn't benefit from the additional threads. In the end the best you can ever achieve is a runtime of 30 seconds.

Below is a nice graph from wikipedia showing this law for different percentages of parallel proportions of the algorithm.

You can see that the different coloured graphs all flatten out after a while. Adding more threads to the equation doesn't result in any benefits any more. Even for an algorithm with 95% parallel proportion the maximal speed-up you can ever achieve is 20.

In practise having the algorithm run with a large number of threads is actually likely to reduce the speed-up again. This is due to the cost of multi-threading in the operating system like context switching.

What does this mean for my programs?

Like I tried to explain in my blog post "Free lunch for programers" the time of easy performance gains is over and only parallel programs will benefit from future advances in computer hardware. But because of Amdahl's law even parallel programs are very limited in its potential performance gains due to its non-parallel sections.

So in a way we have two conflicting forces: Safety and Performance. You need to use synchronization to make your concurrent programs correct and safe but by introducing synchronization you are installing so called critical sections which are essentially single-threaded and therefore harming performance.

By minimizing shared mutable state you can reduce the amount of synchronization used in your programs and therefore enable them to a higher performance.

Conclusion

Shared mutable state really is the root of all evil. Eliminate it wherever possible and your live as a developer will be a lot easier.

Free lunch for programers

In my blog post Why shared mutable state is the root of all evil. I commented on the fact that for the last 10 years the free lunch for programers was over and significant performance gains were only possible by developing concurrent programs.

Last night I came across Herb Sutter who described this idea for the first time in early 2005 in his article in the Dr. Dobb's Journal titled "The Free Lunch Is Over - A Fundamental Turn Toward Concurrency in Software". Credit where credit is due I thought I write a blog post about this article.

Herb really hit the nail on the head and it is actually surprising to find a 8 year old text about computer performance which is pretty much still up-to-date.

Here is a quote from the article:

Quick: What’s the clock speed on the CPU(s) in your current workstation? Are you running at 10GHz? On Intel chips, we reached 2GHz a long time ago (August 2001), and according to CPU trends before 2003, now in early 2005 we should have the first 10GHz Pentium-family chips. A quick look around shows that, well, actually, we don’t. What’s more, such chips are not even on the horizon—we have no good idea at all about when we might see them appear. Well, then, what about 4GHz? We’re at 3.4GHz already—surely 4GHz can’t be far away? Alas, even 4GHz seems to be remote indeed. In mid-2004, as you probably know, Intel first delayed its planned introduction of a 4GHz chip until 2005, and then in fall 2004 it officially abandoned its 4GHz plans entirely. As of this writing, Intel is planning to ramp up a little further to 3.73GHz in early 2005 (already included in Figure 1 as the upper-right-most dot), but the clock race really is over, at least for now; Intel’s and most processor vendors’ future lies elsewhere as chip companies aggressively pursue the same new multicore directions.

It is almost scary to see that even now 8 years later the article was first published the fastest Intel CPU is the i7-3970X which has 3.5GHz with 6 Cores and 15MB of cache. For a while the CPU can increase its clockspeed for a bit (turbo mode) but this happens only if the CPU temperature it not too high already. In other words there are still no common CPUs with 4GHz or more in the market.

However the trend to more transistors and multicore processors is continuing. Intel's forthcoming Xeon Phi uses the Many Integrated Core Architecture and will have up to 61 cores, 30MB of L2 cache and only 1.25GHz clockspeed per core.

Conclusion

To improve throughput, latency and utilization in a world of CPUs with ever growing number of cores applications need to able to run in parallel. As a consequence higher-level concurrent programming techniques like message passing, which don't rely on shared mutable, will become more and more important in the future.

Why double checked locking is broken?

Introduction

Yesterday I was talking to a good friend in the park and the topic of double checked locking for lazy instantiating of singletons came up. (Why we talked about this on a nice sunny day in the park is a separate issue, which won't be addressed in the blog ;)) At the time I was sure it was broken but I couldn't explain the reasons behind this strange behaviour. So I decided to have a look at it and write a quick blog about it.

How does double check locking look like in Java:

public class DoubleCheckedLocking {

    private static DoubleCheckedLocking singleton;
    private final String a;
    private final String b;

    private DoubleCheckedLocking() {
        this.a = "A";
        this.b = "B";
    }

    public DoubleCheckedLocking getSingleton() {
      if(singleton == null) {                       //1
        synchronized(this) {                        //2
          if(singleton == null) {                   //3
            singleton = new DoubleCheckedLocking(); //4
          }
        }
      }
      return singleton;                             //5
   }
}

The idea behind this pattern is that you want to lazy initialise your singleton but you want to avoid the performance penalty which comes from declaring the whole method synchronized. In the pattern the first thread would enter the method in line 1 and check that the singleton is null. It would then synchronize on the objects internal lock on line 2 and do a null check on the value of the singleton again on line 3. If the null check holds true the singleton will be initialised on line 5 finally. All further calls to the getSingleton method wouldn't see the singleton variable as null and would just return the cached instance. Unfortunately this pattern is not thread-safe and is considered broken. What could possibly go wrong in this situation? The problem sits on line 4. Assigning a reference to a variable and running the constructor is not an atomic operation. Two things need to happen:

• Run the constructor
• Assign newly created instance to variable (singleton)

The JVM is allowed to use out-of-order processing (see Why shared mutable state is root of all evil ) and can assign the reference to the variable before the constructors returns. That means that there is a window of vulnerability that singleton points to not fully instantiated object for a short while. For example if the constructor initialises internal fields a and b the unfinished object might have a initialised but not b. If a or b are final fields then it could actually happen that clients of singleton see them first as null and later properly initialised ("A"). It is only guaranteed that one threads sees the action of the other thread in proper order if you use synchronization for both reads and writes of the shared mutable state.

What can you do?

The easiest way to fix this is to not use lazy instantiation at all or synchronize the whole method.

public class ThreadSafeLoading {
    private static final ThreadSafeLoading singleton = new ThreadSafeLoading();
    
    public ThreadSafeLoading getSingleton() {
     return singleton;
    }
}

This works very well. The code to initiate a static variable runs during classloading time and before the class can be instantiated. The variable is declared final so it is ensured that all clients calling getSingleton will refer to the same instance of the class.

What if you must have the use lazy loading and can't synchronize the whole method? You can also declare the variable singleton as volatile. That way the JVM will bring memory barriers in place which will stop the possibility for out-of-order processing. Each write to volatile variable and each read from a volatile variable will create memory barrier and ensure that two threads will see actions in the other thread in proper order.

public class DoubleCheckedLocking {

    private static volatile DoubleCheckedLocking singleton;
    private final String a;
    private final String b;

    private DoubleCheckedLocking() {
        this.a = "A";
        this.b = "B";
    }
 
    public DoubleCheckedLocking getSingleton() {
      if(singleton == null) {                       //1
        synchronized(this) {                        //2
          if(singleton == null) {                   //3
            singleton = new DoubleCheckedLocking(); //4
          }
        }
      }
      return singleton;                             //5
    }
}

Why shared mutable state is the root of all evil.

Introduction

A while back I went to a talk by Martin Odersky introducing Scala. Martin is the lead designer of Scala and a very smart guy. You can have a look at the slides from the talk here.

He described how the effect of Moore's law (that the number of transistors on a reasonable priced CPU doubles roughly every 2 years) doesn't lead to higher clock speeds anymore since the early 2000s. The number of transistors is still doubling but the extra transistors are used to include additional cores per CPU and to increase L2 and L3 cache sizes. Before the 2000s programmers got a free lunch meaning that the performance of their programs automatically improved with each new processor generation. This free lunch is now over and the performance of a single threaded program hasn't improved much over the last 10 years. To be able to create programs with smaller latency or higher throughput parallel programming mechanism are needed. 

What I found really profound was this pseudo equation which Martin introduced:

       non-determinism = parallel processing + mutable state

This equation basically means that both parallel processing and mutable state combined result in non-deterministic program behaviour. If you just do parallel processing and have only immutable state everything is fine and it is easy to reason about programs. On the other hand if you want to do parallel processing with mutable data you need to synchronize the access to the mutable variables which essentially renders these sections of the program single threaded. This  is not really new but I haven't seen this concepts expressed so elegantly. A non-deterministic program is broken.

Why are parallel programs without proper synchronization broken?

There are a few different things which can go wrong when no proper synchronization policy is enforced: Race conditions, visibility issues and out-of-order processing.

Race condition

A race condition means that the outcome of an algorithm is depend on its timing and lack of influences from other threads. Lets have a lock at the check-then-act race condition. In Java it would look something like this:

public class BrokenMap<E, V> extends HashMap<E ,V> {
    public T putIfAbsent(final E key, final T value) {
        if (!this.containsKey(key)) {
            return this.put(key, value);
        } else {
            return this.get(key);
        }
    )
}

In the putIfAbsent method we first check if the element is part of the map already. If this is not the case we add the element. Otherwise we just return the existing element. This code works perfectly fine in a single threaded environment. In a multithreaded environment however a second thread could have jumped in between the two calls to containsKey and put and put its value their first. Once thread one is continuing execution again it would override the already existing value of thread two in the map.

For the method putIfAbsent to be thread-safe it needs to guaranteed that the two calls to containsKey and put are always run uninterrupted. They need to be atomic. The easiest way to ensure this to put both calls into a synchronized block which essentially renders the program single threaded in this section.

Another form of race condition is read-modify-write. In Java it would look something like this:

public class BrokenCounter {
    private long count = 0;
    public long increment() {
        return ++count;
    }
}

The class BrokenCounter has a method increment. This class is not thread-safe because the call to increment the counter ++count is not just one operation. Under the hood it is actually 3 operations.

1. Read the old value of count.
2. Increment the value of count.
3. Store the new value of count.

If a second thread interrupts the first thread somewhere between step 1 and 3 it would read the same value as thread one, increment it by one and store it back into the count variable. Once the first thread resumes it would also increment the old value and store it back into the count variable. The result of this would be a counter which has been only incremented by one even though it was called twice.

For the method increment to be thread-safe it needs to guarantee that calls to ++count will not be interrupted. The easiest way to achieve this is by putting the call into a synchronized block which essentially renders this section of the program single threaded.

Visibility

Visibility means essentially that an action in thread one is visible to a second thread. In a single threaded program when you write a new value to a variable it is guaranteed that all future reads to this variable will return the new value. In a multithreaded program such a guarantee doesn't exist. Lets have a look at the example program BrokenServer:

public class BrokenServer {

    private boolean stopped=false;
    

    public void run() {
        while(!stopped) {
            /* do something useful */
        }
    }
 
    public void cancel() {
        this.stopped = true;
    }
}

In this program a method run keeps processing stuff until it get interrupted by another thread calling the cancel method. It is a bid odd to imagine but the thread in the run method may actually never see the updated value of stopped. This is because the variable stopped may be cached in a local variable in the JVM or the value is resolved from the L1/L2 cache of the core rather than from main memory. To fix this we need to tell the JVM to include a memory barrier after writing the stopped variable and another one before reading the stopped variable. The memory barrier guarantees that all writes to the variable happen before all successive reads from the same variable (like you would expect in a single threaded program).

The easiest way to achieve this is to use a synchronized block around reading and writing the variable stopped which once again renders this part of the program single threaded.

Ordering

If you made it this far you must be truly interested in Java Concurrency. Lets have a look at one more case which is even more weird than the visibility issue above. The JVM and modern CPUs are allowed to execute code out of order if that helps with speeding up the code or improve memory access pattern.

Lets have a look at another piece of code:

public class BrokenOrder {
    int a = 0;
    int b = 0;
 
    public void assignment() {
        a = 1;
        b = 2;
    }
 
    public int getSum() {
        return a+b;
    } 
}

It is actually surprisingly difficult to reason about this very simple program. What would be the result of getSum if called in a multithreaded environment?

• Returns 0 if getSum runs before assignment
• Returns 3 if getSum runs after assignment
• Returns 1 if getSum runs after a=2 assignment but before b=3 assignment
• Returns 2 if getSum runs after b=2 assignment but before a=2 assignment

This last case can happen if the JVM / CPU decides to process the assignment method out of order. To prohibit this kind of non-deterministic behavior once again we need to use a memory barrier to prevent out-of-order processing. The easiest way to do this in Java is to use a synchronized block which renders the program single threaded in this section.

Conclusion

Shared mutable state and parallel processing doesn't go together at all. If you do not use proper synchronization you will create extremely difficult to find bugs and your programs are basically broken even if they appear to work just fine in most cases.