Recursion in Java enums?

Question

I've been trying for 3 hours and I just can't understand what is happening here.

I have an enum 'Maze'. For some reason, when the method 'search' is called on this enum it's EXTREMELY slow (3 minutes to run). However, if I copy the same method to another class as a static method, and I call it from the enum 'Maze' it runs in one second!

I don't understand why? is there any problem with recursive methods in Java enums?? What am I doing wrong?

public enum Maze
{
    A("A.txt"), B("B.txt");

    // variables here...

    Maze(String fileName)
    {
        loadMap(fileName);
        nodeDistances = new int[nodes.size()][nodes.size()];
        setNeighbors();
        setDistances();
    }

    ... more methods here ...

    private void setDistances()
    {
        nodeDistances = new int[nodes.size()][nodes.size()];

        for (int i = 0; i < nodes.size(); i++) {
            setMax(nodeDistances[i]);
            // This works!!!
            TestMaze.search(nodes, nodeDistances[i], i, 0);
            // This DOESN'T WORK
            //search(nodes, nodeDistances[i], i, 0);
        }
    }

    public void setMax(int[] a) {
        for (int i=0; i<a.length; i++) {
            a[i] = Integer.MAX_VALUE;
        }
    }

    public void search(List<Node> allNodes, int[] distances, int curNodeIndex, int curDist)
    {
        if (curDist < distances[curNodeIndex])
        {
            distances[curNodeIndex] = curDist;

            for (Node n : allNodes.get(curNodeIndex).getNeighbors()) {
                search(allNodes, distances, n.getNodeIndex(), curDist + 1);
            }
        }
    }
}

public class TestMaze
{
    public static void search(List<Node> allNodes, int[] distances, int curNodeIndex, int curDist)
    {
        if (curDist < distances[curNodeIndex])
        {
            distances[curNodeIndex] = curDist;

            for (Node n : allNodes.get(curNodeIndex).getNeighbors()) {
                search(allNodes, distances, n.getNodeIndex(), curDist + 1);
            }
        }
    }
}

Answer 1

One obvious question is, do the two variants of search() both produce correct results?

My best guess is that you're running into a class load order problem. This is because your search routine is kicked off as a side-effect of the enum's constructor. Since you didn't post the full code I can't say for sure, but try this:

Maze(String fileName)
{
    //show when the individual enum values get constructed
    new Exception("constructor for " + fileName).printStackTrace();

    loadMap(fileName);
    nodeDistances = new int[nodes.size()][nodes.size()];
    setNeighbors();
    setDistances();
}

... and see if you get different results when you call the enum's search method vs. the static version in the other class.

Answer 2

This strange behaviour seems to be related to JIT. It seems to be that methods work slower if they were JIT-compiled during initialization of their classes (i.e. if they were frequenty called from static initializers, it also happens in the OP's case, because enum values are instantiated during initialization).

Here is a small test:

public class Test {
    public static final long N = 40;

    static {
        long t = System.currentTimeMillis();
        computeStatic1(N);
        System.out.println("computeStatic1 in initializer: " + (System.currentTimeMillis() - t));

        Test x = new Test();
        t = System.currentTimeMillis();
        x.compute1(N);
        System.out.println("compute1 in initializer: " + (System.currentTimeMillis() - t));

        computeStatic2(10); // Not enough to launch JIT
        x.compute2(10); // Not enough to launch JIT
    }     

    public static void main(String[] args) throws Exception {
        long t = System.currentTimeMillis();
        computeStatic1(N);
        System.out.println("computeStatic1 in main: " + (System.currentTimeMillis() - t));

        Test x = new Test();
        t = System.currentTimeMillis();
        x.compute1(N);
        System.out.println("compute1 in main: " + (System.currentTimeMillis() - t));

        t = System.currentTimeMillis();
        computeStatic2(N);
        System.out.println("computeStatic2 in main: " + (System.currentTimeMillis() - t));

        t = System.currentTimeMillis();
        x.compute2(N);
        System.out.println("compute2 in main: " + (System.currentTimeMillis() - t));
    }

    private long compute1(long n) {
        if (n == 0 || n == 1) return 1;
        else return compute1(n - 2) + compute1(n - 1);
    }

    private static long computeStatic1(long n) {
        if (n == 0 || n == 1) return 1;
        else return computeStatic1(n - 2) + computeStatic1(n - 1);
    }

    private long compute2(long n) {
        if (n == 0 || n == 1) return 1;
        else return compute2(n - 2) + compute2(n - 1);
    }

    private static long computeStatic2(long n) {
        if (n == 0 || n == 1) return 1;
        else return computeStatic2(n - 2) + computeStatic2(n - 1);
    }
}

Results (Sun JVM):

> java Test
computeStatic1 in initializer: 4360
compute1 in initializer: 4578
computeStatic1 in main: 4359
compute1 in main: 4610
computeStatic2 in main: 2859
compute2 in main: 2859

JIT disabled:

> java -Xint Test
computeStatic1 in initializer: 20578
compute1 in initializer: 21656
computeStatic1 in main: 20250
compute1 in main: 21391
computeStatic2 in main: 20250
compute2 in main: 21375

In IBM J9 VM this behaviour is observed only for static methods:

$ java Test
computeStatic1 in initializer: 5053
compute1 in initializer: 2488
computeStatic1 in main: 5044
compute1 in main: 2473
computeStatic2 in main: 2597
compute2 in main: 2489