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

Question

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:UsersLukas>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?

Answer 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.