#On a note. Caution atomic operations in ConcurrentHashMap
Since time immemorial, Java has had a wonderful Map interface and its implementation, in particular HashMap. And starting with Java 5, there is also ConcurrentHashMap. Consider these two implementations, their evolution and what this evolution can lead to inattentive developers.
Warning: this article uses citations from the OpenJDK 11 source code, distributed under the GNU General Public License version 2.
Times Before Java 8
Those who found long, long waiting times, first Java 7, and then Java 8 (not like now, every six months a new version), remember which operations with Map were the most popular. It:
• V Map.put (K key, V value)
• V Map.get (Object key)
If you need to put a value in the collection, we use the first method, and to get the existing value, use the second.
But what if lazy initialization is required? Then a code of this kind appeared:
String getOrPut (String key) {
String result = map.get (key); //(one)
if (result == null) {// (2)
result = createValue (key); // (3)
map.put (key, result); //(4)
}
return result;
}
1. get the key value
2. check if the desired value is found
3. if no value is found, then create it
4. add the value to the collection by key
It turns out a little cumbersome, do not you? Moreover, in the case when a simple HashMap is used, then this is just code that is inconvenient to read, because it is not threaded. But in the case of ConcurrentHashMap, an additional feature pops up: the createValue (2) method can be called several times if several threads manage to check condition (1) before one of them writes the value to collection (3). Such behavior can often lead to undesirable consequences.
Before Java 8, there were simply no elegant options. If you needed to dodge several value creation, then you had to use additional locks.
Java 8 made things easier. It would seem that…
Java 8 comes to us …
What is the most anticipated feature that came to us with Java 8? That's right, lambda. And not just llamas, but their support in all the variety of APIs of the standard library. Map data structures have not been ignored. In particular, there appeared methods such as:
• computeIfAbsent
• computeIfPresent
• forEach
• etc.
Due to these methods, it is possible to rewrite the code given earlier much easier:
String getOrPut (String key) {
return map.computeIfAbsent (key, this :: createValue);
}
It is clear that no one will give up the opportunity to simplify their code. Moreover, in the case of ConcurrentHashMap, the computeIfAbsent method also executes atomically. Those. createValue will be called exactly once and only if the required value is absent.
IDEs also did not pass by. So IntelliJ IDEA offers auto-replacement of the old version with the new one:
It’s clear that both code simplification and IDE hints encourage developers to use this new API. As a result, the same computeIfAbsent began to appear in so many places in the code.
Till…
Suddenly!
Until the time has come for the next load testing. And then a terrible thing appeared:
For those who are not familiar with such a wonderful tool like YourKit.
In the screenshot, horizontal wide lines show the operation of application threads in time. Depending on the state of the stream at a particular point in time, the strip is painted in the appropriate color:
• yellow – the stream is idle, waiting for work;
• green — the thread is running by executing program code;
• red – this thread is blocked by another thread.
That is, it turns out that almost all threads (and in fact there were much more than what is shown in the screenshot) are almost all the time in a blocked state. And for all, the lock is in the same computeIfAbsent of ConcurrentHashMap! And this despite the fact that due to the specifics of this particular load test, no more than 6-8 values can be stored in this collection. Those. almost all operations in a given place are exclusively reading the existing values.
But wait, how so? After all, even in the documentation for the method about locks, they say only in the application for the update:
"If the specified key is not already associated with a value, attempts to compute its value using the given mapping function and enters it into this map unless null. The entire method invocation is performed atomically, so the function is applied at most once per key. Some attempted update operations on this map by other threads may be blocked while computation is in progress, so the computation should be short and simple, and must not attempt to update any other mappings of this map. ”
In fact, it turns out not so. If you look at the source code of this method, it turns out that it contains two very thick synchronizing blocks:
public V computeIfAbsent (K key, Function mappingFunction) {
if (key == null || mappingFunction == null)
throw new NullPointerException ();
int h = spread (key.hashCode ());
V val = null; // (one)
int binCount = 0;
for (Node[] tab = table ;;) {
Node f; int n, i, fh; K fk; V fv;
if (tab == null || (n = tab.length) == 0)
tab = initTable ();
else if ((f = tabAt (tab, i = (n - 1) & h)) == null) {
Node r = new ReservationNode();
synchronized (r) {
if (casTabAt (tab, i, null, r)) {
binCount = 1;
Node node = null;
try {
if ((val = mappingFunction.apply (key))! = null) // (2)
node = new Node(h, key, val);
} finally {
setTabAt (tab, i, node);
}
}
}
if (binCount! = 0)
break;
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer (tab, f);
else if (fh == h // check first node without acquiring lock
&& ((fk = f.key) == key || (fk! = null && key.equals (fk)))
&& (fv = f.val)! = null)
return fv;
else {
boolean added = false;
synchronized (f) {
if (tabAt (tab, i) == f) {
if (fh> = 0) {
binCount = 1;
for (Node e = f ;; ++ binCount) {
K ek;
if (e.hash == h &&
((ek = e.key) == key ||
(ek! = null && key.equals (ek)))) {
val = e.val; // (3)
break;
}
Node pred = e;
if ((e = e.next) == null) {
if ((val = mappingFunction.apply (key))! = null) {// (4)
if (pred.next! = null)
throw new IllegalStateException ("Recursive update");
added = true;
pred.next = new Node(h, key, val);
}
break;
}
}
}
else if (f instanceof TreeBin) {
binCount = 2;
Treebin t = (TreeBin) f;
Treenode r, p;
if ((r = t.root)! = null &&
(p = r.findTreeNode (h, key, null))! = null)
val = p.val; // (5)
else if ((val = mappingFunction.apply (key))! = null) {// (6)
added = true;
t.putTreeVal (h, key, val);
}
}
else if (f instanceof ReservationNode)
throw new IllegalStateException ("Recursive update");
}
}
if (binCount! = 0) {
if (binCount> = TREEIFY_THRESHOLD)
treeifyBin (tab, i);
if (! added)
return val;
break;
}
}
}
if (val! = null)
addCount (1L, binCount);
return val;
}
From the above example, it can be seen that the result can be formed only at six points, and almost all of these places are inside synchronizing blocks. Quite unexpectedly. Moreover, a simple get does not contain synchronization at all:
public V get (Object key) {
Node[] tab; Node e, p; int n, eh; K ek;
int h = spread (key.hashCode ());
if ((tab = table)! = null && (n = tab.length)> 0 &&
(e = tabAt (tab, (n - 1) & h))! = null) {
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek! = null && key.equals (ek)))
return e.val;
}
else if (eh <0)
return (p = e.find (h, key))! = null? p.val: null;
while ((e = e.next)! = null) {
if (e.hash == h &&
((ek = e.key) == key || (ek! = null && key.equals (ek))))
return e.val;
}
}
return null;
}
So what to do? In fact, there are only two options: either return to the original code, or use it, but in a slightly modified version:
String getOrPut (String key) {
String result = map.get (key);
return (result! = null)? result: map.computeIfAbsent (key, this :: createValue);
}
Conclusion
In general, such fatal consequences from a seemingly banal refactoring were very unexpected. The situation was saved only by the presence of a stress test, which successfully revealed degradation.
It remains a mystery to me why computeIfAbsent is written in such a way that even a read operation turns out to be blocking and you have to manually add a preliminary non-blocking read with subsequent verification. Why not put this code right inside computeIfAbsent?
So be careful, do not trust the tempting tips and write tests. Especially stressful.
Java to everyone!
