Puzzler: nested computeIfAbsent

Overview

The Java 8 libraries have a new method on map, computeIfAbsent.  This is very useful way to turn your Map into a cache of objects associated with a key.

However, there is a combination you might not have considered; what happens if you call computeIfAbsent inside itself.

map.computeIfAbsent(Key.Hello, s -> {
    map.computeIfAbsent(Key.Hello, t -> 1);
    return 2;
});

enum Key {Hello}

While this might seem like a strange thing to do in simple cases, in more complex code you could do this by accident (as I did this afternoon)  So what happens?  Well it depends on the collection you are using.

HashMap: {Hello=2}
WeakHashMap: {Hello=2}
TreeMap: {Hello=2}
IdentityHashMap: {Hello=2}
EnumMap: {Hello=2}
Hashtable: {Hello=2, Hello=1}
LinkedHashMap: {Hello=1, Hello=2}
ConcurrentSkipListMap: {Hello=1}
ConcurrentHashMap: 

Note: ConcurrentHashMap never returns.  It's locking doesn't appear to be re-entrant.

ConcurrentSkipListMap has the most reasonable result, retaining the first value added.  Hello=2 is reasonable for this undefined situation, if confusing as it is the second value not the first.  What doesn't make much sense is to have the unique immutable key appear twice.

Having ConcurrentHashMap deadlock itself is unfortunate but at least its not subtle.

The complete code.

public class A {
    public static void main(String[] args) {
        for (Map map : new Map[]{
                new HashMap<>(),
                new WeakHashMap<>(),
                new TreeMap<>(),
                new IdentityHashMap<>(),
                new EnumMap<>(Key.class),
                new Hashtable<>(),
                new LinkedHashMap<>(),
                new ConcurrentSkipListMap<>(),
                new ConcurrentHashMap<>()
        }) {
            System.out.print(map.getClass().getSimpleName() + ": ");
            map.computeIfAbsent(Key.Hello, s -> {
                map.computeIfAbsent(Key.Hello, t -> 1);
                return 2;
            });
            System.out.println(map);
        }
    }

    enum Key {Hello}
}

The method compute() has similar results

HashMap: {Hello=null2}
WeakHashMap: {Hello=null2}
TreeMap: {Hello=null2}
IdentityHashMap: {Hello=null2}
EnumMap: {Hello=null2}
Hashtable: {Hello=null2, Hello=1}
LinkedHashMap: {Hello=1, Hello=null2}
ConcurrentSkipListMap: {Hello=12}
ConcurrentHashMap:

public class A {
    public static void main(String[] args) {
        for (Map map : new Map[]{
                new HashMap<>(),
                new WeakHashMap<>(),
                new TreeMap<>(),
                new IdentityHashMap<>(),
                new EnumMap<>(Key.class),
                new Hashtable<>(),
                new LinkedHashMap<>(),
                new ConcurrentSkipListMap<>(),
                new ConcurrentHashMap<>()
        }) {
            System.out.print(map.getClass().getSimpleName() + ": ");
            map.compute(Key.Hello, (s, v) -> {
                map.compute(Key.Hello, (s2, v2) -> "1");
                return v + "2";
            });
            System.out.println(map);
        }
    }

    enum Key {Hello}
}

Conclusion

You need to be careful if you nest calls to a map from inside a lambda, or avoid doing so at all.  If you have to do this, ConcurrentSkipListMap appears to behave the best.

Comments

  1. An interesting caveat of doing that with ConcurrentHashMap is the fact that you may cause an infinite loop inside of the computeIfAbsent method. Details:

    - http://blog.jooq.org/2015/03/04/avoid-recursion-in-concurrenthashmap-computeifabsent
    - https://bugs.openjdk.java.net/browse/JDK-8074374
    - http://stackoverflow.com/q/28840047/521799

    ReplyDelete
  2. Yes, it's essentially a livelock, rather than a deadlock. Good luck to ya!

    ReplyDelete

Post a Comment

Popular posts from this blog

Java is Very Fast, If You Don’t Create Many Objects

System wide unique nanosecond timestamps

Unusual Java: StackTrace Extends Throwable