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

Millies, Sebastian Sebastian.Millies at softwareag.com
Sat Apr 23 06:50:58 EDT 2016


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<mailto: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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20160423/849f2c72/attachment-0001.html>


More information about the Concurrency-interest mailing list