ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

classic Classic list List threaded Threaded
27 messages Options
12
Reply | Threaded
Open this post in threaded view
|

ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

Dr Heinz M. Kabutz
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
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

Benjamin Manes
Unfortunately the improvements 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 <[hidden email]> 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: <a href="tel:%2B30%2069%2075%20595%20262" value="+306975595262" target="_blank">+30 69 75 595 262
Skype: kabutz

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

Dr Heinz M. Kabutz
Thanks for responding Ben and for pointing me at the "improvements".  However, if I use the algorithm with putIfAbsent() in the default implementation from the ConcurrentMap interface, then it works fine.  I don't see anything in the Map.computeIfAbsent() JavaDoc contract that would make my code invalid.  I guess inside ConcurrentHashMap there is a clause of "so the computation should be short and simple, and must not attempt to update any other mappings of this map."  I don't think IllegalStateException should be thrown in my case, because I'm not violating the Map.computeIfAbsent() contract.  Liskov Substitution Principle applies here I think.


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


Benjamin Manes wrote:
Unfortunately the improvements 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 <[hidden email]> 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: <a moz-do-not-send="true" href="tel:%2B30%2069%2075%20595%20262" value="+306975595262" target="_blank">+30 69 75 595 262
Skype: kabutz

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

Doug Lea
On 04/19/2016 05:35 AM, Dr Heinz M. Kabutz wrote:
>  I don't see anything in the
> Map.computeIfAbsent() JavaDoc contract that would make my code invalid.  I guess
> inside ConcurrentHashMap there is a clause of "so the computation should be
> short and simple, *and must not attempt to update any other mappings of this
> map*."

You are right that something should be said in ConcurrentMap and/or Map,
not just ConcurrentHashMap.

In any concurrent context, a computeIfAbsent function with side effects
that that modify map entries (including especially the initially absent one)
may be subject to livelock, deadlock, and/or exceptions.
An exception is the nicest of these options. So as Ben mentioned, we
updated to do so when possible.

Similar issues can arise even in non-concurrent settings when the
side-effecting operations on other map entries throw exceptions
or cause the initially-absent entry not to be absent.

-Doug


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

Andrew Haley
On 04/19/2016 12:40 PM, Doug Lea wrote:

> On 04/19/2016 05:35 AM, Dr Heinz M. Kabutz wrote:
>>  I don't see anything in the
>> Map.computeIfAbsent() JavaDoc contract that would make my code invalid.  I guess
>> inside ConcurrentHashMap there is a clause of "so the computation should be
>> short and simple, *and must not attempt to update any other mappings of this
>> map*."
>
> You are right that something should be said in ConcurrentMap and/or Map,
> not just ConcurrentHashMap.
>
> In any concurrent context, a computeIfAbsent function with side effects
> that that modify map entries (including especially the initially absent one)
> may be subject to livelock, deadlock, and/or exceptions.
> An exception is the nicest of these options. So as Ben mentioned, we
> updated to do so when possible.
>
> Similar issues can arise even in non-concurrent settings when the
> side-effecting operations on other map entries throw exceptions
> or cause the initially-absent entry not to be absent.

And indeed if you're trying to memoize a (possibly) recursive
function.  You end up having to do something like this:

    static <T, R> Function<T, R> memoize(Function<T, R> f) {
        HashMap<T, R> values = new HashMap<>();
        return t -> {
            R result = values.get(t);
            if (result == null) {
                result = f.apply(t);
                values.put(t, result);
            }
            return result;
        };
    }

computeIfAbsent() would be very nice here, but you can't use it.

Andrew.
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

Doug Lea
In reply to this post by Doug Lea
On 04/19/2016 11:43 AM, Per Mildner wrote:

>> In any concurrent context, a computeIfAbsent function with side effects
>> that that modify map entries (including especially the initially absent one)
>
> The documentation seems to explicitly exclude the initially absent map entry from the prohibited entries by saying "the computation … must not attempt to update any _other_ mappings”.
>
> Should this say "the computation … must not attempt to update any mappings”?

Yes. The wording implicitly assumed that readers already knew not to
modify the key's mapping.

In any case, this is already partially covered in the Map javadocs:
http://docs.oracle.com/javase/8/docs/api/java/util/Map.html#computeIfAbsent-K-java.util.function.Function-
      * <p>The mapping function should not modify this map during computation.

We could add something saying what might happen otherwise:
      * If it does so, the results of this operation are undefined, but may
      * include IllegalStateExceptions, or in concurrent contexts, deadlock
      * or livelock.
      *

-Doug




_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

Viktor Klang
Heinz,

There's also the option of going this route:

  package livedemo;

  import java.util.concurrent.*;
  import java.math.BigInteger;
  import java.util.Map;

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

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

    public CompletionStage<BigInteger> f(int n) {
      CompletableFuture<BigInteger> next = new CompletableFuture<>();
      CompletionStage<BigInteger> prev = cache.putIfAbsent(n, next);
      if (prev != null) return prev;
      else
        return f(n-1).thenCompose(v -> f(n-2).thenCompose(v2 -> { next.complete(v.add(v2)); return next; }));
    }
  }


Add Executor parameter to `f` and switch to thenComposeAsync to be able to parallelize it.
Also means that concurrent readers/writers won't block eachother (computeIfAbsent would do that for instance)

á la:

  package livedemo;

  import java.util.concurrent.*;
  import java.math.BigInteger;
  import java.util.Map;

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

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

    public CompletionStage<BigInteger> f(int n, Executor e) {
      CompletableFuture<BigInteger> next = new CompletableFuture<>();
      CompletionStage<BigInteger> prev = cache.putIfAbsent(n, next);
      if (prev != null) return prev;
      else
        return f(n-1, e).thenComposeAsync(v -> f(n-2, e).thenComposeAsync(v2 -> { next.complete(v.add(v2)); return next; }, e), e);
    }
  }


--
Cheers,

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

Dr Heinz M. Kabutz
Thanks so much Viktor for that code!  The part that I somehow missed was the empty CompletableFuture: CompletableFuture<BigInteger> next = new CompletableFuture<>();

Very interesting indeed.
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


Viktor Klang wrote:
Heinz,

There's also the option of going this route:

  package livedemo;

  import java.util.concurrent.*;
  import java.math.BigInteger;
  import java.util.Map;

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

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

    public CompletionStage<BigInteger> f(int n) {
      CompletableFuture<BigInteger> next = new CompletableFuture<>();
      CompletionStage<BigInteger> prev = cache.putIfAbsent(n, next);
      if (prev != null) return prev;
      else
        return f(n-1).thenCompose(v -> f(n-2).thenCompose(v2 -> { next.complete(v.add(v2)); return next; }));
    }
  }


Add Executor parameter to `f` and switch to thenComposeAsync to be able to parallelize it.
Also means that concurrent readers/writers won't block eachother (computeIfAbsent would do that for instance)

á la:

  package livedemo;

  import java.util.concurrent.*;
  import java.math.BigInteger;
  import java.util.Map;

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

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

    public CompletionStage<BigInteger> f(int n, Executor e) {
      CompletableFuture<BigInteger> next = new CompletableFuture<>();
      CompletionStage<BigInteger> prev = cache.putIfAbsent(n, next);
      if (prev != null) return prev;
      else
        return f(n-1, e).thenComposeAsync(v -> f(n-2, e).thenComposeAsync(v2 -> { next.complete(v.add(v2)); return next; }, e), e);
    }
  }


--
Cheers,

_______________________________________________ Concurrency-interest mailing list [hidden email] http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

Millies, Sebastian

I’m not sure I’m getting it. What’s significant about putting that empty CF in as a placeholder first? That is, what is the advantage over writing

 

public CompletionStage<BigInteger> f(int n) { 

  CompletionStage<BigInteger> prev = cache.get(n);

  if (prev != null) {

    return prev;

  }

  else {

    return f(n - 1).thenCompose(x ->

           f(n - 2).thenCompose(y -> {

           CompletableFuture<BigInteger> next = CompletableFuture.completedFuture(x.add(y));

           CompletionStage<BigInteger> v = cache.putIfAbsent(n, next);

           return prev != null ? v : next;

    }));

  }

}

 

Is it that in Viktor’s code, only the thread that first has a cache miss calls the computation that will complete the future, while in the above code there may be multiple computations, only one of which will eventually contribute to the result? And would that consideration only apply to the async version?

 

n  Sebastian

 

From: [hidden email] [mailto:[hidden email]] On Behalf Of Dr Heinz M. Kabutz
Sent: Saturday, April 23, 2016 7:31 AM
To: Viktor Klang
Cc: concurrency-interest
Subject: Re: [concurrency-interest] ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

 

Thanks so much Viktor for that code!  The part that I somehow missed was the empty CompletableFuture: CompletableFuture<BigInteger> next = new CompletableFuture<>();

Very interesting indeed.

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



Viktor Klang wrote:

Heinz,

There's also the option of going this route:

 

  package livedemo;

 

  import java.util.concurrent.*;

  import java.math.BigInteger;

  import java.util.Map;

 

  public class FibonacciCached {

    private final Map<Integer, CompletionStage<BigInteger>> cache;

 

    public FibonacciCached(Map<Integer, CompletionStage<BigInteger>> cache) {

      this.cache = cache;

      cache.put(0, CompletableFuture.completedFuture(BigInteger.ZERO));

      cache.put(1, CompletableFuture.completedFuture(BigInteger.ONE));

    }

 

    public CompletionStage<BigInteger> f(int n) {

      CompletableFuture<BigInteger> next = new CompletableFuture<>();

      CompletionStage<BigInteger> prev = cache.putIfAbsent(n, next);

      if (prev != null) return prev;

      else

        return f(n-1).thenCompose(v -> f(n-2).thenCompose(v2 -> { next.complete(v.add(v2)); return next; }));

    }

  }

 

 

Add Executor parameter to `f` and switch to thenComposeAsync to be able to parallelize it.

Also means that concurrent readers/writers won't block eachother (computeIfAbsent would do that for instance)

 

á la:

 

  package livedemo;

 

  import java.util.concurrent.*;

  import java.math.BigInteger;

  import java.util.Map;

 

  public class FibonacciCached {

    private final Map<Integer, CompletionStage<BigInteger>> cache;

 

    public FibonacciCached(Map<Integer, CompletionStage<BigInteger>> cache) {

      this.cache = cache;

      cache.put(0, CompletableFuture.completedFuture(BigInteger.ZERO));

      cache.put(1, CompletableFuture.completedFuture(BigInteger.ONE));

    }

 

    public CompletionStage<BigInteger> f(int n, Executor e) {

      CompletableFuture<BigInteger> next = new CompletableFuture<>();

      CompletionStage<BigInteger> prev = cache.putIfAbsent(n, next);

      if (prev != null) return prev;

      else

        return f(n-1, e).thenComposeAsync(v -> f(n-2, e).thenComposeAsync(v2 -> { next.complete(v.add(v2)); return next; }, e), e);

    }

  }

 

 

--

Cheers,

 

 
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
  

Software AG – Sitz/Registered office: Uhlandstraße 12, 64297 Darmstadt, Germany – Registergericht/Commercial register: Darmstadt HRB 1562 - Vorstand/Management Board: Karl-Heinz Streibich (Vorsitzender/Chairman), Eric Duffaut, Dr. Wolfram Jost, Arnd Zinnhardt; - Aufsichtsratsvorsitzender/Chairman of the Supervisory Board: Dr. Andreas Bereczky - http://www.softwareag.com


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

Viktor Klang
Hi Sebastian,

I only provided the code as an alternate solution to using computeIfAbsent, for a more «optimized»[1] version, see the snippet below.

If / when CHM becomes completely non-blocking, this would mean that readers would never block other readers nor other writers, and writers would never block readers or other writers.

package livedemo;

  import java.util.concurrent.*;
  import java.math.BigInteger;
  import java.util.Map;

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

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

    public CompletionStage<BigInteger> f(int n, Executor e) {
      CompletionStage<BigInteger> ret = cache.get(n);
      if (ret == null) {
        final CompletableFuture<BigInteger> compute = new CompletableFuture<>();
        ret = cache.putIfAbsent(n, compute);
        if (ret == null)
          ret = f(n-1, e).thenComposeAsync(v -> f(n-2, e).thenComposeAsync(v2 -> { compute.complete(v.add(v2)); return compute; }, e), e);
      }
      return ret;
    }
  }

