'Since Java 9 HashMap.computeIfAbsent() throws ConcurrentModificationException on attempt to memoize recursive function results

Today I learned from some JS course what memoization is and tried to implement it in Java. I had a simple recursive function to evaluate n-th Fibonacci number:

long fib(long n) {
    if (n < 2) {
        return n;
    }

    return fib(n - 1) + fib(n - 2);
}

Then I decided to use HashMap in order to cache results of recursive method:

private static <I, O> Function<I, O> memoize(Function<I, O> fn) {
    final Map<I, O> cache = new HashMap<>();
    return in -> {
        if (cache.get(in) != null) {
            return cache.get(in);
        } else {
            O result = fn.apply(in);
            cache.put(in, result);
            return result;
        }
    };
}

This worked as I expected and it allowed me to memoize fib() like this memoize(this::fib)

Then I googled the subject of memoization in Java and found the question: Java memoization method where computeIfAbsent was proposed which is much shorter than my conditional expression.

So my final code which I expected to work was:

public class FibMemo {
    private final Function<Long, Long> memoizedFib = memoize(this::slowFib);

    public long fib(long n) {
        return memoizedFib.apply(n);
    }

    long slowFib(long n) {
        if (n < 2) {
            return n;
        }

        return fib(n - 1) + fib(n - 2);
    }

    private static <I, O> Function<I, O> memoize(Function<I, O> fn) {
        final Map<I, O> cache = new HashMap<>();
        return in -> cache.computeIfAbsent(in, fn);
    }

    public static void main(String[] args) {
        new FibMemo().fib(50);
    }
}

Since I used Java 11, I got:

Exception in thread "main" java.util.ConcurrentModificationException
    at java.base/java.util.HashMap.computeIfAbsent(HashMap.java:1134)
    at algocasts.matrix.fibonacci.FibMemo.lambda$memoize$0(FibMemo.java:24)
    at algocasts.matrix.fibonacci.FibMemo.fib(FibMemo.java:11)
    at algocasts.matrix.fibonacci.FibMemo.slowFib(FibMemo.java:19)
    at java.base/java.util.HashMap.computeIfAbsent(HashMap.java:1133)
    at algocasts.matrix.fibonacci.FibMemo.lambda$memoize$0(FibMemo.java:24)

The problem quickly brought me to the following question which is very similar: Recursive ConcurrentHashMap.computeIfAbsent() call never terminates. Bug or "feature"?

except Lukas used ConcurrentHashMap and got never ending loop. In the article related to the question Lukas advised:

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

That's exactly what I was trying to do, but did not succeed with Java 11. I found out empirically that HashMap throws ConcurrentModificationException since Java 9 (thanks SDKMAN):

sdk use java 9.0.7-zulu && javac Test.java && java Test # throws ConcurrentModificationException
sdk use java 8.0.202-zulufx && javac Test.java && java Test # works as expected

Here are the summary of my attempts:

  • Java 8 && ConcurrentHashMap -> works if input < 13, otherwise endless loop
  • Java 9 && ConcurrentHashMap -> works if input < 13, hangs if input = 14, throws IllegalStateException: Recursive update if input is 50
  • Java 8 && HashMap -> Works!
  • Java 9 && HashMap -> Throws ConcurrentModificationException after input >= 3

I would like to know why ConcurrentModificationException gets thrown on attempt to use HashMap as a cache for recursive function? Was it a bug in Java 8 allowing me to do so or is it another in Java > 9 which throws ConcurrentModificationException?

javarecursionjava-9concurrenthashmap


Solution 1:[1]

You can roll your own:

public static <K, V> V computeIfAbsent(
    Map<K, V> cache, 
    K key,
    Function<? super K, ? extends V> function
) {
    V result = cache.get(key);

    if (result == null) {
        result = function.apply(key);
        cache.put(key, result);
    }

    return result;
}

This approach assumes you don't have null values. If you do, just change the logic to use Map.containsKey()

This access works around the problem by making the cache value retrieval and putting of calculated values non-atomic again, which Map::computeIfAbsent tries to avoid. I.e. the usual race condition problems re-occur. But that might be fine in your case, of course.

Solution 2:[2]

What about this one? Not sure about performance though...

public class Fibonacci {

  private static final Map<Integer, Integer> memoized = new ConcurrentSkipListMap<>(Map.of(1,1,2,1));

  public static int fib(int n) {
    return memoized.computeIfAbsent(n, x -> fib(x - 2) + fib(x - 1));
  }

  public static void main(String[] args) {
    System.out.println(fib(12));
  }

}

Solution 3:[3]

You can use ConcurrentSkipListMap

It is a thread-safe map and it will not through ConcurrentModificationException in recursive & itaration of collections while using computeIfAbsent().

Reference:

https://dzone.com/articles/avoid-recursive-invocation-on-computeifabsent-in-h

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1
Solution 2 Bojan Vukasovic
Solution 3 Atequer Rahman

Related Questions