Danger of Memory Reachability with Recursive Fiber Code

[Dr Heinz M. Kabutz]

Let's start with a very basic single-threaded Factorial function. I use 
divide and conquer to avoid having a stack that is too deep:

import java.math.*;
import java.util.function.*;

public class FactorialBasic implements IntFunction<BigInteger> {
public BigInteger apply(int n) {
return apply(0, n);
}

private BigInteger apply(int from, int to) {
if (from == to) {
if (from == 0) return BigInteger.ONE;
else return BigInteger.valueOf(from);
}
int mid = (from + to) >>> 1;

int leftFrom = from;
int leftTo = mid;
int rightFrom = mid + 1;
int rightTo = to;

var left = apply(leftFrom, leftTo);
var right = apply(rightFrom, rightTo);

return left.multiply(right);
}
}

To parallelize this with CompletableFuture is trivial:

import java.math.*;
import java.util.concurrent.*;
import java.util.function.*;

public class FactorialCompletableFuture implements IntFunction<BigInteger> {
public BigInteger apply(int n) {
return apply(0, n).join();
}
private CompletableFuture<BigInteger> apply(int from, int to) {
if (from == to) {
if (from == 0) return CompletableFuture.completedFuture(BigInteger.ONE);
else return CompletableFuture.completedFuture(BigInteger.valueOf(from));
}
int mid = (from + to) >>> 1;

int leftFrom = from;
int leftTo = mid;
int rightFrom = mid + 1;
int rightTo = to;

var left = apply(leftFrom, leftTo);
var right = apply(rightFrom, rightTo);

return left.thenCombineAsync(right, BigInteger::multiply);
}
}

However, when we now write this with Fibers, we have several choices of 
how to write it. For example, we could write it like this, where we do 
the recursive calls inside the Fiber:

import java.math.*;
import java.util.concurrent.*;
import java.util.function.*;

public class FactorialFibers1 implements IntFunction<BigInteger> {
public BigInteger apply(int n) {
return apply(0, n).join();
}

public Fiber<BigInteger> apply(int from, int to) {
if (from == to) {
if (from == 0) return Fiber.schedule(() -> BigInteger.ONE);
else return Fiber.schedule(() -> BigInteger.valueOf(from));
}
int mid = (from + to) >>> 1;

int leftFrom = from;
int leftTo = mid;
int rightFrom = mid + 1;
int rightTo = to;

return Fiber.schedule(ForkJoinPool.commonPool(), () -> {
var left = apply(leftFrom, leftTo);
var right = apply(rightFrom, rightTo);
return left.join().multiply(right.join());
});
}
}

Or like this, where we do the recursive calls before the Fiber.schedule():

import java.math.*;
import java.util.concurrent.*;
import java.util.function.*;

public class FactorialFibers2 implements IntFunction<BigInteger> {
public BigInteger apply(int n) {
return apply(0, n).join();
}

public Fiber<BigInteger> apply(int from, int to) {
if (from == to) {
if (from == 0) return Fiber.schedule(() -> BigInteger.ONE);
else return Fiber.schedule(() -> BigInteger.valueOf(from));
}
int mid = (from + to) >>> 1;

int leftFrom = from;
int leftTo = mid;
int rightFrom = mid + 1;
int rightTo = to;

var left = apply(leftFrom, leftTo);
var right = apply(rightFrom, rightTo);

return Fiber.schedule(ForkJoinPool.commonPool(),
() -> left.join().multiply(right.join()));
}
}

Seems almost the same, right? In terms of concurrency, there is not a 
big difference. But in terms of memory reachability, there seems to be.

In the case of FactorialFibers1, the left and right fiber objects could 
be collected once we call join() on them. In the case of 
FactorialFibers2, there is an implicit memory reference to them from 
within the lambda object so that they cannot be collected. In other 
words, FactorialFibers1 has only local variables pointing to the left 
and right fibers, whereas FactorialFibers2 has fields pointing to them. 
In the case of local variables, Java is smart enough to recognize when 
these will never be used again and can clear them. It cannot do so with 
fields.

Now for some results.

Here is a test class:

import java.math.*;
import java.util.*;
import java.util.function.*;
import java.util.stream.*;

// -XX:+UseParallelGC -Xmx8g -verbose:gc
public class FactorialAllTest {
public static void main(String... args) {
Stream.of(
new FactorialBasic(),
new FactorialCompletableFuture(),
new FactorialFibers1(),
new FactorialFibers2()
).forEach(
fact ->
{
for (int j = 0; j < 3; j++) System.gc();
check(fact, 100_000, 708_218);
Timer gcInvoker = new Timer(true);
gcInvoker.schedule(new TimerTask() {
public void run() {
// Cause full GC every 5 seconds during run
// to get rid of prematurely tenured objects
System.gc();
}
}, 5000, 5000);
long time = System.nanoTime();
System.out.println(fact.getClass().getSimpleName());
check(fact, 5_000_000, 49_524_628);
time = System.nanoTime() - time;
gcInvoker.cancel();
System.out.println(time / 1_000_000 + "ms");
System.out.println();
}
);
}

protected static void check(IntFunction<BigInteger> func, int n, int 
bitcount) {
int actual = func.apply(n).bitCount();
if (actual != bitcount)
throw new AssertionError(func.getClass().getSimpleName() +
"(" + n + ") incorrect. " +
"expected=" + bitcount + ", actual=" + actual);
System.out.printf("%s(%d) OK%n", func.getClass().getSimpleName(), n);
}
}

It is not supposed to test the performance of the various approaches at 
this point. I have other test classes for that. Since Fibers are still 
very much in development, I don't think it would be fair to let them 
face-off against an established construct like CompletableFutures.

All I'm interested at this point is the astounding difference in 
resident set size in the memory between the various approaches. A small 
change can cause a whole bunch of memory to stay strongly reachable.

As we continue along the path of Project Loom, I believe it will be 
necessary to establish good coding idioms that others can follow. 
Letting them code whatever they want and then hoping it will perform 
well is going to lead to disappointment.

I will mention my thoughts on the "structured concurrency" approaches in 
another email :-)

Regards

Heinz
-- 
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java™ Specialists' Newsletter" - www.javaspecialists.eu
Java Champion - www.javachampions.org
JavaOne Rock Star Speaker
Tel: +30 69 75 595 262
Skype: kabutz