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

Viktor Klang viktor.klang at gmail.com
Fri Apr 22 04:37:11 EDT 2016


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


More information about the Concurrency-interest mailing list