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?

Nothing in this snippet that would suggest it; the problem is probably in your `Cache` class. Add that to the question, that'd help. — rzwitserloot, Jan 17 '21 at 07:32

javadev · Answer 1 · 2021-01-17T09:17:19.153

0

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.

edited Jan 17 '21 at 09:17

answered Jan 17 '21 at 07:52

javadev

688
2
6
17

You don't need multiple threads for `ConcurrentModificationException` to occur. See https://stackoverflow.com/q/223918/5646962 for an example – Thomas Kläger Jan 17 '21 at 08:44
You are right, I meant the common case for ConcurrentModificationException is un-safe thread usage. There's also this iteration-during-removal thing. Thanks for the clarification :) – javadev Jan 17 '21 at 09:14

score 0 · Answer 2 · answered Jan 17 '21 at 08:04

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

score 0 · Answer 3 · answered Jan 17 '21 at 08:41

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.

ConcurrentModificationException with very limited iterations

3 Answers3