Avoid Recursion in ConcurrentHashMap.computeIfAbsent()

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:

https://bugs.openjdk.java.net/browse/JDK-8062841

My own report (probably a duplicate of the above) was also accepted quickly, as:

https://bugs.openjdk.java.net/browse/JDK-8074374

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.

4 thoughts on “Avoid Recursion in ConcurrentHashMap.computeIfAbsent()

  1. A fresh, unexpected way to unintentionally cause my execution to hang. Fun! Thank you for potentially saving me some head-scratching 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s