Java - implementing a busy wait mechanism

Question

in my project I have until now "synchronized" multiple threads (each running the same type of Runnable) using a CyclicBarrier. In my case, using a CyclicBarrier turned out to be inefficient due to the high frequency of synchronizations, but a busy-wait mechanism might work faster. Here's what I got so far (some parts left out):

public class MyRunnable implements Runnable {

    private static AtomicInteger counter = null; // initialized to the number
                                                 // of threads

    public void run() {

        // do work up to a "common point"

        synchronized (this) {

            // decrement the counter and - if necessary - reset it
            if (counter.decrementAndGet() == 0) {

                counter.set(numberOfThreads);

                // make all the busy waiting threads exit from the loop
                for (int i = 0; i < threads.length; i++)
                    threads[i].interrupt();
            }
        }

        // busy wait until all threads have reached the "common point"
        while (!Thread.interrupted()) {}
    }
}

Unfortunately, this code performs even worse than CyclicBarrier. Here's a short, compilable example. Any suggestions on how to improve it?

These seems like the sort of question that's perfect for Code Review (http://codereview.stackexchange.com/), you tried asking over there? — Daniel Bingham, Jul 01 '11 at 20:46
why do you need the synchronized block if you are using AtomicInteger and synchronizing on the thread object itslef? — Asaf, Jul 01 '11 at 20:53
@Asaf: Now that you mention it, there's no real reason to. However, it's also slower without the `synchronized`. — ryyst, Jul 01 '11 at 21:05

score 3 · Accepted Answer · answered Jul 01 '11 at 21:02

3

Busy wait here will only work 'faster' if you have more processors then you have threads running. If you continuously spin on Thread.interrupted and are just consuming CPU time you will actually degrade performance dramatically.

What went wrong with a CyclicBarrier/CountDownLatch? That seems like a much better solution.

answered Jul 01 '11 at 21:02

John Vint

39,695
7
78
108

The threads do relatively few work between synchronization points, so `CyclicBarrier`'s overhead slowed everything down. (See discussion [here](http://stackoverflow.com/questions/6541104/java-multithreaded-code-does-not-run-faster-on-more-cores)) – ryyst Jul 01 '11 at 21:05

score 1 · Answer 2 · answered Jul 01 '11 at 21:38

1

How about something like this? This code has a concurrency bug (if one thread is slow between calls to counter.get()), but it should be solvable by having two counters and repeating this code twice so that the counters alternate.

if (counter.decrementAndGet() == 0) {
    counter.set(numberOfThreads);
} else {
    while (counter.get() < numberOfThreads) {}
}

Please post an example which can be compiled and which demonstrates the performance problem. Otherwise all answers will be just speculation.

answered Jul 01 '11 at 21:38

Esko Luontola

73,184
17
117
128

Look [here](http://pastebin.com/4J56v8ii). The problem is due to the workload being rather small compared to the number of synchronizations being performed. – ryyst Jul 01 '11 at 21:58
The problem with that code is that it's not doing *any* work. The JVM optimizes away the calculation, so all that remains is the synchronization. Understand this first: http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java – Esko Luontola Jul 01 '11 at 22:30
Even though the benchmark is flawed, this my code with two counters is 2-16 times faster (depending on the number of threads; I tested 1-4 threads on C2Q6600). But even it performs worse with more threads. That's to be expected, because synchronization always causes some overhead. – Esko Luontola Jul 01 '11 at 22:39
Here is an example of doing some real work (calling Math.sqrt) and distributing it over many threads so that it scales linearly: http://pastebin.com/433pwPkW – Esko Luontola Jul 01 '11 at 23:16

score 1 · Answer 3 · answered Jul 02 '11 at 00:20

It's hard to imagine that busy-wait loop would be faster than non busy one. First of all, in your code you are still using no less synchronization that you would need when using a CyclicBarrier (see below). Secondly, you have just re-implemented CyclicBarrier mechanism, on which Java developers have spend time and effort to optimize it for best performance. Thirdly, CyclicBarrier uses ReentrantLock for synchronization, which is apparently more efficient and faster than using synchronized keyword. So overall it's unlikely your code will win the race.

Consider this reference code:

public class MyRunnable implements Runnable {

    private static CyclicBarrier barrier = new CyclicBarrier(threads.length);

    public void run() {

        // do work up to a "common point"

        try{
          barrier.await();
        }catch(InterruptedException e){
          Thread.interrupt();
          //Something unlikely has happened. You might want to handle this.
        }   
    }
 }

In one run, this code will synchronize thread.length times, which is no more than in your version with busy-wait. Therefore it cannot be slower than your code.

The real cause of performance problem is that your threads do little work before they "meet", which probably means there is high thread context switch overhead as well as a lot of synchronization.

Can you re-consider the architecture? Do you really need to wait for all workers to "meet" at common point? Can you do a bit more work before their "meeting"? Have you tried setting thread count to a smaller number (=CPU/core count)?

Can you share a bit more about the purpose of the code and give a bit more detail?

As a side note. Reentrantlock aren't much faster if at all compared to synchronized. That is true with java 6 — John Vint, Jul 02 '11 at 17:52

trutheality · Answer 4 · 2011-07-02T07:06:30.443

What about wait/notify?

public class MyRunnable implements Runnable {

    private static AtomicInteger counter = null; // initialized to the number
                                                 // of threads

    public void run() {

        // do work up to a "common point"

        // need to synchronize for wait/notify.
        synchronized ( counter ) {
            // decrement the counter and - if necessary - reset it
            if (counter.decrementAndGet() == 0) {

                counter.set(numberOfThreads);

                // notify all the waiting threads
                counter.notifyAll();
            }else{
                // wait until all threads have reached the "common point"
                counter.wait();
            }
        }
    }
}

On a general note, if you're synchronizing so often that the barrier's overhead is a problem, it is suspicious: either you're doing work that's not worth multithreading, or you're synchronizing more often than you should be.

Your implementation lacks synchronizing on counter and thus throws `IllegalMonitorStateException`s. — ryyst, Jul 01 '11 at 21:40
You can't call `notifyAll()` nor `wait()` unless you are holding the object's monitor. — Esko Luontola, Jul 01 '11 at 21:40
@ryyst: Fixed. I don't usually use `wait()` and `notify[All]()` directly so I wasn't sure how the locking should work at first. — trutheality, Jul 02 '11 at 07:12

Java - implementing a busy wait mechanism

4 Answers4

Linked