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

Viktor Klang viktor.klang at gmail.com
Wed Apr 27 09:20:32 EDT 2016


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> 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: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> 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: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> 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: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> 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> 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:* 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
>
> 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* <http://www.softwareag.com>
>
>
>
>
>
> --
>
> Cheers,
>
>>
>
> _______________________________________________
> Concurrency-interest mailing list
> 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/d41ee775/attachment-0001.html>


More information about the Concurrency-interest mailing list