1: It's very much possible and recommended to not make the first thenCompose an async one, as only the addition of v and v2 might be "expensive" (for large additions).

On Sat, Apr 23, 2016 at 12:50 PM, Millies, Sebastian <[hidden email]> wrote:

I’m not sure I’m getting it. What’s significant about putting that empty CF in as a placeholder first? That is, what is the advantage over writing

 

public CompletionStage<BigInteger> f(int n) { 

  CompletionStage<BigInteger> prev = cache.get(n);

  if (prev != null) {

    return prev;

  }

  else {

    return f(n - 1).thenCompose(x ->

           f(n - 2).thenCompose(y -> {

           CompletableFuture<BigInteger> next = CompletableFuture.completedFuture(x.add(y));

           CompletionStage<BigInteger> v = cache.putIfAbsent(n, next);

           return prev != null ? v : next;

    }));

  }

}

 

Is it that in Viktor’s code, only the thread that first has a cache miss calls the computation that will complete the future, while in the above code there may be multiple computations, only one of which will eventually contribute to the result? And would that consideration only apply to the async version?

 

n  Sebastian

 

From: [hidden email] [mailto:[hidden email]] On Behalf Of Dr Heinz M. Kabutz
Sent: Saturday, April 23, 2016 7:31 AM
To: Viktor Klang
Cc: concurrency-interest
Subject: Re: [concurrency-interest] ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

 

Thanks so much Viktor for that code!  The part that I somehow missed was the empty CompletableFuture: CompletableFuture<BigInteger> next = new CompletableFuture<>();

Very interesting indeed.

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



Viktor Klang wrote:

Heinz,

There's also the option of going this route:

 

  package livedemo;

 

  import java.util.concurrent.*;

  import java.math.BigInteger;

  import java.util.Map;

 

  public class FibonacciCached {

    private final Map<Integer, CompletionStage<BigInteger>> cache;

 

    public FibonacciCached(Map<Integer, CompletionStage<BigInteger>> cache) {

      this.cache = cache;

      cache.put(0, CompletableFuture.completedFuture(BigInteger.ZERO));

      cache.put(1, CompletableFuture.completedFuture(BigInteger.ONE));

    }

 

    public CompletionStage<BigInteger> f(int n) {

      CompletableFuture<BigInteger> next = new CompletableFuture<>();

      CompletionStage<BigInteger> prev = cache.putIfAbsent(n, next);

      if (prev != null) return prev;

      else

        return f(n-1).thenCompose(v -> f(n-2).thenCompose(v2 -> { next.complete(v.add(v2)); return next; }));

    }

  }

 

 

Add Executor parameter to `f` and switch to thenComposeAsync to be able to parallelize it.

Also means that concurrent readers/writers won't block eachother (computeIfAbsent would do that for instance)

 

á la:

 

  package livedemo;

 

  import java.util.concurrent.*;

  import java.math.BigInteger;

  import java.util.Map;

 

  public class FibonacciCached {

    private final Map<Integer, CompletionStage<BigInteger>> cache;

 

    public FibonacciCached(Map<Integer, CompletionStage<BigInteger>> cache) {

      this.cache = cache;

      cache.put(0, CompletableFuture.completedFuture(BigInteger.ZERO));

      cache.put(1, CompletableFuture.completedFuture(BigInteger.ONE));

    }

 

    public CompletionStage<BigInteger> f(int n, Executor e) {

      CompletableFuture<BigInteger> next = new CompletableFuture<>();

      CompletionStage<BigInteger> prev = cache.putIfAbsent(n, next);

      if (prev != null) return prev;

      else

        return f(n-1, e).thenComposeAsync(v -> f(n-2, e).thenComposeAsync(v2 -> { next.complete(v.add(v2)); return next; }, e), e);

    }

  }

 

 

--

Cheers,

 

 
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
  

Software AG – Sitz/Registered office: Uhlandstraße 12, 64297 Darmstadt, Germany – Registergericht/Commercial register: Darmstadt HRB 1562 - Vorstand/Management Board: Karl-Heinz Streibich (Vorsitzender/Chairman), Eric Duffaut, Dr. Wolfram Jost, Arnd Zinnhardt; - Aufsichtsratsvorsitzender/Chairman of the Supervisory Board: Dr. Andreas Bereczky - http://www.softwareag.com




--
Cheers,

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

Henri Tremblay
Hi Viktor,

Thanks a lot for those examples. They are crystal clear demonstration of a nice CompletableFuture usage.

Really nice
Henri

On 23 April 2016 at 15:45, Viktor Klang <[hidden email]> wrote:
Hi Sebastian,

I only provided the code as an alternate solution to using computeIfAbsent, for a more «optimized»[1] version, see the snippet below.

If / when CHM becomes completely non-blocking, this would mean that readers would never block other readers nor other writers, and writers would never block readers or other writers.

package livedemo;

  import java.util.concurrent.*;
  import java.math.BigInteger;
  import java.util.Map;

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

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

    public CompletionStage<BigInteger> f(int n, Executor e) {
      CompletionStage<BigInteger> ret = cache.get(n);
      if (ret == null) {
        final CompletableFuture<BigInteger> compute = new CompletableFuture<>();
        ret = cache.putIfAbsent(n, compute);
        if (ret == null)
          ret = f(n-1, e).thenComposeAsync(v -> f(n-2, e).thenComposeAsync(v2 -> { compute.complete(v.add(v2)); return compute; }, e), e);
      }
      return ret;
    }
  }

1: It's very much possible and recommended to not make the first thenCompose an async one, as only the addition of v and v2 might be "expensive" (for large additions).

On Sat, Apr 23, 2016 at 12:50 PM, Millies, Sebastian <[hidden email]> wrote:

I’m not sure I’m getting it. What’s significant about putting that empty CF in as a placeholder first? That is, what is the advantage over writing

 

public CompletionStage<BigInteger> f(int n) { 

  CompletionStage<BigInteger> prev = cache.get(n);

  if (prev != null) {

    return prev;

  }

  else {

    return f(n - 1).thenCompose(x ->

           f(n - 2).thenCompose(y -> {

           CompletableFuture<BigInteger> next = CompletableFuture.completedFuture(x.add(y));

           CompletionStage<BigInteger> v = cache.putIfAbsent(n, next);

           return prev != null ? v : next;

    }));

  }

}

 

Is it that in Viktor’s code, only the thread that first has a cache miss calls the computation that will complete the future, while in the above code there may be multiple computations, only one of which will eventually contribute to the result? And would that consideration only apply to the async version?

 

n  Sebastian

 

From: [hidden email] [mailto:[hidden email]] On Behalf Of Dr Heinz M. Kabutz
Sent: Saturday, April 23, 2016 7:31 AM
To: Viktor Klang
Cc: concurrency-interest
Subject: Re: [concurrency-interest] ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

 

Thanks so much Viktor for that code!  The part that I somehow missed was the empty CompletableFuture: CompletableFuture<BigInteger> next = new CompletableFuture<>();

Very interesting indeed.

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



Viktor Klang wrote:

Heinz,

There's also the option of going this route:

 

  package livedemo;

 

  import java.util.concurrent.*;

  import java.math.BigInteger;

  import java.util.Map;

 

  public class FibonacciCached {

    private final Map<Integer, CompletionStage<BigInteger>> cache;

 

    public FibonacciCached(Map<Integer, CompletionStage<BigInteger>> cache) {

      this.cache = cache;

      cache.put(0, CompletableFuture.completedFuture(BigInteger.ZERO));

      cache.put(1, CompletableFuture.completedFuture(BigInteger.ONE));

    }

 

    public CompletionStage<BigInteger> f(int n) {

      CompletableFuture<BigInteger> next = new CompletableFuture<>();

      CompletionStage<BigInteger> prev = cache.putIfAbsent(n, next);

      if (prev != null) return prev;

      else

        return f(n-1).thenCompose(v -> f(n-2).thenCompose(v2 -> { next.complete(v.add(v2)); return next; }));

    }

  }

 

 

Add Executor parameter to `f` and switch to thenComposeAsync to be able to parallelize it.

Also means that concurrent readers/writers won't block eachother (computeIfAbsent would do that for instance)

 

á la:

 

  package livedemo;

 

  import java.util.concurrent.*;

  import java.math.BigInteger;

  import java.util.Map;

 

  public class FibonacciCached {

    private final Map<Integer, CompletionStage<BigInteger>> cache;

 

    public FibonacciCached(Map<Integer, CompletionStage<BigInteger>> cache) {

      this.cache = cache;

      cache.put(0, CompletableFuture.completedFuture(BigInteger.ZERO));

      cache.put(1, CompletableFuture.completedFuture(BigInteger.ONE));

    }

 

    public CompletionStage<BigInteger> f(int n, Executor e) {

      CompletableFuture<BigInteger> next = new CompletableFuture<>();

      CompletionStage<BigInteger> prev = cache.putIfAbsent(n, next);

      if (prev != null) return prev;

      else

        return f(n-1, e).thenComposeAsync(v -> f(n-2, e).thenComposeAsync(v2 -> { next.complete(v.add(v2)); return next; }, e), e);

    }

  }

 

 

--

Cheers,

 

 
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
  

Software AG – Sitz/Registered office: Uhlandstraße 12, 64297 Darmstadt, Germany – Registergericht/Commercial register: Darmstadt HRB 1562 - Vorstand/Management Board: Karl-Heinz Streibich (Vorsitzender/Chairman), Eric Duffaut, Dr. Wolfram Jost, Arnd Zinnhardt; - Aufsichtsratsvorsitzender/Chairman of the Supervisory Board: Dr. Andreas Bereczky - http://www.softwareag.com




--
Cheers,

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest



_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

Millies, Sebastian

Yes, thank you very much,  very instructive. I wonder how expensive the asynchronous computation step must be to make it worthwhile speed-wise. When computing the 2000th Fibonacci number on my quadcore, at least, the asynchronous “optimized” CF version performs 10 – 20 times worse compared to single-threaded code using a memoizer  with a simple HashMap, such as the one posted by Andrew Haley in this thread.

n  Sebastian

 

From: Henri Tremblay [mailto:[hidden email]]
Sent: Monday, April 25, 2016 7:02 PM
To: Viktor Klang
Cc: Millies, Sebastian; concurrency-interest
Subject: Re: [concurrency-interest] ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

 

Hi Viktor,

 

Thanks a lot for those examples. They are crystal clear demonstration of a nice CompletableFuture usage.

 

Really nice

Henri

 

On 23 April 2016 at 15:45, Viktor Klang <[hidden email]> wrote:

Hi Sebastian,

 

I only provided the code as an alternate solution to using computeIfAbsent, for a more «optimized»[1] version, see the snippet below.


If / when CHM becomes completely non-blocking, this would mean that readers would never block other readers nor other writers, and writers would never block readers or other writers.

package livedemo;

 

  import java.util.concurrent.*;

  import java.math.BigInteger;

  import java.util.Map;

 

  public class FibonacciCached {

    private final Map<Integer, CompletionStage<BigInteger>> cache;

 

    public FibonacciCached(Map<Integer, CompletionStage<BigInteger>> cache) {

      this.cache = cache;

      cache.put(0, CompletableFuture.completedFuture(BigInteger.ZERO));

      cache.put(1, CompletableFuture.completedFuture(BigInteger.ONE));

    }

 

    public CompletionStage<BigInteger> f(int n, Executor e) {

      CompletionStage<BigInteger> ret = cache.get(n);

      if (ret == null) {

        final CompletableFuture<BigInteger> compute = new CompletableFuture<>();

        ret = cache.putIfAbsent(n, compute);

        if (ret == null)

          ret = f(n-1, e).thenComposeAsync(v -> f(n-2, e).thenComposeAsync(v2 -> { compute.complete(v.add(v2)); return compute; }, e), e);

      }

      return ret;

    }

  }

