[concurrency-interest] CompletableFuture improvements

Doug Lea dl at cs.oswego.edu
Tue Aug 18 09:14:49 EDT 2015

On 08/17/2015 02:27 PM, Chris Purcell wrote:

> I may be way off-base on /why/ CompletableFuture has a work queue of callbacks.
> I assumed it was because, if you have a long chain (a couple of thousand) of
> dependent futures, and you call dependent callbacks recursively within the
> upstream future's completion handler, then the call stack will overflow. You can
> easily demonstrate this with CompletableFutures:

CompletableFuture uses a Treiber-stack-like completion list for
several related reasons: it is non-blocking, atomically resolves
races (like when adding to a CF that is in the midst of completing),
allows helping across threads, and helps avoids stack-overflow
(especially with the 8u update to do so even across threads).

As discussed last year, we'd like to catch as many of these
cases as possible, because StackOverflowError is otherwise
so problematic on JVMs -- some are never caught or handled.
This is not special to completion designs but more common with them.
(Aside: it is an odd state of affairs that you need to emulate
stacks on heaps, with greater peak total memory overhead,
to avoid stack overflow.) Without some JVM-level tail-recursion
support (and maybe even with it), the options are limited in cases
where the recursion occurs in the bodies of lambdas where we
cannot see it. That's the main difference in your two examples:

               CompletableFuture<Integer> newTail = new CompletableFuture<>();
               tail.thenAccept(v -> newTail.complete(v + 1));
               tail = newTail;

               tail = tail.thenApply(v -> v + 1);

We can "trampoline" thenAccept and thenApply, but we don't
even see the newTail.complete(v + 1) because it is inside a
lambda. On the other hand, if the first usage were async, the
cross-thread mechanisms kick in to prevent SOE:

     public void async_recursive_callbacks() {
         CompletableFuture<Integer> head = new CompletableFuture<>();
         CompletableFuture<Integer> tail = head;
         for (int i = 0; i < 2_000; i++) {
             CompletableFuture<Integer> newTail = new CompletableFuture<>();
             tail.thenAcceptAsync(v -> newTail.complete(v + 1));
             tail = newTail;
         assertEquals(2007, (int) tail.join());

It is possible that we could do better here. I'll investigate.
Your thread-local back-channel approach handles some cases,
but I don't think can coexist with other support.


More information about the Concurrency-interest mailing list