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

Viktor Klang viktor.klang at gmail.com
Tue Apr 26 11:34:00 EDT 2016


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
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20160426/86f4b65d/attachment-0001.html>


More information about the Concurrency-interest mailing list