1: It's very much possible and recommended to not make the first thenCompose an async one, as only the addition of v and v2 might be "expensive" (for large additions).

 

On Sat, Apr 23, 2016 at 12:50 PM, Millies, Sebastian <[hidden email]> wrote:

I’m not sure I’m getting it. What’s significant about putting that empty CF in as a placeholder first? That is, what is the advantage over writing

 

public CompletionStage<BigInteger> f(int n) { 

  CompletionStage<BigInteger> prev = cache.get(n);

  if (prev != null) {

    return prev;

  }

  else {

    return f(n - 1).thenCompose(x ->

           f(n - 2).thenCompose(y -> {

           CompletableFuture<BigInteger> next = CompletableFuture.completedFuture(x.add(y));

           CompletionStage<BigInteger> v = cache.putIfAbsent(n, next);

           return prev != null ? v : next;

    }));

  }

}

 

Is it that in Viktor’s code, only the thread that first has a cache miss calls the computation that will complete the future, while in the above code there may be multiple computations, only one of which will eventually contribute to the result? And would that consideration only apply to the async version?

 

n  Sebastian

 

From: [hidden email] [mailto:[hidden email]] On Behalf Of Dr Heinz M. Kabutz
Sent: Saturday, April 23, 2016 7:31 AM
To: Viktor Klang
Cc: concurrency-interest
Subject: Re: [concurrency-interest] ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

 

Thanks so much Viktor for that code!  The part that I somehow missed was the empty CompletableFuture: CompletableFuture<BigInteger> next = new CompletableFuture<>();

Very interesting indeed.

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



Viktor Klang wrote:

Heinz,

There's also the option of going this route:

 

  package livedemo;

 

  import java.util.concurrent.*;

  import java.math.BigInteger;

  import java.util.Map;

 

  public class FibonacciCached {

    private final Map<Integer, CompletionStage<BigInteger>> cache;

 

    public FibonacciCached(Map<Integer, CompletionStage<BigInteger>> cache) {

      this.cache = cache;

      cache.put(0, CompletableFuture.completedFuture(BigInteger.ZERO));

      cache.put(1, CompletableFuture.completedFuture(BigInteger.ONE));

    }

 

    public CompletionStage<BigInteger> f(int n) {

      CompletableFuture<BigInteger> next = new CompletableFuture<>();

      CompletionStage<BigInteger> prev = cache.putIfAbsent(n, next);

      if (prev != null) return prev;

      else

        return f(n-1).thenCompose(v -> f(n-2).thenCompose(v2 -> { next.complete(v.add(v2)); return next; }));

    }

  }

 

 

Add Executor parameter to `f` and switch to thenComposeAsync to be able to parallelize it.

Also means that concurrent readers/writers won't block eachother (computeIfAbsent would do that for instance)

 

á la:

 

  package livedemo;

 

  import java.util.concurrent.*;

  import java.math.BigInteger;

  import java.util.Map;

 

  public class FibonacciCached {

    private final Map<Integer, CompletionStage<BigInteger>> cache;

 

    public FibonacciCached(Map<Integer, CompletionStage<BigInteger>> cache) {

      this.cache = cache;

      cache.put(0, CompletableFuture.completedFuture(BigInteger.ZERO));

      cache.put(1, CompletableFuture.completedFuture(BigInteger.ONE));

    }

 

    public CompletionStage<BigInteger> f(int n, Executor e) {

      CompletableFuture<BigInteger> next = new CompletableFuture<>();

      CompletionStage<BigInteger> prev = cache.putIfAbsent(n, next);

      if (prev != null) return prev;

      else

        return f(n-1, e).thenComposeAsync(v -> f(n-2, e).thenComposeAsync(v2 -> { next.complete(v.add(v2)); return next; }, e), e);

    }

  }

 

 

--

Cheers,

 

 
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
  

 

Software AG – Sitz/Registered office: Uhlandstraße 12, 64297 Darmstadt, Germany – Registergericht/Commercial register: Darmstadt HRB 1562 - Vorstand/Management Board: Karl-Heinz Streibich (Vorsitzender/Chairman), Eric Duffaut, Dr. Wolfram Jost, Arnd Zinnhardt; - Aufsichtsratsvorsitzender/Chairman of the Supervisory Board: Dr. Andreas Bereczky - http://www.softwareag.com



 

--

Cheers,


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

 


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

Dr Heinz M. Kabutz
You need to combine it with Dijkstra's sum of squares and parallelise BigInteger.multiply to see good results 

On Tuesday, 26 April 2016, Millies, Sebastian <[hidden email]> wrote:

Yes, thank you very much,  very instructive. I wonder how expensive the asynchronous computation step must be to make it worthwhile speed-wise. When computing the 2000th Fibonacci number on my quadcore, at least, the asynchronous “optimized” CF version performs 10 – 20 times worse compared to single-threaded code using a memoizer  with a simple HashMap, such as the one posted by Andrew Haley in this thread.

n  Sebastian

 

From: Henri Tremblay [mailto:<a href="javascript:_e(%7B%7D,&#39;cvml&#39;,&#39;henri.tremblay@gmail.com&#39;);" target="_blank">henri.tremblay@...]
Sent: Monday, April 25, 2016 7:02 PM
To: Viktor Klang
Cc: Millies, Sebastian; concurrency-interest
Subject: Re: [concurrency-interest] ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

 

Hi Viktor,

 

Thanks a lot for those examples. They are crystal clear demonstration of a nice CompletableFuture usage.

 

Really nice

Henri

 

On 23 April 2016 at 15:45, Viktor Klang <<a href="javascript:_e(%7B%7D,&#39;cvml&#39;,&#39;viktor.klang@gmail.com&#39;);" target="_blank">viktor.klang@...> wrote:

Hi Sebastian,

 

I only provided the code as an alternate solution to using computeIfAbsent, for a more «optimized»[1] version, see the snippet below.


If / when CHM becomes completely non-blocking, this would mean that readers would never block other readers nor other writers, and writers would never block readers or other writers.

package livedemo;

 

  import java.util.concurrent.*;

  import java.math.BigInteger;

  import java.util.Map;

 

  public class FibonacciCached {

    private final Map<Integer, CompletionStage<BigInteger>> cache;

 

    public FibonacciCached(Map<Integer, CompletionStage<BigInteger>> cache) {

      this.cache = cache;

      cache.put(0, CompletableFuture.completedFuture(BigInteger.ZERO));

      cache.put(1, CompletableFuture.completedFuture(BigInteger.ONE));

    }

 

    public CompletionStage<BigInteger> f(int n, Executor e) {

      CompletionStage<BigInteger> ret = cache.get(n);

      if (ret == null) {

        final CompletableFuture<BigInteger> compute = new CompletableFuture<>();

        ret = cache.putIfAbsent(n, compute);

        if (ret == null)

          ret = f(n-1, e).thenComposeAsync(v -> f(n-2, e).thenComposeAsync(v2 -> { compute.complete(v.add(v2)); return compute; }, e), e);

      }

      return ret;

    }

  }

1: It's very much possible and recommended to not make the first thenCompose an async one, as only the addition of v and v2 might be "expensive" (for large additions).

 

On Sat, Apr 23, 2016 at 12:50 PM, Millies, Sebastian <<a href="javascript:_e(%7B%7D,&#39;cvml&#39;,&#39;Sebastian.Millies@softwareag.com&#39;);" target="_blank">Sebastian.Millies@...> wrote:

I’m not sure I’m getting it. What’s significant about putting that empty CF in as a placeholder first? That is, what is the advantage over writing

 

public CompletionStage<BigInteger> f(int n) { 

  CompletionStage<BigInteger> prev = cache.get(n);

  if (prev != null) {

    return prev;

  }

  else {

    return f(n - 1).thenCompose(x ->

           f(n - 2).thenCompose(y -> {

           CompletableFuture<BigInteger> next = CompletableFuture.completedFuture(x.add(y));

           CompletionStage<BigInteger> v = cache.putIfAbsent(n, next);

           return prev != null ? v : next;

    }));

  }

}

 

Is it that in Viktor’s code, only the thread that first has a cache miss calls the computation that will complete the future, while in the above code there may be multiple computations, only one of which will eventually contribute to the result? And would that consideration only apply to the async version?

 

n  Sebastian

 

From: <a href="javascript:_e(%7B%7D,&#39;cvml&#39;,&#39;concurrency-interest-bounces@cs.oswego.edu&#39;);" target="_blank">concurrency-interest-bounces@... [mailto:<a href="javascript:_e(%7B%7D,&#39;cvml&#39;,&#39;concurrency-interest-bounces@cs.oswego.edu&#39;);" target="_blank">concurrency-interest-bounces@...] On Behalf Of Dr Heinz M. Kabutz
Sent: Saturday, April 23, 2016 7:31 AM
To: Viktor Klang
Cc: concurrency-interest
Subject: Re: [concurrency-interest] ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

 

Thanks so much Viktor for that code!  The part that I somehow missed was the empty CompletableFuture: CompletableFuture<BigInteger> next = new CompletableFuture<>();

Very interesting indeed.

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



Viktor Klang wrote:

Heinz,

There's also the option of going this route:

 

  package livedemo;

 

  import java.util.concurrent.*;

  import java.math.BigInteger;

  import java.util.Map;

 

  public class FibonacciCached {

    private final Map<Integer, CompletionStage<BigInteger>> cache;

 

    public FibonacciCached(Map<Integer, CompletionStage<BigInteger>> cache) {

      this.cache = cache;

      cache.put(0, CompletableFuture.completedFuture(BigInteger.ZERO));

      cache.put(1, CompletableFuture.completedFuture(BigInteger.ONE));

    }

 

    public CompletionStage<BigInteger> f(int n) {

      CompletableFuture<BigInteger> next = new CompletableFuture<>();

      CompletionStage<BigInteger> prev = cache.putIfAbsent(n, next);

      if (prev != null) return prev;

      else

        return f(n-1).thenCompose(v -> f(n-2).thenCompose(v2 -> { next.complete(v.add(v2)); return next; }));

    }

  }

 

 

Add Executor parameter to `f` and switch to thenComposeAsync to be able to parallelize it.

Also means that concurrent readers/writers won't block eachother (computeIfAbsent would do that for instance)

 

á la:

 

  package livedemo;

 

  import java.util.concurrent.*;

  import java.math.BigInteger;

  import java.util.Map;

 

  public class FibonacciCached {

    private final Map<Integer, CompletionStage<BigInteger>> cache;

 

    public FibonacciCached(Map<Integer, CompletionStage<BigInteger>> cache) {

      this.cache = cache;

      cache.put(0, CompletableFuture.completedFuture(BigInteger.ZERO));

      cache.put(1, CompletableFuture.completedFuture(BigInteger.ONE));

    }

 

    public CompletionStage<BigInteger> f(int n, Executor e) {

      CompletableFuture<BigInteger> next = new CompletableFuture<>();

      CompletionStage<BigInteger> prev = cache.putIfAbsent(n, next);

      if (prev != null) return prev;

      else

        return f(n-1, e).thenComposeAsync(v -> f(n-2, e).thenComposeAsync(v2 -> { next.complete(v.add(v2)); return next; }, e), e);

    }

  }

 

 

--

Cheers,

 

 
_______________________________________________
Concurrency-interest mailing list
<a href="javascript:_e(%7B%7D,&#39;cvml&#39;,&#39;Concurrency-interest@cs.oswego.edu&#39;);" target="_blank">Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
  

 

Software AG – Sitz/Registered office: Uhlandstraße 12, 64297 Darmstadt, Germany – Registergericht/Commercial register: Darmstadt HRB 1562 - Vorstand/Management Board: Karl-Heinz Streibich (Vorsitzender/Chairman), Eric Duffaut, Dr. Wolfram Jost, Arnd Zinnhardt; - Aufsichtsratsvorsitzender/Chairman of the Supervisory Board: Dr. Andreas Bereczky - http://www.softwareag.com



 

--

Cheers,


_______________________________________________
Concurrency-interest mailing list
<a href="javascript:_e(%7B%7D,&#39;cvml&#39;,&#39;Concurrency-interest@cs.oswego.edu&#39;);" target="_blank">Concurrency-interest@...
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

 



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


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

