add()/offer(): Adds a new item to the end of the list;
poll(): Removes the first item in the list;
contains(): Verifies whether a given item exists in the list or not;
remove(): Removes an item anywhere in the list if it is present;
We talked on a previous post about CLLElectedUnlink that can use an optimized version with relaxed list traversals to improve the throughout in CPU architectures with weak memory ordering, like PowerPC and ARM, providing an increase in performance that can go up to 15x.
As it so happens, we figured out a way to use the same kind of optimizations on Java's ConcurrentLinkedQueue (CLQ) with minimum code modifications, and we named it ConcurrentLinkedQueueRelaxed.
Yes, you read it well, it's not a typo! This version of CLQ has a throughput increase on PowerPC that can be 15x than the one currently on JDK 8:
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/Java/com/concurrencyfreaks/list/ConcurrentLinkedQueueRelaxed.java
You can try for yourself on one of the PowerPC instances of RunAbove, or if you have a PowerPC machine.
We would like to hear about the results of your own application, or your own benchmarks, on either PowerPC or ARM (ARMv7 or ARMv8).
A more detailed description of the optimizations can be found on this presentation:
https://github.com/pramalhe/ConcurrencyFreaks/raw/master/Presentations/ConcurrentLinkedQueueRelaxed.pptx
The basic idea is that we traverse the list and read the value of item without using a non-volatile load, until the item we're looking for is found (it's a bit more trickier than that, but this is the main concept).
We modified contains() to use read the reference to the next node using a non-volatile load (unless it is null), and to read the reference to the item also as a non-volatile load (unless it is null):
public boolean contains(Object o) {
if (o == null) return false;
for (Node<E> p = first(); p != null; p = succRelaxed(p)) {
E item = p.getRelaxedItem();
if (item != null && o.equals(item) && p.item != null)
return true;
}
return false;
}
A similar modification was done for remove():
public boolean remove(Object o) {
if (o == null) return false;
Node<E> pred = null;
for (Node<E> p = first(); p != null; p = succRelaxed(p)) {
E item = p.getRelaxedItem();
if (item != null &&
o.equals(item) &&
p.casItem(item, null)) {
Node<E> next = succ(p);
if (pred != null && next != null)
pred.casNext(p, next);
return true;
}
pred = p;
}
return false;
}
}
The results speak for themselves:
The 100% Writes plot means that 50% of the operations are add(), the other 50% remove(), and there are no contains() being done.
Notice that as Herb Sutter mentioned on the second part of his presentation on the C++1x memory model, and Doug Lea on several presentations, using volatile loads or relaxed loads on x86 is the same, which means that these optimizations have absolutely no effect on x86.
http://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html
It's only on PowerPC (and maybe ARM) that we see its true potential, because a volatile load on PowerPC implies two dcs instructions per node that is traversed, so by cutting those, we have the observed performance gains.
And what's more impressive is that you get the performance improvement even if you're using a single thread :-O
