Sometimes we give terrible advice. Like in that article about how to use Java 8 for a cached, functional approach to calculating fibonacci numbers. As Matthias, one of our readers, noticed in the comments, the proposed algorithm may just never halt. Consider the following program:
public class Test {
static Map<Integer, Integer> cache
= new ConcurrentHashMap<>();
public static void main(String[] args) {
System.out.println(
"f(" + 25 + ") = " + fibonacci(25));
}
static int fibonacci(int i) {
if (i == 0)
return i;
if (i == 1)
return 1;
return cache.computeIfAbsent(i, (key) -> {
System.out.println(
"Slow calculation of " + key);
return fibonacci(i - 2) + fibonacci(i - 1);
});
}
}It will run indefinitely at least on the following Java version:
C:\Users\Lukas>java -version java version "1.8.0_40-ea" Java(TM) SE Runtime Environment (build 1.8.0_40-ea-b23) Java HotSpot(TM) 64-Bit Server VM (build 25.40-b25, mixed mode)
This is of course a “feature”. The ConcurrentHashMap.computeIfAbsent() Javadoc reads:
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.
The “must not” wording is a clear contract, which my algorithm violated, although not for the same concurrency reasons.
The Javadoc also reads:
Throws:
IllegalStateException – if the computation detectably attempts a recursive update to this map that would otherwise never complete
But that exception isn’t thrown. Neither is there any ConcurrentModificationException. Instead, the program just never halts.
The simplest use-site solution for this concrete problem would be to not use a ConcurrentHashMap, but just a HashMap instead:
static Map<Integer, Integer> cache = new HashMap<>();
Subtypes overriding super type contracts
The HashMap.computeIfAbsent() or Map.computeIfAbsent() Javadoc don’t forbid such recursive computation, which is of course ridiculous as the type of the cache is Map<Integer, Integer>, not ConcurrentHashMap<Integer, Integer>. It is very dangerous for subtypes to drastically re-define super type contracts (Set vs. SortedSet is greeting). It should thus be forbidden also in super types, to perform such recursion.
Further reference
While the contract issues are a matter of perception, the halting problem clearly is a bug. I’ve also documented this issue on Stack Overflow where Ben Manes gave an interesting answer leading to a previous (unresolved as of early 2015) bug report:
My own report (probably a duplicate of the above) was also accepted quickly, as:
While this is being looked at by Oracle, remember to:
Never recurse inside a
ConcurrentHashMap.computeIfAbsent()method. And if you’re implementing collections and think it’s a good idea to write a possibly infinite loop, think again, and read our article:Infinite Loops. Or: Anything that Can Possibly Go Wrong, Does)
Murphy is always right.
| Reference: | Avoid Recursion in ConcurrentHashMap.computeIfAbsent() from our JCG partner Lukas Eder at the JAVA, SQL, AND JOOQ blog. |
