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

Viktor Klang viktor.klang at gmail.com
Sat Apr 23 15:45:03 EDT 2016


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,
√
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20160423/08c5fafd/attachment.html>


More information about the Concurrency-interest mailing list