Viktor Klang
In reply to this post by Millies, Sebastian

Hi Sebastian!

(IMO) Async is neverr for performance, it is for scalability. (And resilience; Parallelization is for performance)

What does the scaling profile look for 1..N concurrent accesses?

And did you try using thenCompose iso. thenComposeAsync for the initial step?

Also, which executor did you use and using what config?

A lot of questions, I know!
--
Cheers,

On Apr 26, 2016 5:09 PM, "Millies, Sebastian" <[hidden email]> wrote:

Yes, thank you very much,  very instructive. I wonder how expensive the asynchronous computation step must be to make it worthwhile speed-wise. When computing the 2000th Fibonacci number on my quadcore, at least, the asynchronous “optimized” CF version performs 10 – 20 times worse compared to single-threaded code using a memoizer  with a simple HashMap, such as the one posted by Andrew Haley in this thread.

n  Sebastian

 

From: Henri Tremblay [mailto:[hidden email]]
Sent: Monday, April 25, 2016 7:02 PM
To: Viktor Klang
Cc: Millies, Sebastian; concurrency-interest
Subject: Re: [concurrency-interest] ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

 

Hi Viktor,

 

Thanks a lot for those examples. They are crystal clear demonstration of a nice CompletableFuture usage.

 

Really nice

Henri

 

On 23 April 2016 at 15:45, Viktor Klang <[hidden email]> wrote:

Hi Sebastian,

 

I only provided the code as an alternate solution to using computeIfAbsent, for a more «optimized»[1] version, see the snippet below.


If / when CHM becomes completely non-blocking, this would mean that readers would never block other readers nor other writers, and writers would never block readers or other writers.

package livedemo;

 

  import java.util.concurrent.*;

  import java.math.BigInteger;

  import java.util.Map;

 

  public class FibonacciCached {

    private final Map<Integer, CompletionStage<BigInteger>> cache;

 

    public FibonacciCached(Map<Integer, CompletionStage<BigInteger>> cache) {

      this.cache = cache;

      cache.put(0, CompletableFuture.completedFuture(BigInteger.ZERO));

      cache.put(1, CompletableFuture.completedFuture(BigInteger.ONE));

    }

 

    public CompletionStage<BigInteger> f(int n, Executor e) {

      CompletionStage<BigInteger> ret = cache.get(n);

      if (ret == null) {

        final CompletableFuture<BigInteger> compute = new CompletableFuture<>();

        ret = cache.putIfAbsent(n, compute);

        if (ret == null)

          ret = f(n-1, e).thenComposeAsync(v -> f(n-2, e).thenComposeAsync(v2 -> { compute.complete(v.add(v2)); return compute; }, e), e);

      }

      return ret;

    }

  }

1: It's very much possible and recommended to not make the first thenCompose an async one, as only the addition of v and v2 might be "expensive" (for large additions).

 

On Sat, Apr 23, 2016 at 12:50 PM, Millies, Sebastian <[hidden email]> wrote:

I’m not sure I’m getting it. What’s significant about putting that empty CF in as a placeholder first? That is, what is the advantage over writing

 

public CompletionStage<BigInteger> f(int n) { 

  CompletionStage<BigInteger> prev = cache.get(n);

  if (prev != null) {

    return prev;

  }

  else {

    return f(n - 1).thenCompose(x ->

           f(n - 2).thenCompose(y -> {

           CompletableFuture<BigInteger> next = CompletableFuture.completedFuture(x.add(y));

           CompletionStage<BigInteger> v = cache.putIfAbsent(n, next);

           return prev != null ? v : next;

    }));

  }

}

 

Is it that in Viktor’s code, only the thread that first has a cache miss calls the computation that will complete the future, while in the above code there may be multiple computations, only one of which will eventually contribute to the result? And would that consideration only apply to the async version?

 

n  Sebastian

 

From: [hidden email] [mailto:[hidden email]] On Behalf Of Dr Heinz M. Kabutz
Sent: Saturday, April 23, 2016 7:31 AM
To: Viktor Klang
Cc: concurrency-interest
Subject: Re: [concurrency-interest] ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

 

Thanks so much Viktor for that code!  The part that I somehow missed was the empty CompletableFuture: CompletableFuture<BigInteger> next = new CompletableFuture<>();

Very interesting indeed.

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



Viktor Klang wrote:

Heinz,

There's also the option of going this route:

 

  package livedemo;

 

  import java.util.concurrent.*;

  import java.math.BigInteger;

  import java.util.Map;

 

  public class FibonacciCached {

    private final Map<Integer, CompletionStage<BigInteger>> cache;

 

    public FibonacciCached(Map<Integer, CompletionStage<BigInteger>> cache) {

      this.cache = cache;

      cache.put(0, CompletableFuture.completedFuture(BigInteger.ZERO));

      cache.put(1, CompletableFuture.completedFuture(BigInteger.ONE));

    }

 

    public CompletionStage<BigInteger> f(int n) {

      CompletableFuture<BigInteger> next = new CompletableFuture<>();

      CompletionStage<BigInteger> prev = cache.putIfAbsent(n, next);

      if (prev != null) return prev;

      else

        return f(n-1).thenCompose(v -> f(n-2).thenCompose(v2 -> { next.complete(v.add(v2)); return next; }));

    }

  }

 

 

Add Executor parameter to `f` and switch to thenComposeAsync to be able to parallelize it.

Also means that concurrent readers/writers won't block eachother (computeIfAbsent would do that for instance)

 

á la:

 

  package livedemo;

 

  import java.util.concurrent.*;

  import java.math.BigInteger;

  import java.util.Map;

 

  public class FibonacciCached {

    private final Map<Integer, CompletionStage<BigInteger>> cache;

 

    public FibonacciCached(Map<Integer, CompletionStage<BigInteger>> cache) {

      this.cache = cache;

      cache.put(0, CompletableFuture.completedFuture(BigInteger.ZERO));

      cache.put(1, CompletableFuture.completedFuture(BigInteger.ONE));

    }

 

    public CompletionStage<BigInteger> f(int n, Executor e) {

      CompletableFuture<BigInteger> next = new CompletableFuture<>();

      CompletionStage<BigInteger> prev = cache.putIfAbsent(n, next);

      if (prev != null) return prev;

      else

        return f(n-1, e).thenComposeAsync(v -> f(n-2, e).thenComposeAsync(v2 -> { next.complete(v.add(v2)); return next; }, e), e);

    }

  }

 

 

--

Cheers,

 

 
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
  

 

Software AG – Sitz/Registered office: Uhlandstraße 12, 64297 Darmstadt, Germany – Registergericht/Commercial register: Darmstadt HRB 1562 - Vorstand/Management Board: Karl-Heinz Streibich (Vorsitzender/Chairman), Eric Duffaut, Dr. Wolfram Jost, Arnd Zinnhardt; - Aufsichtsratsvorsitzender/Chairman of the Supervisory Board: Dr. Andreas Bereczky - http://www.softwareag.com



 

--

Cheers,


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

 


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

Millies, Sebastian

Hello Viktor,

 

as I don’t know if attachments are alright in this group, I have put the code and benchmark in a gist:

https://gist.github.com/smillies/0cceb17501f74c4f53bf4930eba61889

 

n  Sebastian

 

From: Viktor Klang [mailto:[hidden email]]
Sent: Tuesday, April 26, 2016 5:34 PM
To: Millies, Sebastian
Cc: concurrency-interest; Henri Tremblay
Subject: RE: [concurrency-interest] ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

 

Hi Sebastian!

(IMO) Async is neverr for performance, it is for scalability. (And resilience; Parallelization is for performance)

What does the scaling profile look for 1..N concurrent accesses?

And did you try using thenCompose iso. thenComposeAsync for the initial step?

Also, which executor did you use and using what config?

A lot of questions, I know!
--
Cheers,

On Apr 26, 2016 5:09 PM, "Millies, Sebastian" <[hidden email]> wrote:

Yes, thank you very much,  very instructive. I wonder how expensive the asynchronous computation step must be to make it worthwhile speed-wise. When computing the 2000th Fibonacci number on my quadcore, at least, the asynchronous “optimized” CF version performs 10 – 20 times worse compared to single-threaded code using a memoizer  with a simple HashMap, such as the one posted by Andrew Haley in this thread.

n  Sebastian

 

From: Henri Tremblay [mailto:[hidden email]]
Sent: Monday, April 25, 2016 7:02 PM
To: Viktor Klang
Cc: Millies, Sebastian; concurrency-interest
Subject: Re: [concurrency-interest] ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

 

Hi Viktor,

 

Thanks a lot for those examples. They are crystal clear demonstration of a nice CompletableFuture usage.

 

Really nice

Henri

 

On 23 April 2016 at 15:45, Viktor Klang <[hidden email]> wrote:

Hi Sebastian,

 

I only provided the code as an alternate solution to using computeIfAbsent, for a more «optimized»[1] version, see the snippet below.


If / when CHM becomes completely non-blocking, this would mean that readers would never block other readers nor other writers, and writers would never block readers or other writers.

package livedemo;

 

  import java.util.concurrent.*;

  import java.math.BigInteger;

  import java.util.Map;

 

  public class FibonacciCached {

    private final Map<Integer, CompletionStage<BigInteger>> cache;

 

    public FibonacciCached(Map<Integer, CompletionStage<BigInteger>> cache) {

      this.cache = cache;

      cache.put(0, CompletableFuture.completedFuture(BigInteger.ZERO));

      cache.put(1, CompletableFuture.completedFuture(BigInteger.ONE));

    }

 

    public CompletionStage<BigInteger> f(int n, Executor e) {

      CompletionStage<BigInteger> ret = cache.get(n);

      if (ret == null) {

        final CompletableFuture<BigInteger> compute = new CompletableFuture<>();

        ret = cache.putIfAbsent(n, compute);

        if (ret == null)

          ret = f(n-1, e).thenComposeAsync(v -> f(n-2, e).thenComposeAsync(v2 -> { compute.complete(v.add(v2)); return compute; }, e), e);

      }

      return ret;

    }

  }

1: It's very much possible and recommended to not make the first thenCompose an async one, as only the addition of v and v2 might be "expensive" (for large additions).

 

On Sat, Apr 23, 2016 at 12:50 PM, Millies, Sebastian <[hidden email]> wrote:

I’m not sure I’m getting it. What’s significant about putting that empty CF in as a placeholder first? That is, what is the advantage over writing

 

public CompletionStage<BigInteger> f(int n) { 

  CompletionStage<BigInteger> prev = cache.get(n);

  if (prev != null) {

    return prev;

  }

  else {

    return f(n - 1).thenCompose(x ->

           f(n - 2).thenCompose(y -> {

           CompletableFuture<BigInteger> next = CompletableFuture.completedFuture(x.add(y));

           CompletionStage<BigInteger> v = cache.putIfAbsent(n, next);

           return prev != null ? v : next;

    }));

  }

}

 

Is it that in Viktor’s code, only the thread that first has a cache miss calls the computation that will complete the future, while in the above code there may be multiple computations, only one of which will eventually contribute to the result? And would that consideration only apply to the async version?

 

n  Sebastian

 

From: [hidden email] [mailto:[hidden email]] On Behalf Of Dr Heinz M. Kabutz
Sent: Saturday, April 23, 2016 7:31 AM
To: Viktor Klang
Cc: concurrency-interest
Subject: Re: [concurrency-interest] ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

 

Thanks so much Viktor for that code!  The part that I somehow missed was the empty CompletableFuture: CompletableFuture<BigInteger> next = new CompletableFuture<>();

Very interesting indeed.

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



Viktor Klang wrote:

Heinz,

