[concurrency-interest] ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

Dr Heinz M. Kabutz heinz at javaspecialists.eu
Tue Apr 19 04:14:18 EDT 2016


Hi everybody,

I think I might have discovered some issues with our wonderful 
ConcurrentHashMap.  In this code, it appears to livelock on the 
transfer() method once i=12:

import java.math.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;

public class WeirdComputeIfAbsentBehaviour {
  public static void main(String... args) {
    for (int i = 0; i < 30; i++) {
      System.out.println("i = " + i);
      show(new HashMap(), i);
      show(new LinkedHashMap(), i);
      show(new ConcurrentSkipListMap<>(), i);
      show(new ConcurrentHashMap<>(), i);
    }
  }

  private static void show(Map<Integer, BigInteger> map, int n) {
    System.out.println(map.getClass().getSimpleName() + ": " +
        new FibonacciCached(map).f(n));
  }


  public static class FibonacciCached {
    private final Map<Integer, BigInteger> cache;

    public FibonacciCached(Map<Integer, BigInteger> cache) {
      this.cache = cache;
      cache.put(0, BigInteger.ZERO);
      cache.put(1, BigInteger.ONE);
    }

    public BigInteger f(int n) {
      return cache.computeIfAbsent(n, key -> f(n - 1).add(f(n - 2)));
    }
  }
}


Output in Java 8:

java version "1.8.0_74"
Java(TM) SE Runtime Environment (build 1.8.0_74-b02)
Java HotSpot(TM) 64-Bit Server VM (build 25.74-b02, mixed mode)

i = 0
HashMap: 0
LinkedHashMap: 0
ConcurrentSkipListMap: 0
ConcurrentHashMap: 0
i = 1
HashMap: 1
LinkedHashMap: 1
ConcurrentSkipListMap: 1
ConcurrentHashMap: 1
i = 2
HashMap: 1
LinkedHashMap: 1
ConcurrentSkipListMap: 1
ConcurrentHashMap: 1
i = 3
HashMap: 2
LinkedHashMap: 2
ConcurrentSkipListMap: 2
ConcurrentHashMap: 2
i = 4
HashMap: 3
LinkedHashMap: 3
ConcurrentSkipListMap: 3
ConcurrentHashMap: 3
i = 5
HashMap: 5
LinkedHashMap: 5
ConcurrentSkipListMap: 5
ConcurrentHashMap: 5
i = 6
HashMap: 8
LinkedHashMap: 8
ConcurrentSkipListMap: 8
ConcurrentHashMap: 8
i = 7
HashMap: 13
LinkedHashMap: 13
ConcurrentSkipListMap: 13
ConcurrentHashMap: 13
i = 8
HashMap: 21
LinkedHashMap: 21
ConcurrentSkipListMap: 21
ConcurrentHashMap: 21
i = 9
HashMap: 34
LinkedHashMap: 34
ConcurrentSkipListMap: 34
ConcurrentHashMap: 34
i = 10
HashMap: 55
LinkedHashMap: 55
ConcurrentSkipListMap: 55
ConcurrentHashMap: 55
i = 11
HashMap: 89
LinkedHashMap: 89
ConcurrentSkipListMap: 89
ConcurrentHashMap: 89
i = 12
HashMap: 144
LinkedHashMap: 144
ConcurrentSkipListMap: 144
2016-04-19 11:08:49
Full thread dump Java HotSpot(TM) 64-Bit Server VM (25.74-b02 mixed mode):
*snip*

"main" #1 prio=5 os_prio=31 tid=0x00007f81e3801000 nid=0x1703 runnable 
[0x0000700000219000]
   java.lang.Thread.State: RUNNABLE
        at 
java.util.concurrent.ConcurrentHashMap.transfer(ConcurrentHashMap.java:2497)
        at 
java.util.concurrent.ConcurrentHashMap.addCount(ConcurrentHashMap.java:2288)
        at 
java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1720)
        at 
samples.ch15.WeirdComputeIfAbsentBehaviour$FibonacciCached.f(WeirdComputeIfAbsentBehaviour.java:35)
        at 
samples.ch15.WeirdComputeIfAbsentBehaviour$FibonacciCached.lambda$f$0(WeirdComputeIfAbsentBehaviour.java:35)
        at 
samples.ch15.WeirdComputeIfAbsentBehaviour$FibonacciCached$$Lambda$1/1831932724.apply(Unknown 
Source)
        at 
java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660)
        - locked <0x000000076ae88b50> (a 
java.util.concurrent.ConcurrentHashMap$ReservationNode)
        at 
samples.ch15.WeirdComputeIfAbsentBehaviour$FibonacciCached.f(WeirdComputeIfAbsentBehaviour.java:35)
        at 
samples.ch15.WeirdComputeIfAbsentBehaviour.show(WeirdComputeIfAbsentBehaviour.java:21)
        at 
samples.ch15.WeirdComputeIfAbsentBehaviour.main(WeirdComputeIfAbsentBehaviour.java:15)

Oh and it doesn't even get that far with Java 9 (my VarHandle build from 
last month), because HashMap dies when i=3:

openjdk version "9-internal"
OpenJDK Runtime Environment (build 
9-internal+0-2016-03-02-185127.heinz.sandbox)
OpenJDK 64-Bit Server VM (build 
9-internal+0-2016-03-02-185127.heinz.sandbox, mixed mode)

i = 0
HashMap: 0
LinkedHashMap: 0
ConcurrentSkipListMap: 0
ConcurrentHashMap: 0
i = 1
HashMap: 1
LinkedHashMap: 1
ConcurrentSkipListMap: 1
ConcurrentHashMap: 1
i = 2
HashMap: 1
LinkedHashMap: 1
ConcurrentSkipListMap: 1
ConcurrentHashMap: 1
i = 3
Exception in thread "main" java.util.ConcurrentModificationException
        at java.util.HashMap.computeIfAbsent(HashMap.java:1138)
        at 
samples.ch15.WeirdComputeIfAbsentBehaviour$FibonacciCached.f(WeirdComputeIfAbsentBehaviour.java:35)
        at 
samples.ch15.WeirdComputeIfAbsentBehaviour.show(WeirdComputeIfAbsentBehaviour.java:21)
        at 
samples.ch15.WeirdComputeIfAbsentBehaviour.main(WeirdComputeIfAbsentBehaviour.java:12)

Regards

Heinz
-- 
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java(tm) Specialists' Newsletter"
Sun/Oracle Java Champion since 2005
JavaOne Rock Star Speaker 2012
http://www.javaspecialists.eu
Tel: +30 69 75 595 262
Skype: kabutz



More information about the Concurrency-interest mailing list