CODEWITHSUNDEEP
javamultithreadingconcurrencyqueueblocking
Cedric Martin
Cedric Martin

Reputation: 6014

What is the latency of a BlockingQueue's take() method?

I'd like to understand how take() works and if it's a suitable method to consume "fastly" elements that are pushed on a queue.

Note that, for the sake of understanding how it works, I'm not considering here the observer pattern: I know that I could use that pattern to "react quicly" to events but that's not what my question is about.

For example if I have a BlockingQueue (mostly empty) and a thread "stuck" waiting for an element to be pushed on that queue so that it can be consumed, what would be a good way to minimize the time spent (reduce the latency) between the moment an element is pushed on the queue and the moment it is consumed?

For example what's the difference between a thread doing this:

while( true ) {
   elem = queue.peek();
   if ( elem == null ) {
       Thread.sleep( 25 ); // prevents busy-looping
   } else {
   ... // do something here
   }
}

and another one doing this:

while ( true ) {
    elem = queue.take();
    ... // do something with elem here
}

(I take it that to simplify things we can ignore discussing about exceptions here!?)

What goes on under the hood when you call take() and the queue is empty? The JVM somehow has to "sleep" the thread under the hood because it can't be busy-looping constantly checking if there's something on the queue? Is take() using some CAS operation under the hood? And if so what determines how often take() does call that CAS operation?

What when something suddenly makes it to the queue? How's that thread blocked on take() somehow "notified" that it should act promptly?

Lastly, is it "common" to have one thread "stuck" on take() on a BlockingQueue for the lifetime of the application?

It's all one big question related to how the blocking take() works and I take it that answering my various questions (at least the one that makes sense) would help me understand all this better.

Upvotes: 1

Views: 902

Answers (5)

user207421
user207421

Reputation: 310980

The difference is that the first thread sleeps for up to 25ms too long, whereas the second thread doesn't waste any time at all.

Upvotes: 0

Ralf H
Ralf H

Reputation: 1474

Since two threads are involved, the peek/sleep with a hypothetical micro/nano-sleep implementation would not differ too much from take() since they both involve passing information from one thread to the next via main memory (using volatile write/read and a healthy amount of CAS), unless the JVMs find other ways to do inter-thread synchronization. You can try to implement a benchmark using two BlockingQueues and two threads who each act as producer for one queue and consumer for the other and move a token back and forth, taking it from one queue and offering to the next. Then you could see how fast they can produce/consume and compare that to peek/sleep. I guess performance depends a lot on the amount work spent on each token (in this case zero, so we measure pure overhead) and the distance of CPU to memory. In my experience, single CPUs come out way ahead of multi-socket machines.

Upvotes: 0

Peter Lawrey
Peter Lawrey

Reputation: 533670

You can assume that take() will be notified that it can wake as soon your OS can pass such a signal between threads. Note: your OS will be involved worst case. Typically this is 1 - 10 micro-seconds, and in rare case 100 or even 1000 micro-seconds in very rare cases. Note: Thread.sleep will wait for a minimum of 1000 microseconds and 25 milli-seconds is 25,000 micro-seconds so I would hope the difference is obvious to you.

The only really way of avoiding rare but long context switches is to busy wait on a affinity lock CPU. (This allocates a CPU to your thread) If your application is that latency sensible, simpler solution is to not pass the work between threads at all. ;)

Upvotes: 1

Eran
Eran

Reputation: 393936

Well, here's the implementation of LinkedBlockingQueue<E>.take() :

public E take() throws InterruptedException {
    E x;
    int c = -1;
    final AtomicInteger count = this.count;
    final ReentrantLock takeLock = this.takeLock;
    takeLock.lockInterruptibly();
    try {
            while (count.get() == 0) {
                notEmpty.await();
            }
        x = dequeue();
        c = count.getAndDecrement();
        if (c > 1)
            notEmpty.signal();
    } finally {
        takeLock.unlock();
    }
    if (c == capacity)
        signalNotFull();
    return x;
}

When the queue is empty, notEmpty.await() is called, which :

Causes the current thread to wait until it is signalled or interrupted.

The lock associated with this Condition is atomically released and the current thread becomes disabled for thread scheduling purposes and lies dormant until one of four things happens:

  1. Some other thread invokes the signal method for this Condition and the current thread happens to be chosen as the thread to be awakened; or
  2. Some other thread invokes the signalAll method for this Condition; or
  3. Some other thread interrupts the current thread, and interruption of thread suspension is supported; or
  4. A "spurious wakeup" occurs.

When another threads puts something in the queue, it calls signal, which awakes one of the threads waiting to consume items from this queue. This should work faster then your peek/sleep loop.

Upvotes: 1

Zim-Zam O&#39;Pootertoot
Zim-Zam O&#39;Pootertoot

Reputation: 18148

Internally, take waits on the notEmpty condition, which is signaled in the insert method; in other words, the waiting thread goes to sleep, and wakes up on insert. This should be fast.

Some blocking queues, e.g. ArrayBlockingQueue and SynchronousQueue, have a constructor that accepts the queue's fairness property; passing in true should prevent threads from getting stuck on take, otherwise this is a possibility. (This parameter specifies whether the underlying ReentrantLock is fair.)

Upvotes: 1

Related Questions