[concurrency-interest] A puzzle about recursive functions in CompletableFuture

Doug Lea dl at cs.oswego.edu
Wed Dec 2 07:52:07 EST 2015


On 12/02/2015 05:34 AM, Millies, Sebastian wrote:
> I have thought of a way of doing tail-recursion elimination with CompletableFuture. It works, but I do not understand why. There must be some inter-thread communication going on about which I have not been able to find documentation. Perhaps someone here can enlighten me.
>
> public static BigInteger fibTailRecursive(int n) {
>      return n <= 2 ? ONE : fibTailRecursiveAux(n, ZERO, ONE);
> }
>
> private static BigInteger fibTailRecursiveAux(int n, BigInteger a, BigInteger b) {
>      return n <= 0 ? a : fibTailRecursiveAux(n - 1, b, a.add(b));
> }
>
> And here is the "optimized" version with TRE,
>
> public static BigInteger fibCF(int n) {
>          return n <= 2 ? ONE : fibCF(n, ZERO, ONE).join();
> }
>
> private static CompletableFuture<BigInteger> fibCF(int n, BigInteger a, BigInteger b) {
>          return n <= 0 ? terminate(a) : tailcall(() -> fibCF(n - 1, b, a.add(b)));
> }
>
> Finally, here are my problematic implementations of terminate() and tailcall():
>
> public static <T> CompletableFuture<T> terminate(T t) {
>          return completedFuture(t);
> }
>
> public static <T> CompletableFuture<T> tailcall(Supplier<CompletableFuture<T>> s) {
>          return CF.thenComposeAsync(_x -> s.get(), THREAD);
> }

(Using default Async would work at least as well.
Aside: using direct executors (run in the same thread as caller)
is almost never a good idea with CompletableFutures.)

>
> private static final CompletableFuture<?> CF = completedFuture(null);
> private static final Executor THREAD = Executors.newSingleThreadExecutor(new ThreadFactoryBuilder().setDaemon(true).build());
>

This is a variation of the issues brought up by Chris Purcell a few months
ago. In async mode, CF generally avoids StackOverflowError (SOE),
because threads help clear out dependent tasks, which they do anyway to
maximize parallelism.

In non-async mode, you can still get SOE because java compilers do not
loopify tail recursion. It would be possible to better avoid this
kind of non-async SOE by thread-local trampolining at the expense
of reducing parallelism, so we don't want to do it.

It's still an open question whether we can find some scheme that
combines both advantages.

In the mean time, there is some sentiment that default thread stack
sizes on 64bit JVMs should be expanded keep up with the times. On
32bit systems the 1MB limit is completely defensible. But expanding
to say 64MB on 64bit systems would reduce practical encounters with
SOE in these kinds of constructions by a factor of 64 or so.

-Doug




More information about the Concurrency-interest mailing list