java recursion java-9 memoization concurrenthashmap

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?

Solution

ConcurrentModificationException is thrown because slowFib is modifying multiple keys and values. If you look at Java 9 HashMap.computeIfAbsent() code you will find that the exception is thrown here:

int mc = modCount;
V v = mappingFunction.apply(key);
if (mc != modCount) { throw new ConcurrentModificationException(); }

Each invocation of slowFib attempts to modify values mapped to keys n-1 and n-2.

The modCount check is not performed in Java 8 HashMap.computeIfAbsent() code. This is a bug in Java 8, your approach doesn't work in all cases as per JDK-8071667 HashMap.computeIfAbsent() adds entry that HashMap.get() does not find which added the modCount check in Java 9:

If the function supplied to computeIfAbsent adds items to the same HashTable on which the function is called from and the internal table is enlarged because of this, the new entry will be added to the wrong place in the Map's internal table making it inaccessible.