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

Benjamin Manes ben.manes at gmail.com
Tue Apr 19 04:45:44 EDT 2016


Unfortunately the improvements
<http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java?r1=1.258&r2=1.259>
have not made it into a JDK8 release, as far as I am aware. These increased
the ability for detecting computations that modify the map and throws an
IllegalStateException, as defined by the contract.

On Tue, Apr 19, 2016 at 1:14 AM, Dr Heinz M. Kabutz <
heinz at javaspecialists.eu> wrote:

> 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
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20160419/8cdd0962/attachment.html>


More information about the Concurrency-interest mailing list