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

Millies, Sebastian Sebastian.Millies at softwareag.com
Wed Apr 27 10:45:58 EDT 2016


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 [mailto:viktor.klang at gmail.com]
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 <Sebastian.Millies at softwareag.com<mailto:Sebastian.Millies at softwareag.com>> 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.)


•  Sebastian

From: Viktor Klang [mailto:viktor.klang at gmail.com<mailto:viktor.klang at gmail.com>]
Sent: Wednesday, April 27, 2016 10:22 AM
To: Millies, 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 <Sebastian.Millies at softwareag.com<mailto:Sebastian.Millies at softwareag.com>> 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


•  Sebastian

From: Viktor Klang [mailto:viktor.klang at gmail.com<mailto:viktor.klang at gmail.com>]
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" <Sebastian.Millies at softwareag.com<mailto:Sebastian.Millies at softwareag.com>> 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.

•  Sebastian

From: Henri Tremblay [mailto:henri.tremblay at gmail.com<mailto:henri.tremblay at gmail.com>]
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 <viktor.klang at gmail.com<mailto:viktor.klang at gmail.com>> 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 <Sebastian.Millies at softwareag.com<mailto:Sebastian.Millies at softwareag.com>> 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?


•  Sebastian


From: concurrency-interest-bounces at cs.oswego.edu<mailto:concurrency-interest-bounces at cs.oswego.edu> [mailto:concurrency-interest-bounces at cs.oswego.edu<mailto:concurrency-interest-bounces at cs.oswego.edu>] 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

Concurrency-interest at cs.oswego.edu<mailto:Concurrency-interest at cs.oswego.edu>

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
Concurrency-interest at cs.oswego.edu<mailto:Concurrency-interest at cs.oswego.edu>
http://cs.oswego.edu/mailman/listinfo/concurrency-interest




--
Cheers,
√



--
Cheers,
√
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20160427/e2b9bc92/attachment-0001.html>


More information about the Concurrency-interest mailing list