Tail Recursion Optimization for the JVM

jvm-tail-recursion

Java library performing tail recursion optimizations on Java bytecode. It simply replaces the final recursive method calls in a function to a goto to the start of the same function.

The project uses ASM to perform bytecode manipulation.

Examples

Count down to zero

A simple tail recursive function that counts down to zero:

static void count(int n) {

    if (n == 0) {
        return;
    }
    count(n - 1);
    
}

static void count(int n) {
    while (true) {
        if (n == 0) {
            return;
        }
        n = n - 1;
    }
}

List numbers in a string

If you've ever wanted a sequence of numbers in a string:

static String numbers(int n, String s) {

    if (n == 0) {
        return s + "0";
    }
    return numbers(n - 1, s + n + ",");
    
}

static String numbers(int n, String s) {
    while (true) {
        if (n == 0) {
            return s + "0";
        }
        s = s + n + ",";
        n = n - 1;
    }
}

Enumerate all interfaces that a class implements

Tail recursive class can also be optimized inside an if-else condition. Note that here only the recursive call at the end is optimized, not the one in the loop!

static void collectInterfaces(
        Class<?> clazz, 
        Set<Class<?>> result) {
        
    for (Class<?> itf : clazz.getInterfaces()) {
        if (result.add(itf)) 
            collectInterfaces(itf, result);
    }
    Class<?> sclass = clazz.getSuperclass();
    if (sclass != null) {
        collectInterfaces(sclass, result);
        
    }
    
    
}

static void collectInterfaces(
        Class<?> clazz, 
        Set<Class<?>> result) {
    while (true) {
        for (Class<?> itf : clazz.getInterfaces()) {
            if (result.add(itf)) 
                collectInterfaces(itf, result);
        }
        Class<?> sclass = clazz.getSuperclass();
        if (sclass != null) {
            clazz = sclass;
            continue;
        }
        return;
    }
}

Side effect free instruction removal

If there are some instructions in the return path of a tail recursive call which can be removed, the library will do so. Some of these are:

• Unused variables
• Unused allocated arrays
• Unused field or array accesses

final void count(int n) {

    if (n == 0) {
        return;
    }
    count(n - 1);
    Object b = new int[Integer.MAX_INT];
    Object f = this.myField;
    Object a = this.myArray[30];
}

final void count(int n) {
    while (true) {
        if (n == 0) {
            return;
        }
        n = n - 1;
    }

    
}

Note that this causes some exceptions to not be thrown in case of programming errors. E.g. No OutOfMemoryError will be thrown in the optimized code as the new int[Integer.MAX_INT] instruction is optimized out, and no NullPointerException s are thrown if the myArray field is null .

this instance change

The optimization can be performed even if the tail recursive call is done on a different instance: (See limitations)

public class MyClass {
    public final void count(int n) {

        if (n == 0) {
            return;
        }
        new MyClass().count(n - 1);
        
        
    }
}

public class MyClass {
    public final void count(int n) {
        while (true) {
            if (n == 0) {
                return;
            }
            this = new MyClass();
            n = n - 1;
        }
    }
}

Note that setting the this variable is not valid Java code, but it is possible in bytecode.

Limitations

There are some limitations to the optimization:

1. The method must not be virtual. A virtual method is called based on the dynamic type of the object. This means that instance methods which are virtual cannot be optimized, as if the object on which the method is being invoked on changes, the recursive call cannot be simplified to a jump.
   • This could be improved in the future by analyizing the bytecode and ensuring that the recursive call can only be made on this .
   • However, default interface methods can be optimized.
2. Synchronized instance methods cannot be optimized. See the previous point for the reasons.
   • static method can be synchronized.
3. If you throw an exception in the method, the stacktrace will only show the method once, as the tail recursive calls are optimized.

Recommendations

The methods you want to be subject to optimization should be any of the following:

static
private
final

Usage

The project is released as the sipka.jvm.tailrec package on the saker.nest repository .

You can download the latest release using this link or by selecting a version and clicking Download on the Bundles tab on the sipka.jvm.tailrec package page.

It can be used in the following ways:

Part of the build process

The project integrates with the saker.build system in the following ways:

ZIP transformer

Using the sipka.jvm.tailrec.zip.transformer() task to retrieve a ZIP transformer when creating your JAR or ZIP archive will cause each .class file to be optimized by the library.

$javac = saker.java.compile(src)
saker.jar.create(
    Resources: {
        Directory: $javac[ClassDirectory],
        Resources: **,
    },
    Transformers: sipka.jvm.tailrec.zip.transformer(),
)

The above is an example for compiling all Java sources in the src directory, and creating a JAR file with the compiled and optimized classes.

Class directory optimization

You can use the sipka.jvm.tailrec.optimize() task to optimize a directory with the .class files in it.

$javac = saker.java.compile(src)

$path = sipka.jvm.tailrec.optimize($javac[ClassDirectory])

The above will simply optimize all the .class files that are the output of the Java compilation. The optimized classes are written into the build directory, and a path to it is returned by the task. ( $path )

Optimize an existing archive

If you already have an archive that you want to optimize, use the ZIP transformer as seen previously, but specify the inputs as your archive:

saker.jar.create(
    Include: my_jar_to_optimize.jar,
    Transformers: sipka.jvm.tailrec.zip.transformer(),
)

This will result in a new archive being created that contains everything from the included JAR, and each .class file will be optimized.

Command line usage

The optimization can also be performed on the command line:

java -jar sipka.jvm.tailrec.jar -output my_jar_opt.jar my_jar.jar

The above will optimize my_jar.jar and create the output of my_jar_opt.jar . You can also overwrite the input:

java -jar sipka.jvm.tailrec.jar -overwrite my_jar.jar

Which causes the input JAR to be overwritten with the result.

The input can also be a class directory.

See --help for more usage information.

With saker.build

If you already have the saker.build system at hand, you don't have to bother with downloading. You can use the main action of saker.nest to invoke the library:

java -jar saker.build.jar action main sipka.jvm.tailrec --help

Building the project

The project uses the saker.build system for building.

Use the following command, or do build it inside an IDE:

java -jar saker.build.jar -build-directory build export

See the build script for the executable build targets.

Repository structure

• src : The source files for the project
  • Sources for the ASM library are under the package sipka.jvm.tailrec.thirdparty .
• resources : Resource files for the created JAR files
• test/src : Test Java sources
• test/resources : Resource files for test cases which need them

Should I use this?

You should use it, but you should not rely on it.

In general, when you're writing production code, you'll most likely already optimize your methods in ways that it already avoids issues that are solvable with tail recursion optimization.

My recommendation is that in general you shouldn't rely on a specific optimization being performed for you. They are subject to the circumstances, and can easily break without the intention of breaking it. For example, by not paying attention and accidentally adding a new instruction after the tail recursive call that you want to optimize, will cause the optimization to not be performed. This could cause your code to break unexpectedly.

If you want an optimization done for you, you should do it yourself, or be extremely explicit about it. Make sure to add tests for the scenarios that you want to work in a specific way.

This project serves mainly educational purposes, and is also fun as you can write infinite loops like this:

public static void loopForever() {
    System.out.println("Hello world!");
    
    loopForever();
}

Magnificent!

License

The source code for the project is licensed under GNU General Public License v3.0 only .

Short identifier: GPL-3.0-only .

Official releases of the project (and parts of it) may be licensed under different terms. See the particular releases for more information.