Java Concurrency JDK 1.6: Busy wait does better than signalling? Effective Java #51

Question

Joshua Bloch's "Effective Java", Item 51 is not about depending on the thread scheduler as well as not keeping threads unnecessarily in the runnable state. Quoted text:

The main technique for keeping the number of runnable threads down is to have each thread do a small amount of work and then wait for some condition using Object.wait or for some time to elapse using Thread.sleep. Threads should not busy-wait, repeatedly checking a data structure waiting for something to happen. Besides making the program vulnerable to the vagaries of the scheduler, busy-waiting can greatly increase the load on the processor, reducing the amount of useful work that other processes can accomplish on the same machine.

And then goes on to show a microbenchmark of a busy wait vs using signals properly. In the book, the busy wait does 17 round trips/s whereas the wait/notify version does 23,000 round trips per second.

However, when I tried the same benchmark on JDK 1.6, I see just the opposite - the busy wait does 760K roundtrips/second whereas the wait/notify version does 53.3K roundtrips/s - that is, wait/notify should have been ~1400 times faster, but turns out to be ~13 times slower?

I understand the busy waits aren't good and signalling is still better - cpu utilization is ~50% on the busy wait version whereas it stays at ~30% on the wait/notify version - but is there something that explains the numbers?

If it helps, I'm running JDK1.6 (32 bit) on Win 7 x64 (core i5).

UPDATE: Source below. To run the busy work bench, change the base class of PingPongQueue to BusyWorkQueue import java.util.LinkedList; import java.util.List;

abstract class SignalWorkQueue { 
    private final List queue = new LinkedList(); 
    private boolean stopped = false; 

    protected SignalWorkQueue() { new WorkerThread().start(); } 

    public final void enqueue(Object workItem) { 
        synchronized (queue) { 
            queue.add(workItem); 
            queue.notify(); 
        } 
    } 

    public final void stop()  { 
        synchronized (queue) { 
            stopped = true; 
            queue.notify(); 
        } 
    } 
    protected abstract void processItem(Object workItem) 
        throws InterruptedException; 
    private class WorkerThread extends Thread { 
        public void run() { 
            while (true) {  // Main loop 
                Object workItem = null; 
                synchronized (queue) { 
                    try { 
                        while (queue.isEmpty() && !stopped) 
                            queue.wait(); 
                    } catch (InterruptedException e) { 
                        return; 
                    } 
                    if (stopped) 
                        return; 
                    workItem = queue.remove(0); 
                } 
                try { 
                    processItem(workItem); // No lock held 
                } catch (InterruptedException e) { 
                    return; 
                } 
            } 
        } 
    } 
}

// HORRIBLE PROGRAM - uses busy-wait instead of Object.wait! 
abstract class BusyWorkQueue {
    private final List queue = new LinkedList();
    private boolean stopped = false;

    protected BusyWorkQueue() {
        new WorkerThread().start();
    }

    public final void enqueue(Object workItem) {
        synchronized (queue) {
            queue.add(workItem);
        }
    }

    public final void stop() {
        synchronized (queue) {
            stopped = true;
        }
    }

    protected abstract void processItem(Object workItem)
            throws InterruptedException;

    private class WorkerThread extends Thread {
        public void run() {
            final Object QUEUE_IS_EMPTY = new Object();
            while (true) { // Main loop
                Object workItem = QUEUE_IS_EMPTY;
                synchronized (queue) {
                    if (stopped)
                        return;
                    if (!queue.isEmpty())
                        workItem = queue.remove(0);
                }

                if (workItem != QUEUE_IS_EMPTY) {
                    try {
                        processItem(workItem);
                    } catch (InterruptedException e) {
                        return;
                    }
                }
            }
        }
    }
}

class PingPongQueue extends SignalWorkQueue {
    volatile int count = 0;

    protected void processItem(final Object sender) {
        count++;
        SignalWorkQueue recipient = (SignalWorkQueue) sender;
        recipient.enqueue(this);
    }
}

public class WaitQueuePerf {
    public static void main(String[] args) {
        PingPongQueue q1 = new PingPongQueue();
        PingPongQueue q2 = new PingPongQueue();
        q1.enqueue(q2); // Kick-start the system

        // Give the system 10 seconds to warm up
        try {
            Thread.sleep(10000);
        } catch (InterruptedException e) {
        }

        // Measure the number of round trips in 10 seconds
        int count = q1.count;
        try {
            Thread.sleep(10000);
        } catch (InterruptedException e) {
        }
        System.out.println(q1.count - count);

        q1.stop();
        q2.stop();
    }
}

Answer 1

In your test, the queue gets new items continuously, therefore the busy-wait does very little actual waiting.

If the queue get one new item every 1ms, you can see the busy-wait will spend most time burning CPU for nothing. It will slow down other part of the application.

So it depends. If you busy wait on an user input, that is definitely wrong; while the busy-wait in lockless datastructures like AtomicInteger is definitely good.

Answer 2

Yes, busy wait will respond more quickly and execute more loops, but I think the point was that it puts an disproportionally heavier load on the entire system.

Try running 1000 busy wait threads vs 1000 wait/notify threads and check your total throughput.

I think the difference you observed is probably sun re-optimizing the compiler for what people do rather than what people should do. Sun does that all the time. The original benchmark in the book may have even been due to some scheduler bug that Sun fixed--with that ratio it certainly sounds wrong.