I am reading Java Concurrency in practice, now I'm on page about comparison LinkedBlockingQueue with ArrayBlockingQueue and I've found this text
This test suggests that LinkedBlockingQueue scales better than ArrayBlockingQueue.This may seem odd at first: a linked queue must allocate a link node object for each insertion, and hence seems to be doing more work than the array-based queue. However, even though it has more allocation and GC overhead, a linked queue allows more concurrent access by put and take than an array-based queue because the best linked queue algorithms allow the head and tail to be updated independently. Because allocation is usually threadlocal, algorithms that can reduce contention by doing more allocation usually scale better.(This is another instance in which intuition based on traditional performance tuning runs counter to what is needed for scalability.)
with such an image
I've dived into source code of ArrayBlockingQueue and, indeed, found single lock for put()
and take()
operations (as fact, by semantic, I've only found synchronization for accessing count field, where there is information about current content's size of queue).
code of put method
public void put(E e) throws InterruptedException {
checkNotNull(e);
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
while (count == items.length)
notFull.await();
enqueue(e);
} finally {
lock.unlock();
}
}
My question is: What is impediment to implement ArrayBlockingQueue with two locks instead of one lock for tail and head. I can imagine some algorithm, which check if there is some place ahead to move the next take's place and next put's place;
put()
check on equality with place where take()
is and if it is equal put()
is waiting and the same done by take()
. It is seemed will be working because put()
and take()
have, in some sense, constant direction of moving along array. Of course, we should take into account the initial state by some boolean flag.
Of course, it is obviously that in present ArrayBlockingQueue has worse throughput than LinkedBlockingQueue, because of more contention and, therefore, more serilized code (Amdal's law). But what can be problem to write it with two locks and have with it a smaller allocation time as well!
sorry for my bad english, in advance!