Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Avoid Recursion in ConcurrentHashMap.computeIfAbsent()

DZone's Guide to

Avoid Recursion in ConcurrentHashMap.computeIfAbsent()

· Java Zone
Free Resource

Learn how to troubleshoot and diagnose some of the most common performance issues in Java today. Brought to you in partnership with AppDynamics.

Sometimes we give terrible advice. Like in that article about how to use Java 8 for a cached, functional approach to calculating fibonacci numbersAs 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”. TheConcurrentHashMap.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>, notConcurrentHashMap<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 whereBen 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 aConcurrentHashMap.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.

Understand the needs and benefits around implementing the right monitoring solution for a growing containerized market. Brought to you in partnership with AppDynamics.

Topics:

Published at DZone with permission of Lukas Eder, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}