There's also the option of going this route:

 

  package livedemo;

 

  import java.util.concurrent.*;

  import java.math.BigInteger;

  import java.util.Map;

 

  public class FibonacciCached {

    private final Map<Integer, CompletionStage<BigInteger>> cache;

 

    public FibonacciCached(Map<Integer, CompletionStage<BigInteger>> cache) {

      this.cache = cache;

      cache.put(0, CompletableFuture.completedFuture(BigInteger.ZERO));

      cache.put(1, CompletableFuture.completedFuture(BigInteger.ONE));

    }

 

    public CompletionStage<BigInteger> f(int n) {

      CompletableFuture<BigInteger> next = new CompletableFuture<>();

      CompletionStage<BigInteger> prev = cache.putIfAbsent(n, next);

      if (prev != null) return prev;

      else

        return f(n-1).thenCompose(v -> f(n-2).thenCompose(v2 -> { next.complete(v.add(v2)); return next; }));

    }

  }

 

 

Add Executor parameter to `f` and switch to thenComposeAsync to be able to parallelize it.

Also means that concurrent readers/writers won't block eachother (computeIfAbsent would do that for instance)

 

á la:

 

  package livedemo;

 

  import java.util.concurrent.*;

  import java.math.BigInteger;

  import java.util.Map;

 

  public class FibonacciCached {

    private final Map<Integer, CompletionStage<BigInteger>> cache;

 

    public FibonacciCached(Map<Integer, CompletionStage<BigInteger>> cache) {

      this.cache = cache;

      cache.put(0, CompletableFuture.completedFuture(BigInteger.ZERO));

      cache.put(1, CompletableFuture.completedFuture(BigInteger.ONE));

    }

 

    public CompletionStage<BigInteger> f(int n, Executor e) {

      CompletableFuture<BigInteger> next = new CompletableFuture<>();

      CompletionStage<BigInteger> prev = cache.putIfAbsent(n, next);

      if (prev != null) return prev;

      else

        return f(n-1, e).thenComposeAsync(v -> f(n-2, e).thenComposeAsync(v2 -> { next.complete(v.add(v2)); return next; }, e), e);

    }

  }

 

 

--

Cheers,

 

 
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
  

 

Software AG – Sitz/Registered office: Uhlandstraße 12, 64297 Darmstadt, Germany – Registergericht/Commercial register: Darmstadt HRB 1562 - Vorstand/Management Board: Karl-Heinz Streibich (Vorsitzender/Chairman), Eric Duffaut, Dr. Wolfram Jost, Arnd Zinnhardt; - Aufsichtsratsvorsitzender/Chairman of the Supervisory Board: Dr. Andreas Bereczky - http://www.softwareag.com



 

--

Cheers,


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

 


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

Viktor Klang
Thanks Sebastian,

