意外的Java性能表现

Question

我刚刚把我所知道的有关Java优化的所有内容都放弃了。 我有以下任务：

给定表示游戏场地和场地上位置的2D数组，在另一个数组中填充玩家可以移动到场地上每个其他位置所需步骤的数量。 玩家可以向上、向下、向左和向右移动。 例如，第一批邻居将是所有1，对角线将是所有2。

在第一次尝试中，我尝试了一个简单的四方洪水填充算法。它非常慢。

其次，我决定摆脱递归并使用一个简单的队列。 它运行得非常好，并且大大提高了速度（大约20倍）。 这里是代码：

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);
            }
        }
    }
}

现在，“常识”告诉我，使用静态数组和int指针进行队列操作会更快。因此，我删除了队列并使用标准的int[]数组。代码相同，除了类似于队列的操作。现在它看起来像这样（你可以看到，我曾经生活在C端 :))：

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;
            }
        }
    }
}

当我运行这个“优化代码”时，它比使用队列慢得多，只比递归技术快两倍左右。当我将数组声明为实例变量时，几乎没有任何差别。这是怎么可能的？

- Jaco Van Niekerk

---

请看 https://dev59.com/hHRB5IYBdhLWcg3wz6UK，以排除基准测试的注意事项。 - Vadzim

Vadzim，我并不是在尝试对上述内容进行基准测试。当我运行每个版本时，性能差异非常明显。其中一个版本比另一个版本快大约10倍，这完全违反直觉。如果我应用正确的基准测试技术，最终会得到更准确的性能差异估计。 - Jaco Van Niekerk

请注意，如果元素未被添加，Queue.offer() 可能会返回 false，这可能解释了差异（请参见 http://docs.oracle.com/javase/6/docs/api/java/util/ArrayDeque.html#offer(E)）。 - user180100

@Jaco Van Niekerk，关于基准测试注意事项的重点在于您可能正在测量完全不同的内容。例如解释性代码与JIT编译的代码之间可能会有20倍的差异。 - Vadzim

可能是因为Java数组边界检查？ - tanyehzheng

Answer 1

我认为你在优化时颠倒了顺序；

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

那通常会给你不同的表现;-)

- IvoTops

---

非常准确。我怎么会错过那个...更改为头尾指针后，代码按预期优于Dequeue。谢谢！ - Jaco Van Niekerk

Answer 2

在每个循环中插入两个计数器，一个在for循环中，另一个在while循环中，在两个版本中比较最终得到的数字，每个版本中你要进行多少轮循环，如果在getPossibleDestination中有另一个循环，则也记录pos变量。我想这将是找出问题的好起点。

另一种方法是在程序中打印不同行的时间差，比如在第一个循环之前、两个循环之间以及最后，在比较结果并知道第二个版本中哪里需要更长时间后，可以在不同行上打印循环的时间戳。

- CloudyMarble

---

我不确定那样做会有什么成就。计数器将保持相同，只是从标准队列更改为整型数组的队列操作不同了。“逻辑”是相同的。 - Jaco Van Niekerk

我没有完全阅读代码，但我会记录它，这不会花费太多时间，但这取决于你，如果你确定轮数，可以尝试使用时间日志。 - CloudyMarble

你可以轻松地进行基准测试并找到问题，而不是花费时间打注释。 - CloudyMarble

我不同意你的看法... 我已经知道代码是等效的（不需要计数器），而且我也确切地知道在哪里，即将ArrayDeque替换为int-array的位置（不需要时间测试）。无论如何还是谢谢你。 - Jaco Van Niekerk

这段代码并不完全相同。据我所见，你使用 Deque 来实现先进先出 (FIFO) 的队列，而你的 int[] 则用作后进先出（LIFO）的堆栈。因此，这可能会影响需要执行多少轮操作。 - user1252434