Sunday, November 10, 2013

A Comparison of Simple Locking Strategies

I've been playing with locks again and made a comparison between 5 naive implementations. Putting aside arguments about how valuable microbenchmarks are, the results are interesting.

In each case, there were as many threads as CPUs on my machine (a 16 core Linux box) and all each thread wants to do is attain the lock, increment a counter until it reaches a point and release the lock.

Each test was run twice with the first result thrown away to allow the JVM to start up. There was also a 4 second pause before the run to avoid biased locking issues. Averages were taken over 10 runs of 2 000 000 iterations.

These are the five strategies:

SynchronizedIncrementer

Perhaps the simplest implementation is:

            synchronized (this) {
                counter++;
            }

a pessimistic lock approach.

AtomicReferenceIncrementer

Next is an optimistic lock approach with atomics:

            boolean set = false;
            while (!set) {
                Integer expected = counter.get();
                set = counter.compareAndSet(expected, new Integer(expected + 1));
            }

LockingIncrementer

Next is using Java's concurrent classes:

            lock.lock();
            try {
                counter++;
            } finally {
                lock.unlock();
            }

SpinLock

The next spins until a flag allows it to proceed.

            while (!atomicBoolean.compareAndSet(false, true)) {
                Thread.yield();
            }
            
            counter++;
            int myCounter = counter;
            
            if (!atomicBoolean.compareAndSet(true, false)) {
                throw new IllegalStateException();
            }

AtomicReferenceIncrementer

This uses an AtomicReference that holds an Integer and is otherwise similar to the AtomicIncrementer.

The Results

There isn't a huge amount between the strategies in this particular test:

                              Mean (ms) Standard Deviation
                              ========  ==================
AtomicIncrementer             2170      149.626535
SynchronizedIncrementer       2475      53.230630 
AtomicReferenceIncrementer    3319      275.069809
SpinLock                      3519      713.212030
LockingIncrementer            3690      244.545292

On my hardware at least, the optimistic AtomicInteger approach is fastest with the synchronized block offering the most predictable performance. However, there is not much between them.

The interesting thing is if you run the same test with just one thread, typically the results look like this:

Time took 7ms  for [SynchronizedIncrementer, counter = 2000000]
Time took 20ms for [AtomicIncrementer, counter = 2000000]
Time took 21ms for [AtomicReferenceIncrementer, counter = 2000000]
Time took 23ms for [SpinLock, counter = 2000000]
Time took 29ms for [LockingIncrementer, counter = 2000000]

Much faster and it's doing exactly the same amount of work!

Conclusion

Avoid multi-threading if you can help it. Use it only when it demonstrably speeds things up. Even then, try to architect your system so there is no contention in the first place.

No comments:

Post a Comment