(There's a thenComposeAsync missing in the async version.)

Could you augment the JMH test to attempt to use the same Fib from multiple threads to show how it behaves under contention? (this is where the simple-version breaks down as it isn't threadsafe)

I believe you'll also have to use larger values for fib to make sure that BigInteger.add gets a bit of exercise too :)


On Wed, Apr 27, 2016 at 9:20 AM, Millies, Sebastian <[hidden email]> wrote:

Hello Viktor,

 

as I don’t know if attachments are alright in this group, I have put the code and benchmark in a gist:

https://gist.github.com/smillies/0cceb17501f74c4f53bf4930eba61889

 

n  Sebastian

 

From: Viktor Klang [mailto:[hidden email]]
Sent: Tuesday, April 26, 2016 5:34 PM
To: Millies, Sebastian
Cc: concurrency-interest; Henri Tremblay
Subject: RE: [concurrency-interest] ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

 

Hi Sebastian!

(IMO) Async is neverr for performance, it is for scalability. (And resilience; Parallelization is for performance)

What does the scaling profile look for 1..N concurrent accesses?

And did you try using thenCompose iso. thenComposeAsync for the initial step?

Also, which executor did you use and using what config?

A lot of questions, I know!
--
Cheers,

On Apr 26, 2016 5:09 PM, "Millies, Sebastian" <[hidden email]> wrote:

Yes, thank you very much,  very instructive. I wonder how expensive the asynchronous computation step must be to make it worthwhile speed-wise. When computing the 2000th Fibonacci number on my quadcore, at least, the asynchronous “optimized” CF version performs 10 – 20 times worse compared to single-threaded code using a memoizer  with a simple HashMap, such as the one posted by Andrew Haley in this thread.

n  Sebastian

 

From: Henri Tremblay [mailto:[hidden email]]
Sent: Monday, April 25, 2016 7:02 PM
To: Viktor Klang
Cc: Millies, Sebastian; concurrency-interest
Subject: Re: [concurrency-interest] ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

 

Hi Viktor,

 

Thanks a lot for those examples. They are crystal clear demonstration of a nice CompletableFuture usage.

 

Really nice

Henri

 

On 23 April 2016 at 15:45, Viktor Klang <[hidden email]> wrote:

Hi Sebastian,

 

I only provided the code as an alternate solution to using computeIfAbsent, for a more «optimized»[1] version, see the snippet below.


If / when CHM becomes completely non-blocking, this would mean that readers would never block other readers nor other writers, and writers would never block readers or other writers.

package livedemo;

 

  import java.util.concurrent.*;

  import java.math.BigInteger;

  import java.util.Map;

 

  public class FibonacciCached {

    private final Map<Integer, CompletionStage<BigInteger>> cache;

 

    public FibonacciCached(Map<Integer, CompletionStage<BigInteger>> cache) {

      this.cache = cache;

      cache.put(0, CompletableFuture.completedFuture(BigInteger.ZERO));

      cache.put(1, CompletableFuture.completedFuture(BigInteger.ONE));

    }

 

    public CompletionStage<BigInteger> f(int n, Executor e) {

      CompletionStage<BigInteger> ret = cache.get(n);

      if (ret == null) {

        final CompletableFuture<BigInteger> compute = new CompletableFuture<>();

        ret = cache.putIfAbsent(n, compute);

        if (ret == null)

          ret = f(n-1, e).thenComposeAsync(v -> f(n-2, e).thenComposeAsync(v2 -> { compute.complete(v.add(v2)); return compute; }, e), e);

      }

      return ret;

    }

  }

1: It's very much possible and recommended to not make the first thenCompose an async one, as only the addition of v and v2 might be "expensive" (for large additions).

 

On Sat, Apr 23, 2016 at 12:50 PM, Millies, Sebastian <[hidden email]> wrote:

I’m not sure I’m getting it. What’s significant about putting that empty CF in as a placeholder first? That is, what is the advantage over writing

 

public CompletionStage<BigInteger> f(int n) { 

  CompletionStage<BigInteger> prev = cache.get(n);

  if (prev != null) {

    return prev;

  }

  else {

    return f(n - 1).thenCompose(x ->

           f(n - 2).thenCompose(y -> {

           CompletableFuture<BigInteger> next = CompletableFuture.completedFuture(x.add(y));

           CompletionStage<BigInteger> v = cache.putIfAbsent(n, next);

           return prev != null ? v : next;

    }));

  }

}

 

Is it that in Viktor’s code, only the thread that first has a cache miss calls the computation that will complete the future, while in the above code there may be multiple computations, only one of which will eventually contribute to the result? And would that consideration only apply to the async version?

 

n  Sebastian

 

From: [hidden email] [mailto:[hidden email]] On Behalf Of Dr Heinz M. Kabutz
Sent: Saturday, April 23, 2016 7:31 AM
To: Viktor Klang
Cc: concurrency-interest
Subject: Re: [concurrency-interest] ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

 

Thanks so much Viktor for that code!  The part that I somehow missed was the empty CompletableFuture: CompletableFuture<BigInteger> next = new CompletableFuture<>();

Very interesting indeed.

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



Viktor Klang wrote:

Heinz,

There's also the option of going this route:

 

  package livedemo;

 

  import java.util.concurrent.*;

  import java.math.BigInteger;

  import java.util.Map;

 

  public class FibonacciCached {

    private final Map<Integer, CompletionStage<BigInteger>> cache;

 

    public FibonacciCached(Map<Integer, CompletionStage<BigInteger>> cache) {

      this.cache = cache;

      cache.put(0, CompletableFuture.completedFuture(BigInteger.ZERO));

      cache.put(1, CompletableFuture.completedFuture(BigInteger.ONE));

    }

 

    public CompletionStage<BigInteger> f(int n) {

      CompletableFuture<BigInteger> next = new CompletableFuture<>();

      CompletionStage<BigInteger> prev = cache.putIfAbsent(n, next);

      if (prev != null) return prev;

      else

        return f(n-1).thenCompose(v -> f(n-2).thenCompose(v2 -> { next.complete(v.add(v2)); return next; }));

    }

  }

 

 

Add Executor parameter to `f` and switch to thenComposeAsync to be able to parallelize it.

Also means that concurrent readers/writers won't block eachother (computeIfAbsent would do that for instance)

 

á la:

 

  package livedemo;

 

  import java.util.concurrent.*;

  import java.math.BigInteger;

  import java.util.Map;

 

  public class FibonacciCached {

    private final Map<Integer, CompletionStage<BigInteger>> cache;

 

    public FibonacciCached(Map<Integer, CompletionStage<BigInteger>> cache) {

      this.cache = cache;

      cache.put(0, CompletableFuture.completedFuture(BigInteger.ZERO));

      cache.put(1, CompletableFuture.completedFuture(BigInteger.ONE));

    }

 

    public CompletionStage<BigInteger> f(int n, Executor e) {

      CompletableFuture<BigInteger> next = new CompletableFuture<>();

      CompletionStage<BigInteger> prev = cache.putIfAbsent(n, next);

      if (prev != null) return prev;

      else

        return f(n-1, e).thenComposeAsync(v -> f(n-2, e).thenComposeAsync(v2 -> { next.complete(v.add(v2)); return next; }, e), e);

    }

  }

 

 

--

Cheers,

 

 
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
  

 

Software AG – Sitz/Registered office: Uhlandstraße 12, 64297 Darmstadt, Germany – Registergericht/Commercial register: Darmstadt HRB 1562 - Vorstand/Management Board: Karl-Heinz Streibich (Vorsitzender/Chairman), Eric Duffaut, Dr. Wolfram Jost, Arnd Zinnhardt; - Aufsichtsratsvorsitzender/Chairman of the Supervisory Board: Dr. Andreas Bereczky - http://www.softwareag.com



 

--

Cheers,


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

 




--
Cheers,

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

Millies, Sebastian

I have added https://gist.github.com/smillies/0cceb17501f74c4f53bf4930eba61889#file-fibcachedconcurrentbenchmark-java

to compute concurrent benchmarks of the 6000th Fibonacci number. Only the CF versions of course.

 

The same Fib is used by two threads in each case, the pool for the async version gets another two.

 

The bad news is they’re prone to  deadlock. Now I am no expert in JMH, perhaps it’s just the way I’ve set up the tests .(I hope so.)

 

n  Sebastian

 

From: Viktor Klang [mailto:[hidden email]]
Sent: Wednesday, April 27, 2016 10:22 AM
To: Mill
ies, Sebastian
Cc: concurrency-interest; Henri Tremblay
Subject: Re: [concurrency-interest] ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

 

Thanks Sebastian,

 

(There's a thenComposeAsync missing in the async version.)

 

Could you augment the JMH test to attempt to use the same Fib from multiple threads to show how it behaves under contention? (this is where the simple-version breaks down as it isn't threadsafe)

 

I believe you'll also have to use larger values for fib to make sure that BigInteger.add gets a bit of exercise too :)

 

 

On Wed, Apr 27, 2016 at 9:20 AM, Millies, Sebastian <[hidden email]> wrote:

Hello Viktor,

 

as I don’t know if attachments are alright in this group, I have put the code and benchmark in a gist:

https://gist.github.com/smillies/0cceb17501f74c4f53bf4930eba61889

 

n  Sebastian

 

From: Viktor Klang [mailto:[hidden email]]
Sent: Tuesday, April 26, 2016 5:34 PM
To: Millies, Sebastian
Cc: concurrency-interest; Henri Tremblay
Subject: RE: [concurrency-interest] ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

 

Hi Sebastian!

(IMO) Async is neverr for performance, it is for scalability. (And resilience; Parallelization is for performance)

What does the scaling profile look for 1..N concurrent accesses?

And did you try using thenCompose iso. thenComposeAsync for the initial step?

Also, which executor did you use and using what config?

A lot of questions, I know!
--
Cheers,

On Apr 26, 2016 5:09 PM, "Millies, Sebastian" <[hidden email]> wrote:

Yes, thank you very much,  very instructive. I wonder how expensive the asynchronous computation step must be to make it worthwhile speed-wise. When computing the 2000th Fibonacci number on my quadcore, at least, the asynchronous “optimized” CF version performs 10 – 20 times worse compared to single-threaded code using a memoizer  with a simple HashMap, such as the one posted by Andrew Haley in this thread.

n  Sebastian

 

From: Henri Tremblay [mailto:[hidden email]]
Sent: Monday, April 25, 2016 7:02 PM
To: Viktor Klang
Cc: Millies, Sebastian; concurrency-interest
Subject: Re: [concurrency-interest] ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

 

Hi Viktor,

 

Thanks a lot for those examples. They are crystal clear demonstration of a nice CompletableFuture usage.

 

Really nice

Henri

 

On 23 April 2016 at 15:45, Viktor Klang <[hidden email]> wrote:

Hi Sebastian,

 

I only provided the code as an alternate solution to using computeIfAbsent, for a more «optimized»[1] version, see the snippet below.


If / when CHM becomes completely non-blocking, this would mean that readers would never block other readers nor other writers, and writers would never block readers or other writers.

package livedemo;

 

  import java.util.concurrent.*;

  import java.math.BigInteger;

  import java.util.Map;

 

  public class FibonacciCached {

    private final Map<Integer, CompletionStage<BigInteger>> cache;

 

    public FibonacciCached(Map<Integer, CompletionStage<BigInteger>> cache) {

      this.cache = cache;

      cache.put(0, CompletableFuture.completedFuture(BigInteger.ZERO));

      cache.put(1, CompletableFuture.completedFuture(BigInteger.ONE));

    }

 

    public CompletionStage<BigInteger> f(int n, Executor e) {

      CompletionStage<BigInteger> ret = cache.get(n);

      if (ret == null) {

        final CompletableFuture<BigInteger> compute = new CompletableFuture<>();

        ret = cache.putIfAbsent(n, compute);

        if (ret == null)

          ret = f(n-1, e).thenComposeAsync(v -> f(n-2, e).thenComposeAsync(v2 -> { compute.complete(v.add(v2)); return compute; }, e), e);

      }

      return ret;

    }

  }

1: It's very much possible and recommended to not make the first thenCompose an async one, as only the addition of v and v2 might be "expensive" (for large additions).

 

On Sat, Apr 23, 2016 at 12:50 PM, Millies, Sebastian <[hidden email]> wrote:

I’m not sure I’m getting it. What’s significant about putting that empty CF in as a placeholder first? That is, what is the advantage over writing

 

public CompletionStage<BigInteger> f(int n) { 

  CompletionStage<BigInteger> prev = cache.get(n);

  if (prev != null) {

    return prev;

  }

  else {

    return f(n - 1).thenCompose(x ->

           f(n - 2).thenCompose(y -> {

           CompletableFuture<BigInteger> next = CompletableFuture.completedFuture(x.add(y));

           CompletionStage<BigInteger> v = cache.putIfAbsent(n, next);

           return prev != null ? v : next;

    }));

  }

}

 

Is it that in Viktor’s code, only the thread that first has a cache miss calls the computation that will complete the future, while in the above code there may be multiple computations, only one of which will eventually contribute to the result? And would that consideration only apply to the async version?

 

n  Sebastian

 

From: [hidden email] [mailto:[hidden email]] On Behalf Of Dr Heinz M. Kabutz
Sent: Saturday, April 23, 2016 7:31 AM
To: Viktor Klang
Cc: concurrency-interest
Subject: Re: [concurrency-interest] ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

 

Thanks so much Viktor for that code!  The part that I somehow missed was the empty CompletableFuture: CompletableFuture<BigInteger> next = new CompletableFuture<>();

Very interesting indeed.

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



Viktor Klang wrote:

Heinz,

There's also the option of going this route:

 

  package livedemo;

 

  import java.util.concurrent.*;

  import java.math.BigInteger;

  import java.util.Map;

 

  public class FibonacciCached {

    private final Map<Integer, CompletionStage<BigInteger>> cache;

 

    public FibonacciCached(Map<Integer, CompletionStage<BigInteger>> cache) {

      this.cache = cache;

      cache.put(0, CompletableFuture.completedFuture(BigInteger.ZERO));

      cache.put(1, CompletableFuture.completedFuture(BigInteger.ONE));

    }

 

    public CompletionStage<BigInteger> f(int n) {

      CompletableFuture<BigInteger> next = new CompletableFuture<>();

      CompletionStage<BigInteger> prev = cache.putIfAbsent(n, next);

      if (prev != null) return prev;

      else

        return f(n-1).thenCompose(v -> f(n-2).thenCompose(v2 -> { next.complete(v.add(v2)); return next; }));

    }

  }

 

 

Add Executor parameter to `f` and switch to thenComposeAsync to be able to parallelize it.

Also means that concurrent readers/writers won't block eachother (computeIfAbsent would do that for instance)

 

á la:

 

  package livedemo;

 

  import java.util.concurrent.*;

  import java.math.BigInteger;

  import java.util.Map;

 

  public class FibonacciCached {

    private final Map<Integer, CompletionStage<BigInteger>> cache;

 

    public FibonacciCached(Map<Integer, CompletionStage<BigInteger>> cache) {

      this.cache = cache;

      cache.put(0, CompletableFuture.completedFuture(BigInteger.ZERO));

      cache.put(1, CompletableFuture.completedFuture(BigInteger.ONE));

    }

 

    public CompletionStage<BigInteger> f(int n, Executor e) {

      CompletableFuture<BigInteger> next = new CompletableFuture<>();

      CompletionStage<BigInteger> prev = cache.putIfAbsent(n, next);

      if (prev != null) return prev;

      else

        return f(n-1, e).thenComposeAsync(v -> f(n-2, e).thenComposeAsync(v2 -> { next.complete(v.add(v2)); return next; }, e), e);

    }

  }

 

 

--

Cheers,

 

 
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
  

 

Software AG – Sitz/Registered office: Uhlandstraße 12, 64297 Darmstadt, Germany – Registergericht/Commercial register: Darmstadt HRB 1562 - Vorstand/Management Board: Karl-Heinz Streibich (Vorsitzender/Chairman), Eric Duffaut, Dr. Wolfram Jost, Arnd Zinnhardt; - Aufsichtsratsvorsitzender/Chairman of the Supervisory Board: Dr. Andreas Bereczky - http://www.softwareag.com



 

--

Cheers,


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

 



 

--

Cheers,


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

Viktor Klang
Do you have a thread dump? (sorry, I don't have any spare cycles to have a stab at running it right now)

On Wed, Apr 27, 2016 at 3:09 PM, Millies, Sebastian <[hidden email]> wrote:

I have added https://gist.github.com/smillies/0cceb17501f74c4f53bf4930eba61889#file-fibcachedconcurrentbenchmark-java

to compute concurrent benchmarks of the 6000th Fibonacci number. Only the CF versions of course.

 

The same Fib is used by two threads in each case, the pool for the async version gets another two.

 

The bad news is they’re prone to  deadlock. Now I am no expert in JMH, perhaps it’s just the way I’ve set up the tests .(I hope so.)

 

n  Sebastian

 

From: Viktor Klang [mailto:[hidden email]]
Sent: Wednesday, April 27, 2016 10:22 AM
To: Mill
ies, Sebastian
Cc: concurrency-interest; Henri Tremblay


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

 

Thanks Sebastian,

 

(There's a thenComposeAsync missing in the async version.)

 

Could you augment the JMH test to attempt to use the same Fib from multiple threads to show how it behaves under contention? (this is where the simple-version breaks down as it isn't threadsafe)

 

I believe you'll also have to use larger values for fib to make sure that BigInteger.add gets a bit of exercise too :)

 

 

On Wed, Apr 27, 2016 at 9:20 AM, Millies, Sebastian <[hidden email]> wrote:

Hello Viktor,

 

as I don’t know if attachments are alright in this group, I have put the code and benchmark in a gist:

https://gist.github.com/smillies/0cceb17501f74c4f53bf4930eba61889

 

n  Sebastian

 

From: Viktor Klang [mailto:[hidden email]]
Sent: Tuesday, April 26, 2016 5:34 PM
To: Millies, Sebastian
Cc: concurrency-interest; Henri Tremblay
Subject: RE: [concurrency-interest] ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

 

Hi Sebastian!

(IMO) Async is neverr for performance, it is for scalability. (And resilience; Parallelization is for performance)

What does the scaling profile look for 1..N concurrent accesses?

And did you try using thenCompose iso. thenComposeAsync for the initial step?

Also, which executor did you use and using what config?

A lot of questions, I know!
--
Cheers,

On Apr 26, 2016 5:09 PM, "Millies, Sebastian" <[hidden email]> wrote:

Yes, thank you very much,  very instructive. I wonder how expensive the asynchronous computation step must be to make it worthwhile speed-wise. When computing the 2000th Fibonacci number on my quadcore, at least, the asynchronous “optimized” CF version performs 10 – 20 times worse compared to single-threaded code using a memoizer  with a simple HashMap, such as the one posted by Andrew Haley in this thread.

n  Sebastian

 

From: Henri Tremblay [mailto:[hidden email]]
Sent: Monday, April 25, 2016 7:02 PM
To: Viktor Klang
Cc: Millies, Sebastian; concurrency-interest
Subject: Re: [concurrency-interest] ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

 

Hi Viktor,

 

Thanks a lot for those examples. They are crystal clear demonstration of a nice CompletableFuture usage.

 

Really nice

Henri

 

On 23 April 2016 at 15:45, Viktor Klang <[hidden email]> wrote:

Hi Sebastian,

 

I only provided the code as an alternate solution to using computeIfAbsent, for a more «optimized»[1] version, see the snippet below.


If / when CHM becomes completely non-blocking, this would mean that readers would never block other readers nor other writers, and writers would never block readers or other writers.

package livedemo;

 

  import java.util.concurrent.*;

  import java.math.BigInteger;

  import java.util.Map;

 

  public class FibonacciCached {

    private final Map<Integer, CompletionStage<BigInteger>> cache;

 

    public FibonacciCached(Map<Integer, CompletionStage<BigInteger>> cache) {

      this.cache = cache;

      cache.put(0, CompletableFuture.completedFuture(BigInteger.ZERO));

      cache.put(1, CompletableFuture.completedFuture(BigInteger.ONE));

    }

 

    public CompletionStage<BigInteger> f(int n, Executor e) {

      CompletionStage<BigInteger> ret = cache.get(n);

      if (ret == null) {

        final CompletableFuture<BigInteger> compute = new CompletableFuture<>();

        ret = cache.putIfAbsent(n, compute);

        if (ret == null)

          ret = f(n-1, e).thenComposeAsync(v -> f(n-2, e).thenComposeAsync(v2 -> { compute.complete(v.add(v2)); return compute; }, e), e);

      }

      return ret;

    }

  }

1: It's very much possible and recommended to not make the first thenCompose an async one, as only the addition of v and v2 might be "expensive" (for large additions).

 

On Sat, Apr 23, 2016 at 12:50 PM, Millies, Sebastian <[hidden email]> wrote:

I’m not sure I’m getting it. What’s significant about putting that empty CF in as a placeholder first? That is, what is the advantage over writing

 

public CompletionStage<BigInteger> f(int n) { 

  CompletionStage<BigInteger> prev = cache.get(n);

  if (prev != null) {

    return prev;

  }

  else {

    return f(n - 1).thenCompose(x ->

           f(n - 2).thenCompose(y -> {

           CompletableFuture<BigInteger> next = CompletableFuture.completedFuture(x.add(y));

           CompletionStage<BigInteger> v = cache.putIfAbsent(n, next);

           return prev != null ? v : next;

    }));

  }

}

 

Is it that in Viktor’s code, only the thread that first has a cache miss calls the computation that will complete the future, while in the above code there may be multiple computations, only one of which will eventually contribute to the result? And would that consideration only apply to the async version?

 

n  Sebastian

 

From: [hidden email] [mailto:[hidden email]] On Behalf Of Dr Heinz M. Kabutz
Sent: Saturday, April 23, 2016 7:31 AM
To: Viktor Klang
Cc: concurrency-interest
Subject: Re: [concurrency-interest] ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

 

Thanks so much Viktor for that code!  The part that I somehow missed was the empty CompletableFuture: CompletableFuture<BigInteger> next = new CompletableFuture<>();

Very interesting indeed.

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



Viktor Klang wrote:

Heinz,

There's also the option of going this route:

 

  package livedemo;

 

  import java.util.concurrent.*;

  import java.math.BigInteger;

  import java.util.Map;

 

  public class FibonacciCached {

    private final Map<Integer, CompletionStage<BigInteger>> cache;

 

    public FibonacciCached(Map<Integer, CompletionStage<BigInteger>> cache) {

      this.cache = cache;

      cache.put(0, CompletableFuture.completedFuture(BigInteger.ZERO));

      cache.put(1, CompletableFuture.completedFuture(BigInteger.ONE));

    }

 

    public CompletionStage<BigInteger> f(int n) {

      CompletableFuture<BigInteger> next = new CompletableFuture<>();

      CompletionStage<BigInteger> prev = cache.putIfAbsent(n, next);

      if (prev != null) return prev;

      else

        return f(n-1).thenCompose(v -> f(n-2).thenCompose(v2 -> { next.complete(v.add(v2)); return next; }));

    }

  }

 

 

Add Executor parameter to `f` and switch to thenComposeAsync to be able to parallelize it.

Also means that concurrent readers/writers won't block eachother (computeIfAbsent would do that for instance)

 

á la:

 

  package livedemo;

 

  import java.util.concurrent.*;

  import java.math.BigInteger;

  import java.util.Map;

 

  public class FibonacciCached {

    private final Map<Integer, CompletionStage<BigInteger>> cache;

 

    public FibonacciCached(Map<Integer, CompletionStage<BigInteger>> cache) {

      this.cache = cache;

      cache.put(0, CompletableFuture.completedFuture(BigInteger.ZERO));

      cache.put(1, CompletableFuture.completedFuture(BigInteger.ONE));

    }

 

    public CompletionStage<BigInteger> f(int n, Executor e) {

      CompletableFuture<BigInteger> next = new CompletableFuture<>();

      CompletionStage<BigInteger> prev = cache.putIfAbsent(n, next);

      if (prev != null) return prev;

      else

        return f(n-1, e).thenComposeAsync(v -> f(n-2, e).thenComposeAsync(v2 -> { next.complete(v.add(v2)); return next; }, e), e);

    }

  }

 

 

--

Cheers,

 

 
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
  

 

Software AG – Sitz/Registered office: Uhlandstraße 12, 64297 Darmstadt, Germany – Registergericht/Commercial register: Darmstadt HRB 1562 - Vorstand/Management Board: Karl-Heinz Streibich (Vorsitzender/Chairman), Eric Duffaut, Dr. Wolfram Jost, Arnd Zinnhardt; - Aufsichtsratsvorsitzender/Chairman of the Supervisory Board: Dr. Andreas Bereczky - http://www.softwareag.com



 

--

Cheers,


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

 



 

--

Cheers,




--
Cheers,

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

Millies, Sebastian

There is a thread dump on DropBox: https://www.dropbox.com/s/zy87bt4e7dzd099/threaddump-1461767854829.tdump?dl=0

 

Here’s some console output:

 

# JMH 1.12 (released 26 days ago)

# VM version: JDK 1.8.0_92, VM 25.92-b14

# VM invoker: C:\Program Files\Java\jdk1.8.0_92\jre\bin\java.exe

# VM options: -Dfile.encoding=UTF-8

# Warmup: 10 iterations, 1000 ms each

# Measurement: 20 iterations, 1000 ms each

# Timeout: 10 min per iteration

# Threads: 2 threads

# Benchmark mode: Single shot invocation time

# Benchmark: java8.concurrent.FibCachedConcurrentBenchmark.cfAsync6000

 

# Run progress: 0.00% complete, ETA 00:00:00

# Fork: 1 of 1

# Warmup Iteration   1: POOL_SIZE = 2

 

n  Sebastian

 

(PS: changed measurement mode to single shot, because only the first method call in each iteration would do any work, the rest would just be map lookups.)

 

From: Viktor Klang [[hidden email]]
Sent: Wednesday, April 27, 2016 3:21 PM
To: Millies, Sebastian
Cc: concurrency-interest
Subject: Re: [concurrency-interest] ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

 

Do you have a thread dump? (sorry, I don't have any spare cycles to have a stab at running it right now)

 

On Wed, Apr 27, 2016 at 3:09 PM, Millies, Sebastian <[hidden email]> wrote:

I have added https://gist.github.com/smillies/0cceb17501f74c4f53bf4930eba61889#file-fibcachedconcurrentbenchmark-java

to compute concurrent benchmarks of the 6000th Fibonacci number. Only the CF versions of course.

 

The same Fib is used by two threads in each case, the pool for the async version gets another two.

 

The bad news is they’re prone to  deadlock. Now I am no expert in JMH, perhaps it’s just the way I’ve set up the tests .(I hope so.)

 

n  Sebastian

 

From: Viktor Klang [mailto:[hidden email]]
Sent: Wednesday, April 27, 2016 10:22 AM
To: Mill
ies, Sebastian
Cc: concurrency-interest; Henri Tremblay


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

 

Thanks Sebastian,

 

(There's a thenComposeAsync missing in the async version.)

 

Could you augment the JMH test to attempt to use the same Fib from multiple threads to show how it behaves under contention? (this is where the simple-version breaks down as it isn't threadsafe)

 

I believe you'll also have to use larger values for fib to make sure that BigInteger.add gets a bit of exercise too :)

 

 

On Wed, Apr 27, 2016 at 9:20 AM, Millies, Sebastian <[hidden email]> wrote:

Hello Viktor,

 

as I don’t know if attachments are alright in this group, I have put the code and benchmark in a gist:

https://gist.github.com/smillies/0cceb17501f74c4f53bf4930eba61889

 

n  Sebastian

 

From: Viktor Klang [mailto:[hidden email]]
Sent: Tuesday, April 26, 2016 5:34 PM
To: Millies, Sebastian
Cc: concurrency-interest; Henri Tremblay
Subject: RE: [concurrency-interest] ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

 

Hi Sebastian!

(IMO) Async is neverr for performance, it is for scalability. (And resilience; Parallelization is for performance)

What does the scaling profile look for 1..N concurrent accesses?

And did you try using thenCompose iso. thenComposeAsync for the initial step?

Also, which executor did you use and using what config?

A lot of questions, I know!
--
Cheers,

On Apr 26, 2016 5:09 PM, "Millies, Sebastian" <[hidden email]> wrote:

Yes, thank you very much,  very instructive. I wonder how expensive the asynchronous computation step must be to make it worthwhile speed-wise. When computing the 2000th Fibonacci number on my quadcore, at least, the asynchronous “optimized” CF version performs 10 – 20 times worse compared to single-threaded code using a memoizer  with a simple HashMap, such as the one posted by Andrew Haley in this thread.

n  Sebastian

 

From: Henri Tremblay [mailto:[hidden email]]
Sent: Monday, April 25, 2016 7:02 PM
To: Viktor Klang
Cc: Millies, Sebastian; concurrency-interest
Subject: Re: [concurrency-interest] ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

 

Hi Viktor,

 

Thanks a lot for those examples. They are crystal clear demonstration of a nice CompletableFuture usage.

 

Really nice

Henri

 

On 23 April 2016 at 15:45, Viktor Klang <[hidden email]> wrote:

Hi Sebastian,

 

I only provided the code as an alternate solution to using computeIfAbsent, for a more «optimized»[1] version, see the snippet below.


If / when CHM becomes completely non-blocking, this would mean that readers would never block other readers nor other writers, and writers would never block readers or other writers.

package livedemo;

 

  import java.util.concurrent.*;

  import java.math.BigInteger;

  import java.util.Map;

 

  public class FibonacciCached {

    private final Map<Integer, CompletionStage<BigInteger>> cache;

 

    public FibonacciCached(Map<Integer, CompletionStage<BigInteger>> cache) {

      this.cache = cache;

      cache.put(0, CompletableFuture.completedFuture(BigInteger.ZERO));

      cache.put(1, CompletableFuture.completedFuture(BigInteger.ONE));

    }

 

    public CompletionStage<BigInteger> f(int n, Executor e) {

      CompletionStage<BigInteger> ret = cache.get(n);

      if (ret == null) {

        final CompletableFuture<BigInteger> compute = new CompletableFuture<>();

        ret = cache.putIfAbsent(n, compute);

        if (ret == null)

          ret = f(n-1, e).thenComposeAsync(v -> f(n-2, e).thenComposeAsync(v2 -> { compute.complete(v.add(v2)); return compute; }, e), e);

      }

      return ret;

    }

  }

1: It's very much possible and recommended to not make the first thenCompose an async one, as only the addition of v and v2 might be "expensive" (for large additions).

 

On Sat, Apr 23, 2016 at 12:50 PM, Millies, Sebastian <[hidden email]> wrote:

I’m not sure I’m getting it. What’s significant about putting that empty CF in as a placeholder first? That is, what is the advantage over writing

 

public CompletionStage<BigInteger> f(int n) { 

  CompletionStage<BigInteger> prev = cache.get(n);

  if (prev != null) {

    return prev;

  }

  else {

    return f(n - 1).thenCompose(x ->

           f(n - 2).thenCompose(y -> {

           CompletableFuture<BigInteger> next = CompletableFuture.completedFuture(x.add(y));

           CompletionStage<BigInteger> v = cache.putIfAbsent(n, next);

           return prev != null ? v : next;

    }));

  }

}

 

Is it that in Viktor’s code, only the thread that first has a cache miss calls the computation that will complete the future, while in the above code there may be multiple computations, only one of which will eventually contribute to the result? And would that consideration only apply to the async version?

 

n  Sebastian

 

From: [hidden email] [mailto:[hidden email]] On Behalf Of Dr Heinz M. Kabutz
Sent: Saturday, April 23, 2016 7:31 AM
To: Viktor Klang
Cc: concurrency-interest
Subject: Re: [concurrency-interest] ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

 

Thanks so much Viktor for that code!  The part that I somehow missed was the empty CompletableFuture: CompletableFuture<BigInteger> next = new CompletableFuture<>();

Very interesting indeed.

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



Viktor Klang wrote:

Heinz,

There's also the option of going this route:

 

  package livedemo;

 

  import java.util.concurrent.*;

  import java.math.BigInteger;

  import java.util.Map;

 

  public class FibonacciCached {

    private final Map<Integer, CompletionStage<BigInteger>> cache;

 

    public FibonacciCached(Map<Integer, CompletionStage<BigInteger>> cache) {

      this.cache = cache;

      cache.put(0, CompletableFuture.completedFuture(BigInteger.ZERO));

      cache.put(1, CompletableFuture.completedFuture(BigInteger.ONE));

    }

 

    public CompletionStage<BigInteger> f(int n) {

      CompletableFuture<BigInteger> next = new CompletableFuture<>();

      CompletionStage<BigInteger> prev = cache.putIfAbsent(n, next);

      if (prev != null) return prev;

      else

        return f(n-1).thenCompose(v -> f(n-2).thenCompose(v2 -> { next.complete(v.add(v2)); return next; }));

    }

  }

 

 

Add Executor parameter to `f` and switch to thenComposeAsync to be able to parallelize it.

Also means that concurrent readers/writers won't block eachother (computeIfAbsent would do that for instance)

 

á la:

 

  package livedemo;

 

  import java.util.concurrent.*;

  import java.math.BigInteger;

  import java.util.Map;

 

  public class FibonacciCached {

    private final Map<Integer, CompletionStage<BigInteger>> cache;

 

    public FibonacciCached(Map<Integer, CompletionStage<BigInteger>> cache) {

      this.cache = cache;

      cache.put(0, CompletableFuture.completedFuture(BigInteger.ZERO));

      cache.put(1, CompletableFuture.completedFuture(BigInteger.ONE));

    }

 

    public CompletionStage<BigInteger> f(int n, Executor e) {

      CompletableFuture<BigInteger> next = new CompletableFuture<>();

      CompletionStage<BigInteger> prev = cache.putIfAbsent(n, next);

      if (prev != null) return prev;

      else

        return f(n-1, e).thenComposeAsync(v -> f(n-2, e).thenComposeAsync(v2 -> { next.complete(v.add(v2)); return next; }, e), e);

    }

  }

 

 

--

Cheers,

 

 
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
  

 

Software AG – Sitz/Registered office: Uhlandstraße 12, 64297 Darmstadt, Germany – Registergericht/Commercial register: Darmstadt HRB 1562 - Vorstand/Management Board: Karl-Heinz Streibich (Vorsitzender/Chairman), Eric Duffaut, Dr. Wolfram Jost, Arnd Zinnhardt; - Aufsichtsratsvorsitzender/Chairman of the Supervisory Board: Dr. Andreas Bereczky - http://www.softwareag.com



 

--

Cheers,


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

 



 

--

Cheers,



 

--

Cheers,


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

Millies, Sebastian
In reply to this post by Viktor Klang

Dropbox may not have been a good idea L Here’s a thread-dump from deadlock in the cf6000Async benchmark:

 

2016-04-28 10:29:36

Full thread dump Java HotSpot(TM) 64-Bit Server VM (25.92-b14 mixed mode):

 

"java8.concurrent.FibCachedConcurrentBenchmark.cfAsync6000-jmh-worker-2" #14 daemon prio=5 os_prio=0 tid=0x000000001fc95800 nid=0x2418 waiting on condition [0x000000001f62e000]

   java.lang.Thread.State: WAITING (parking)

                at sun.misc.Unsafe.park(Native Method)

                - parking to wait for  <0x000000076bc429b8> (a java.util.concurrent.CompletableFuture$Signaller)

                at java.util.concurrent.locks.LockSupport.park(LockSupport.java:175)

                at java.util.concurrent.CompletableFuture$Signaller.block(CompletableFuture.java:1693)

                at java.util.concurrent.ForkJoinPool.managedBlock(ForkJoinPool.java:3323)

                at java.util.concurrent.CompletableFuture.waitingGet(CompletableFuture.java:1729)

                at java.util.concurrent.CompletableFuture.join(CompletableFuture.java:1934)

                at java8.concurrent.FibCachedConcurrentBenchmark.cfAsync6000(FibCachedConcurrentBenchmark.java:76)

                at java8.concurrent.generated.FibCachedConcurrentBenchmark_cfAsync6000_jmhTest.cfAsync6000_ss_jmhStub(FibCachedConcurrentBenchmark_cfAsync6000_jmhTest.java:490)

                at java8.concurrent.generated.FibCachedConcurrentBenchmark_cfAsync6000_jmhTest.cfAsync6000_SingleShotTime(FibCachedConcurrentBenchmark_cfAsync6000_jmhTest.java:433)

                at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)

                at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)

                at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)

                at java.lang.reflect.Method.invoke(Method.java:498)

                at org.openjdk.jmh.runner.BenchmarkHandler$BenchmarkTask.call(BenchmarkHandler.java:430)

                at org.openjdk.jmh.runner.BenchmarkHandler$BenchmarkTask.call(BenchmarkHandler.java:412)

                at java.util.concurrent.FutureTask.run(FutureTask.java:266)

                at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)

                at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)

                at java.lang.Thread.run(Thread.java:745)

 

   Locked ownable synchronizers:

                - <0x000000076b9cda18> (a java.util.concurrent.ThreadPoolExecutor$Worker)

 

"java8.concurrent.FibCachedConcurrentBenchmark.cfAsync6000-jmh-worker-1" #13 daemon prio=5 os_prio=0 tid=0x000000001fc94800 nid=0x2414 waiting on condition [0x000000001f3df000]

   java.lang.Thread.State: WAITING (parking)

                at sun.misc.Unsafe.park(Native Method)

                - parking to wait for  <0x000000076b9517a0> (a java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject)

                at java.util.concurrent.locks.LockSupport.park(LockSupport.java:175)

                at java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject.await(AbstractQueuedSynchronizer.java:2039)

                at java.util.concurrent.LinkedBlockingQueue.take(LinkedBlockingQueue.java:442)

                at java.util.concurrent.ThreadPoolExecutor.getTask(ThreadPoolExecutor.java:1067)

                at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1127)

                at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)

                at java.lang.Thread.run(Thread.java:745)

 

   Locked ownable synchronizers:

                - None

 

"Service Thread" #10 daemon prio=9 os_prio=0 tid=0x000000001d97d000 nid=0x2404 runnable [0x0000000000000000]

   java.lang.Thread.State: RUNNABLE

 

   Locked ownable synchronizers:

                - None

 

"C1 CompilerThread3" #9 daemon prio=9 os_prio=2 tid=0x000000001c71f000 nid=0x1cb0 waiting on condition [0x0000000000000000]

   java.lang.Thread.State: RUNNABLE

 

   Locked ownable synchronizers:

                - None

 

"C2 CompilerThread2" #8 daemon prio=9 os_prio=2 tid=0x000000001c71e000 nid=0x19cc waiting on condition [0x0000000000000000]

   java.lang.Thread.State: RUNNABLE

 

   Locked ownable synchronizers:

                - None

 

"C2 CompilerThread1" #7 daemon prio=9 os_prio=2 tid=0x000000001c71b000 nid=0x1d78 waiting on condition [0x0000000000000000]

   java.lang.Thread.State: RUNNABLE

 

   Locked ownable synchronizers:

                - None

 

"C2 CompilerThread0" #6 daemon prio=9 os_prio=2 tid=0x000000001d8db000 nid=0xfec waiting on condition [0x0000000000000000]

   java.lang.Thread.State: RUNNABLE

 

   Locked ownable synchronizers:

                - None

 

"Attach Listener" #5 daemon prio=5 os_prio=2 tid=0x000000001d8d9800 nid=0x200c waiting on condition [0x0000000000000000]

   java.lang.Thread.State: RUNNABLE

 

   Locked ownable synchronizers:

                - None

 

"Signal Dispatcher" #4 daemon prio=9 os_prio=2 tid=0x000000001d8d8000 nid=0x620 runnable [0x0000000000000000]

   java.lang.Thread.State: RUNNABLE

 

   Locked ownable synchronizers:

                - None

 

"Finalizer" #3 daemon prio=8 os_prio=1 tid=0x000000001c711000 nid=0x10a4 in Object.wait() [0x000000001ec7f000]

   java.lang.Thread.State: WAITING (on object monitor)

                at java.lang.Object.wait(Native Method)

                - waiting on <0x000000076b208ee0> (a java.lang.ref.ReferenceQueue$Lock)

                at java.lang.ref.ReferenceQueue.remove(ReferenceQueue.java:143)

                - locked <0x000000076b208ee0> (a java.lang.ref.ReferenceQueue$Lock)

                at java.lang.ref.ReferenceQueue.remove(ReferenceQueue.java:164)

                at java.lang.ref.Finalizer$FinalizerThread.run(Finalizer.java:209)

 

   Locked ownable synchronizers:

                - None

 

"Reference Handler" #2 daemon prio=10 os_prio=2 tid=0x000000001c70a000 nid=0x1b48 in Object.wait() [0x000000001e91f000]

   java.lang.Thread.State: WAITING (on object monitor)

                at java.lang.Object.wait(Native Method)

                - waiting on <0x000000076b206b50> (a java.lang.ref.Reference$Lock)

                at java.lang.Object.wait(Object.java:502)

                at java.lang.ref.Reference.tryHandlePending(Reference.java:191)

                - locked <0x000000076b206b50> (a java.lang.ref.Reference$Lock)

                at java.lang.ref.Reference$ReferenceHandler.run(Reference.java:153)

 

   Locked ownable synchronizers:

                - None

 

"main" #1 prio=5 os_prio=0 tid=0x000000000020f800 nid=0x1e14 waiting on condition [0x0000000002b1e000]

   java.lang.Thread.State: TIMED_WAITING (parking)

                at sun.misc.Unsafe.park(Native Method)

                - parking to wait for  <0x000000076b9cd9f8> (a java.util.concurrent.FutureTask)

                at java.util.concurrent.locks.LockSupport.parkNanos(LockSupport.java:215)

                at java.util.concurrent.FutureTask.awaitDone(FutureTask.java:426)

                at java.util.concurrent.FutureTask.get(FutureTask.java:204)

                at org.openjdk.jmh.runner.BenchmarkHandler.runIteration(BenchmarkHandler.java:376)

                at org.openjdk.jmh.runner.BaseRunner.runBenchmark(BaseRunner.java:263)

                at org.openjdk.jmh.runner.BaseRunner.runBenchmark(BaseRunner.java:235)

                at org.openjdk.jmh.runner.BaseRunner.doSingle(BaseRunner.java:142)

                at org.openjdk.jmh.runner.BaseRunner.runBenchmarksForked(BaseRunner.java:76)

                at org.openjdk.jmh.runner.ForkedRunner.run(ForkedRunner.java:72)

                at org.openjdk.jmh.runner.ForkedMain.main(ForkedMain.java:84)

 

   Locked ownable synchronizers:

                - None

 

"VM Thread" os_prio=2 tid=0x000000001c701000 nid=0x2038 runnable

 

"GC task thread#0 (ParallelGC)" os_prio=0 tid=0x000000000266e800 nid=0x1ba0 runnable

 

"GC task thread#1 (ParallelGC)" os_prio=0 tid=0x0000000002670000 nid=0x4a0 runnable

 

"GC task thread#2 (ParallelGC)" os_prio=0 tid=0x0000000002671800 nid=0xfb4 runnable

 

"GC task thread#3 (ParallelGC)" os_prio=0 tid=0x0000000002673000 nid=0x1b8 runnable

 

"GC task thread#4 (ParallelGC)" os_prio=0 tid=0x0000000002676800 nid=0x1168 runnable

 

"GC task thread#5 (ParallelGC)" os_prio=0 tid=0x0000000002677800 nid=0xa84 runnable

 

"GC task thread#6 (ParallelGC)" os_prio=0 tid=0x000000000267b000 nid=0x17dc runnable

 

"GC task thread#7 (ParallelGC)" os_prio=0 tid=0x000000000267c000 nid=0x2090 runnable

 

"VM Periodic Task Thread" os_prio=2 tid=0x000000001d981800 nid=0x2408 waiting on condition

 

JNI global references: 334

 

 

From: Viktor Klang [mailto:[hidden email]]
Sent: Wednesday, April 27, 2016 3:21 PM
To: Millies, Sebastian
Cc: concurrency-interest
Subject: Re: [concurrency-interest] ConcurrentHashMapV8 Livelock on computeIfAbsent() ?

 

Do you have a thread dump? (sorry, I don't have any spare cycles to have a stab at running it right now)

 

On Wed, Apr 27, 2016 at 3:09 PM, Millies, Sebastian <[hidden email]> wrote:

I have added https://gist.github.com/smillies/0cceb17501f74c4f53bf4930eba61889#file-fibcachedconcurrentbenchmark-java

to compute concurrent benchmarks of the 6000th Fibonacci number. Only the CF versions of course.

 

The same Fib is used by two threads in each case, the pool for the async version gets another two.

 

The bad news is they’re prone to  deadlock. Now I am no expert in JMH, perhaps it’s just the way I’ve set up the tests .(I hope so.)

 

n  Sebastian

 


Software AG – Sitz/Registered office: Uhlandstraße 12, 64297 Darmstadt, Germany – Registergericht/Commercial register: Darmstadt HRB 1562 - Vorstand/Management Board: Karl-Heinz Streibich (Vorsitzender/Chairman), Eric Duffaut, Dr. Wolfram Jost, Arnd Zinnhardt; - Aufsichtsratsvorsitzender/Chairman of the Supervisory Board: Dr. Andreas Bereczky - http://www.softwareag.com


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
12