Unexpected Java performance

Question

I have just thrown everything I know about Java optimisation out the window. I have the following task:

Given a 2D array representing a playing field and a position on the field, fill another array with the number of steps a player can make to get to every other position in the field. The player can move up, down, left and right. For example, the first neighbours will be all 1's, with the diagonals being all 2's.

For the first attempt, I tried a simple 4-way floodfill algorithm. It wad dreadfully slow.

Secondly, I decided to get rid of the recursion and use a simple Queue. It worked lovely and gave a huge speed-up (very roughly 20x). Here is the code:

private void fillCounterArray(int[] counters, int position) {
    Queue<Integer> queue = new ArrayDeque<Integer>(900);

    // Obtain the possible destinations from position, check the valid ones
    // and add it the stack.
    int[] destination = board.getPossibleDestinations(position);
    for (int i = 0; i < destination.length; i++) {
        if (board.getBoard()[destination[i]] == Board.CLEAR) {
            counters[destination[i]] = 1;
            queue.add(destination[i]);
        }
    }

    // Now fill up the space.
    while (!queue.isEmpty()) {
        int pos = queue.remove();
        int steps = counters[pos];            
        destination = board.getPossibleDestinations(pos);
        for (int i = 0; i < destination.length; i++) {
            int dest = destination[i];
            if (board.getBoard()[dest] == Board.CLEAR && (counters[dest] > steps + 1 || counters[dest] == 0)) {
                counters[dest] = steps + 1;
                queue.add(dest);
            }
        }
    }
}

Now, "common-sense" told me that the queue operations with a static array and an int-pointer would be faster. So I removed the Queue and use a standard int[] array. The code is identical, except for the queue-like operations. It now looks like this (As you can see, I use to live by the C-side :)):

private void fillCounterArray(int[] counters, int position) {

    // Array and its pointer.
    int[] queue = new int[900]; // max size of field
    int head = 0;

    // Obtain the possible destinations from position, check the valid ones
    // and add it the stack.
    int[] destination = board.getPossibleDestinations(position);
    for (int i = 0; i < destination.length; i++) {
        if (board.getBoard()[destination[i]] == Board.CLEAR) {
            counters[destination[i]] = 1;
            queue[head++] = dest[i];
        }
    }

    // Now fill up the space.
    while (head > 0) {
        int pos = queue[--head];
        int steps = counters[pos];

        destination = board.getPossibleDestinations(pos);
        for (int i = 0; i < destination.length; i++) {
            int dest = destination[i];
            if (board.getBoard()[dest] == Board.CLEAR && (counters[dest] > steps + 1 || counters[dest] == 0)) {
                counters[dest] = steps + 1;
                queue[head++] = dest;
            }
        }
    }
}

When I ran this "optimised code" it was significantly slower than using the Queue and only about twice as fast as the recursive technique. There is also hardly any difference when I declare the array as an instance variable. How is this possible?

Answer 1

Your reversed the order while optimising I think;

The queue is fifo, first in first out
The array is lifo, last in first out, as you walk it downwards

That will usually give you different performance ;-)

Answer 2

Insert two Counters in each Loop one in the for loop and one in the while loop in both versions, compare the numbers you get at the end, how many rounds do you make in each version, if you have another Loop in getPossibleDestination then log the pos variable too. I guess that would be a good starting point to figure it out.

Another way would be to print the time difference on different lines in your program, let say before the 1st loop, between both and at the end, once you compare results and know where it takes a long time in the second Version you can print timestamps in the loop on different lines.