ConcurrentModificationException with very limited iterations

Question

I am trying to learn caching and I tried this:

public static <T, U, R> BiFunction<T, U, R> cached(BiFunction<T, U, R> bifunc) {
    Cache<Pair<T,U>, R> cache = new Cache<Pair<T,U>, R>(DEFAULT_CACHE_SIZE);
    
    System.out.println("Cache Size: "+cache.size());
    
    return (t, u) -> {
        Pair<T,U> pairKey = new Pair<T,U>(t,u);
        
        Function<Pair<T,U>, R> something = input -> {
            return bifunc.apply(input.get_first(), input.get_second());
        };
        
        return cache.computeIfAbsent(pairKey, something);
    };
}

For my cache and this to get the actual result:

BiFunction<BigInteger, BiFunction, BigInteger> fibHelper = cached((n, f) -> {
        if (n.compareTo(BigInteger.TWO) <= 0) return BigInteger.ONE;
        
        return ((BigInteger) (f.apply(n.subtract(BigInteger.ONE), f)))
                .add((BigInteger)f.apply(n.subtract(BigInteger.TWO), f));
    });
    
Function<BigInteger, BigInteger> fib = (n) -> fibHelper.apply(n,fibHelper);

BigInteger large = fib.apply(BigInteger.valueOf(3L));

I've tested it to run with big numbers and I'm getting a ConcurrentModificationException, so I tried to run with low numbers, when I tried to run with input 0 - 2 it works fine, but once I get to 3 and onwards I get a ConcurrentModificationException. I'm using a LinkedHashMap by the way.

I'm fairly new to this, any help?

Answer 1

Your data structures are not Thread-Safe.

ConcurrentModificationException is usually received when two threads are using/overriding the same object (usually data structures), or when an object is changed during iterating it (thanks Thomas Kläger).

I didn't understand what do you mean by

I'm using a LinkedHashMap

In which context?

BTW, LinkedHashMap is not concurrent-safe. If you want concurrent-safe data structures, you should use java.util.Concurrent package.

As rzwitserloot said, please provide full implementation or clearer explanation.

Answer 2

Nevermind, it seems that computeIfAbsent can be replaced by standard if/else which works perfectly.

public static <T, U, R> BiFunction<T, U, R> cached(BiFunction<T, U, R> bifunc) {
    Cache<Pair<T,U>, R> cache = new Cache<Pair<T,U>, R>(DEFAULT_CACHE_SIZE);
    
    return (t, u) -> {
        Pair<T,U> pairKey = new Pair<T,U>(t,u);
        
        Function<Pair<T,U>, R> something = input -> {
            return bifunc.apply(input.get_first(), input.get_second());
        };
        
        if (!cache.containsKey(pairKey)) {
            R result = something.apply(pairKey);
            cache.put(pairKey, result);
            
            return result;
        } else {
            return cache.get(pairKey);
        }
    };
}

Answer 3

The problem is the mapping function that you supply to computeIfAbsent().

The JavaDoc for Map.computeIfAbsent states:

The mapping function should not modify this map during computation.

This method will, on a best-effort basis, throw a ConcurrentModificationException if it is detected that the mapping function modifies this map during computation.

When computing fib(3) (or anything larger) it calls computeIfAbsent(..3..) which recursively calls computeIfAbsent(..2..) which modifies the map during the computation.

The solution to the problem is what you found out yourself: don't use computeIfAbsent() for recursive algorithms.