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.

Java 8 Friday Goodies: Easy-as-Pie Local Caching

At Data Geekery, we love Java. And as we’re really into jOOQ’s fluent API and query DSL, we’re absolutely thrilled about what Java 8 will bring to our ecosystem. We have blogged a couple of times about some nice Java 8 goodies, and now we feel it’s time to start a new blog series, the…

Java 8 Friday

Every Friday, we’re showing you a couple of nice new tutorial-style Java 8 features, which take advantage of lambda expressions, extension methods, and other great stuff. You’ll find the source code on GitHub. tweet this

Java 8 Goodie: Easy-as-Pie Local Caching

Now get ready for one of the most awesome revelations in this series so far. We’ll show you an easy-as-pie way to implement a local cache using the good old HashMap and lambda expressions. Because, Map now has a new way of a atomically calculating a new value in case a key is absent. Perfect for caches. Let’s delve into code:

public static void main(String[] args) {
    for (int i = 0; i < 10; i++)
        System.out.println(
            "f(" + i + ") = " + fibonacci(i));
}

static int fibonacci(int i) {
    if (i == 0)
        return i;

    if (i == 1)
        return 1;

    System.out.println("Calculating f(" + i + ")");
    return fibonacci(i - 2) + fibonacci(i - 1);
}

Yes. That’s the naive way of doing things. Even for small numbers like fibonacci(5), the above algorithm will print out a huge amount of lines, as we’re repeating the same calculations exponentially:

Calculating f(6)
Calculating f(4)
Calculating f(2)
Calculating f(3)
Calculating f(2)
Calculating f(5)
Calculating f(3)
Calculating f(2)
Calculating f(4)
Calculating f(2)
Calculating f(3)
Calculating f(2)
f(6) = 8

What we want to do is build a cache of previously calculated fibonacci numbers. The most straightforward technique is to memoize all values in a cache. Here’s how we build a cache:

static Map<Integer, Integer> cache = new HashMap<>();

Important side note: A previous version of the blog post used a ConcurrentHashMap here. DO NOT USE ConcurrentHashMaps when you recursively calculate values using computeIfAbsent(). Details here:

http://stackoverflow.com/q/28840047/521799

Done! As mentioned before, we’re using the newly added Map.computeIfAbsent() method to calculate a new value from a source function only if we don’t already have a value for a given key. Caching! And since this method is guaranteed to execute atomically, and since we’re using a ConcurrentHashMap, this cache is even thread-safe without resorting to manually applying synchronized anywhere. And it can be reused for stuff other than calculating fibonacci numbers. But let’s first apply this cache to our fibonacci() function.

static int fibonacci(int i) {
    if (i == 0)
        return i;

    if (i == 1)
        return 1;

    return cache.computeIfAbsent(i, (key) ->
                 fibonacci(i - 2)
               + fibonacci(i - 1));
}

That’s it. It can’t get any simpler than this! Want proof? We’ll log a message on the console every time we actually evaluate a new value:

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

The above program will print

f(0) = 0
f(1) = 1
Slow calculation of 2
f(2) = 1
Slow calculation of 3
f(3) = 2
Slow calculation of 4
f(4) = 3
Slow calculation of 5
f(5) = 5
Slow calculation of 6
f(6) = 8
Slow calculation of 7
f(7) = 13
Slow calculation of 8
f(8) = 21
Slow calculation of 9
f(9) = 34

How would we have done it in Java 7?

Good question. With lots of code. We’d probably write something like this using double-checked locking:

static int fibonacciJava7(int i) {
    if (i == 0)
        return i;

    if (i == 1)
        return 1;

    Integer result = cache.get(i);
    if (result == null) {
        synchronized (cache) {
            result = cache.get(i);

            if (result == null) {
                System.out.println(
                    "Slow calculation of " + i);

                result = fibonacci(i - 2) 
                       + fibonacci(i - 1);
                cache.put(i, result);
            }
        }
    }

    return result;
}

Convinced?

Note, that your actual solution would probably make use of Guava Caches.

Conclusion

Lambdas are only one part of Java 8. An important part, but let’s not forget all the new features that were added to the libraries and that can be leveraged with lambdas now!

This is really exciting and…

We can greatly improve our code bases without resorting to new libraries. All of the above can be run with the JDK’s libraries only. tweet this

Next week in this blog series, we’re going to look at how Java 8 will improve on the existing and new concurrency APIs, so stay tuned!

More on Java 8

In the mean time, have a look at Eugen Paraschiv’s awesome Java 8 resources page