Recursion in Java Enumerations?

Question

I tried for 3 hours and I just can't figure out what is going on here.

I have a Labyrinth enumeration. For some reason, when the "search" method is called on this listing, it is EXTREMELY slow (3 minutes to start). However, if I copy the same method to another class as a static method, and I call it from the Labyrinth enumeration, it starts in one second!

I do not understand why? is there a 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

This weird behavior seems to be related to JIT. It seems that methods work more slowly if they were JIT-compiled during the initialization of their classes (i.e. if they were often called from static initializers, this also happens in the case of OP, because enum values ​​are created during initialization).

Here is a little 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 is 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 

On IBM J9 VM, this behavior is only observed 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 

Answer 2

One obvious question: do both search options () give the correct results?

My best guess is that you are facing a class load order problem. This is because your search procedure starts as a side effect of the listing constructor. Since you have not published the full code, I cannot say for sure, but try the following:

 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 search method and the static version in another class.