On Tue, 8 Apr 2025 18:39:30 GMT, kabutz <[email protected]> wrote:
> In the JavaDoc of LinkedBlockingDeque, it states: "Linked nodes are
> dynamically created upon each insertion unless this would bring the deque
> above capacity." However, in the current implementation, nodes are always
> created, even if the deque is full. This is because count is non-volatile,
> and we only check inside the linkFirst/Last() methods whether the queue is
> full. At this point we have already locked and have created the Node.
> Instead, the count could be volatile, and we could check before locking.
>
> In the current version, calling offer() on a full LinkedBlockingDeque creates
> unnecessary objects and contention. Similarly for poll() and peek(), we could
> exit prior to locking by checking the count field.
>
> Our suggestion is to make count volatile, and then exiting early from poll()
> and offer()
My code is similar to how LinkedBlockingQueue works.
>From LinkedBlockingQueue:
public boolean offer(E e) {
if (e == null) throw new NullPointerException();
final AtomicInteger count = this.count;
if (count.get() == capacity)
return false;
final int c;
final Node<E> node = new Node<E>(e);
final ReentrantLock putLock = this.putLock;
putLock.lock();
try {
if (count.get() == capacity)
return false;
enqueue(node);
c = count.getAndIncrement();
if (c + 1 < capacity)
notFull.signal();
} finally {
putLock.unlock();
}
if (c == 0)
signalNotEmpty();
return true;
}
However, I'm not sure whether it is a good idea to make this change, since
making count volatile in LBD might impact performance for the most common use
case (unbounded deque). For example:
import java.util.*;
import java.util.concurrent.*;
import java.util.stream.*;
public class NodeCreationBeforeLockLBD {
/*
This tests how quickly we can offer and poll on an "unbounded" deque,
in order to see whether it is better to create the node before the lock.
*/
public static void main(String... args) {
for (int i = 0; i < 3; i++) {
test(new LinkedBlockingDeque<>());
}
}
private static void test(Queue<Integer> q) {
System.out.println(q.getClass().getSimpleName());
long time = System.nanoTime();
try {
IntStream.range(0, 10_000_000)
.parallel()
.forEach(i -> {
for (int j = 0; j < 5; j++) q.offer(j);
for (int j = 0; j < 5; j++) q.poll();
});
System.out.println("q = " + q);
} finally {
time = System.nanoTime() - time;
System.out.printf("time = %dms%n", (time / 1_000_000));
}
}
}
Output with Java 25+17:
$ java -showversion NodeCreationBeforeLockLBD.java
openjdk version "25-ea" 2025-09-16
OpenJDK Runtime Environment (build 25-ea+17-1966)
OpenJDK 64-Bit Server VM (build 25-ea+17-1966, mixed mode, sharing)
LinkedBlockingDeque
q = []
time = 4790ms
LinkedBlockingDeque
q = []
time = 4411ms
LinkedBlockingDeque
q = []
time = 4588ms
Output with these changes:
$ java -showversion NodeCreationBeforeLockLBD.java
openjdk version "25-internal" 2025-09-16
OpenJDK Runtime Environment (build 25-internal-adhoc.kabutz.jdk)
OpenJDK 64-Bit Server VM (build 25-internal-adhoc.kabutz.jdk, mixed mode)
LinkedBlockingDeque
q = []
time = 6436ms
LinkedBlockingDeque
q = []
time = 5871ms
LinkedBlockingDeque
q = []
time = 5982ms
-------------
PR Comment: https://git.openjdk.org/jdk/pull/24521#issuecomment-2803938784
