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

Dr Heinz M. Kabutz heinz at javaspecialists.eu
Tue Apr 26 11:33:22 EDT 2016


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 <
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
> <javascript:_e(%7B%7D,'cvml','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
> <javascript:_e(%7B%7D,'cvml','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
> <javascript:_e(%7B%7D,'cvml','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
> <javascript:_e(%7B%7D,'cvml','concurrency-interest-bounces at cs.oswego.edu');>
> [mailto:concurrency-interest-bounces at cs.oswego.edu
> <javascript:_e(%7B%7D,'cvml','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 <javascript:_e(%7B%7D,'cvml','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
> <javascript:_e(%7B%7D,'cvml','Concurrency-interest at cs.oswego.edu');>
> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20160426/10bfd8f4/attachment-0001.html>


More information about the Concurrency-interest mailing list