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

Henri Tremblay henri.tremblay at gmail.com
Mon Apr 25 13:01:55 EDT 2016


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/20160425/4e19d91a/attachment.html>


More information about the Concurrency-interest mailing list