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

Millies, Sebastian Sebastian.Millies at softwareag.com
Wed Dec 2 05:34:13 EST 2015


Hello there,

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.

This particular way of doing TRE is not in itself especially worthwhile, because it is almost trivial to transform a tail-recursive function into a loop manually. However, I think it’s still interesting. So, as an example let's use this tail-recursive definition of the Fibonacci series:

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, in which the elementary case and recursive case are wrapped in methods that return a CompletableFuture:

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)));
}

This is similar to Pierre-Yves Saumont's approach (cf. http://www.javacodegeeks.com/2015/10/stack-safe-recursion-in-java.html). However, his implementation uses custom classes and an explicit while-loop. With TRE I can compute e. g. fibCF(5000), although the recursive version normally encounters a StackOverflowError at around n = 1550 on my machine.

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);
}

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

(The ThreadFactoryBuilder is from Guava.)

The interesting thing is that the recursive call is inside the lambda, so cannot be seen by the completion handler. It is essential that I use thenComposeAsync() and a dedicated thread. Using either thenCompose() or a current-thread Executor (Executor e = Runnable::run) will lead to the dreaded SOE. So there must be some implicit interaction between the current thread and the dedicated thread that prevents this.

I suspect it may have to do with the fact that the "dummy" future CF is already completed, so the downstream task would by default be completed in the client thread, but is then somehow handed off to the explicitly required dedicated thread, with the "recursive" call being landed in the client thread again. But how would this prevent SOE?

Could anyone explain to me, please, how my coding works?

-- Sebastian Millies




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




More information about the Concurrency-interest mailing list