[concurrency-interest] Lock-free mania

Szabolcs Ferenczi szabolcs.ferenczi at gmail.com
Mon Apr 16 19:21:50 EDT 2007


On 16/04/07, Joseph Seigh <jseigh_cp00 at xemaps.com> wrote:

> You're making a lot of unsupported suppositions here.

Very well. Then, I give some support for my statements in the form of
some working test in the TMC framework:

    private class NonblockingCounter {  // class under test
	private AtomicInteger value = new AtomicInteger(0);
	public int getValue() {return value.get();}
	public int increment() {
	    int v;
	    do {
		v = value.get();
		for (int i = 0; i<10000; ++i) i = i+2-2; // delay for the test
	    } while (!value.compareAndSet(v, v + 1));
	    return v + 1;
	}
    }
    private class TUnitTestLockFree extends MultithreadedTestCase {
	NonblockingCounter cnt;
	@Override public void initialize() {
	    cnt = new NonblockingCounter();
    	}
    	public void thread1() {
	    for (int i = 0; i<1000; ++i) cnt.increment();
    	}
    	public void thread2() {
	    for (int i = 0; i<1000; ++i) cnt.increment();
    	}
    	public void thread3() {
	    for (int i = 0; i<1000; ++i) cnt.increment();
    	}
	@Override public void finish() {
            assertEquals(3000, cnt.getValue());
	}
    }
    @Test
    public void testLockFree_tunit() throws Throwable {
	final long t0 = System.nanoTime();
    	TestFramework.runOnce( new TUnitTestLockFree() );
	long duration = (System.nanoTime() - t0)/1000000;
	assertEquals(120, duration, 40);
    }

    private class BlockingCounter {  // class under test
	private Integer value = new Integer(0);
	public synchronized int getValue() {return value;}
	public synchronized int increment() {
	    for (int i = 0; i<10000; ++i) i = i+2-2; // delay for the test
	    return ++value;
	}
    }
    private class TUnitTestLockBased extends MultithreadedTestCase {
	BlockingCounter cnt;
	@Override public void initialize() {
	    cnt = new BlockingCounter();
    	}
    	public void thread1() {
	    for (int i = 0; i<1000; ++i) cnt.increment();
    	}
    	public void thread2() {
	    for (int i = 0; i<1000; ++i) cnt.increment();
    	}
    	public void thread3() {
	    for (int i = 0; i<1000; ++i) cnt.increment();
    	}
	@Override public void finish() {
            assertEquals(3000, cnt.getValue());
	}
    }
    @Test
    public void testLockBased_tunit() throws Throwable {
	final long t0 = System.nanoTime();
    	TestFramework.runOnce( new TUnitTestLockBased() );
	long duration = (System.nanoTime() - t0)/1000000;
	assertEquals(90, duration, 15);
    }

As you can see, the difference between the lock-free and the
lock-based algorithm is ca. 4/3 in performance in favor of the
lock-based one. Besides, the lock-based version is much more simple.
You can reconstruct the test if you like. I have checked it on a dual
core Windows XP, java 1.6

I have taken the lock-free counter fragment from a publication:

Java theory and practice: Introduction to nonblocking algorithms
Brian Goetz (brian at quiotix.com), Principal Consultant, Quiotix
18 Apr 2006
http://www-128.ibm.com/developerworks/java/library/j-jtp04186/index.html

I have inserted some delay into both of the algorithms. If the delay
is not inserted, there is a slight advantage for the lock-free
algorithm. That slight advantage would not compensate for the
disadvantage in complexity, however.

Is that some support for the suppositions?

Best Regards,
Szabolcs


More information about the Concurrency-interest mailing list