Recursive ConcurrentHashMap.computeIfAbsent() call never terminates. Bug or "feature"?

Some time ago, I've blogged about a Java 8 functional way of calculating fibonacci numbers recursively, with a ConcurrentHashMap cache and the new, useful computeIfAbsent() method:

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

public class Test {
    static Map<Integer, Integer> cache = new ConcurrentHashMap<>();

    public static void main(String[] args) {
        System.out.println(
            "f(" + 8 + ") = " + fibonacci(8));
    }

    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);
        });
    }
}

I chose ConcurrentHashMap because I was thinking of making this example even more sophisticated by introducing parallelism (which I didn't in the end).

Now, let's increase the number from 8 to 25 and observe what happens:

        System.out.println(
            "f(" + 25 + ") = " + fibonacci(25));

The program never halts. Inside the method, there's a loop that just runs forever:

for (Node<K,V>[] tab = table;;) {
    // ...
}

I'm using:

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)

Matthias, a reader of that blog post also confirmed the issue (he actually found it).

This is weird. I would have expected any of the following two:

• It works
• It throws a ConcurrentModificationException

But just never halting? That seems dangerous. Is it a bug? Or did I misunderstand some contract?

Solution 1:

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.

What's still interesting is that there is no ConcurrentModificationException. Instead, the program just never halts - which still is a rather dangerous bug in my opinion (i.e. infinite loops. or: anything that can possibly go wrong, does).

Note:

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.

Solution 2:

This is fixed in JDK-8062841.

In the 2011 proposal, I identified this issue during the code review. The JavaDoc was updated and a temporary fix was added. It was removed in a further rewrite due to performance issues.

In the 2014 discussion, we explored ways to better detect and fail. Note that some of the discussion was taken offline to private email for considering the low-level changes. While not every case can be covered, the common cases will not livelock. These fixes are in Doug's repository but have not made it into a JDK release.

Solution 3:

This is very similar to the bug. Because, if you create your cache with capacity 32, your program will work until 49. And it is interesting, that parameter sizeCtl =32 + (32 >>> 1) + 1) =49! May be the reason in resizing?