Java中的意外性能惩罚

Question

我在Java中实现了一个GapBuffer列表，但我无法弄清楚为什么它会有如此大的性能损失。用C#编写的类似代码表现正常：将元素插入到列表中部比C#的List实现要快得多。但是Java版本的表现非常奇怪。

以下是一些基准测试信息：

Adding/removing 10,000,000 items @ the end of the dynamic array...
ArrayList: 683 milliseconds
GapBufferList: 416 milliseconds

Adding/removing 100,000 items @ a random spot in the dynamic array...
  - ArrayList add: 721 milliseconds
  - ArrayList remove: 612 milliseconds
ArrayList: 1333 milliseconds
  - GapBufferList add: 1293 milliseconds
  - GapBufferList remove: 2775 milliseconds
GapBufferList: 4068 milliseconds

Adding/removing 100,000 items @ the beginning of the dynamic array...
ArrayList: 2422 milliseconds
GapBufferList: 13 milliseconds

Clearly, the GapBufferList is the better option.

你可以看到，在列表的开头插入时，间隙缓冲区表现如预期的那样：它比ArrayList好得多，好得多，好得多。但是，在列表的任意位置插入和删除时，间隙缓冲区会有奇怪的性能惩罚，我无法解释。更奇怪的是，从GapBufferList中删除项目比添加项目要慢 - 根据我目前运行的每个测试，删除一个项目需要花费大约三倍的时间，尽管它们的代码几乎相同：

@Override
public void add(int index, T t)
{
    if (index < 0 || index > back.length - gapSize) throw new IndexOutOfBoundsException();
    if (gapPos > index)
    {
        int diff = gapPos - index;
        for (int q = 1; q <= diff; q++)
            back[gapPos - q + gapSize] = back[gapPos - q];
    }
    else if (index > gapPos)
    {
        int diff = gapPos - index;
        for (int q = 0; q < diff; q++)
            back[gapPos + q] = back[gapPos + gapSize + q];
    }
    gapPos = index;
    if (gapSize == 0) increaseSize();
    back[gapPos++] = t; gapSize--;
}
@Override
public T remove(int index)
{
    if (index < 0 || index >= back.length - gapSize) throw new IndexOutOfBoundsException();
    if (gapPos > index + 1)
    {
        int diff = gapPos - (index + 1);
        for (int q = 1; q <= diff; q++)
            back[gapPos - q + gapSize] = back[gapPos - q];
    }
    else
    {
        int diff = (index + 1) - gapPos;
        for (int q = 0; q < diff; q++)
            back[gapPos + q] = back[gapPos + gapSize + q];
    }
    gapSize++;
    return back[gapPos = index];
}

缓冲区代码可以在这里找到，基准入口的代码可以在这里找到。（您可以将任何对Flow.***Exception的引用替换为RuntimeException。）

- leviathanbadger

Answer 1

你可以使用System.arraycopy而不是手动复制数组的所有内容。它比手动复制快得多（它是本地的并且使用特殊技术）。此外，您可以查看ArrayList源代码，它肯定会使用System.arraycopy移动元素而不是逐个移动。

关于添加/删除方法的不同性能。在Java中编写微基准测试并不容易。有关详细信息，请阅读如何在Java中编写正确的微基准测试？很难说，在您的情况下确切发生了什么。但我看到你首先填充列表，然后才从中删除项目。在这种情况下，只执行(index > gapPos)分支。因此，如果JIT编译该代码，则CPU分支预测可能会发生，这将进一步加速此代码（因为在您的测试用例中第一个分支不太可能）。删除将几乎同样多次地击中两个分支，并且无法进行任何优化。因此，真正发生了什么实际上很难说。您应该尝试其他访问模式，例如。或者具有间隙的特制数组。或其他示例。您还应该从JVM输出一些调试信息，这可能会有所帮助。

- maxkar

---

好的，谢谢，这解释了为什么LinkedList比ArrayList慢的部分原因，但并没有解释remove函数为什么比add函数慢三倍。你知道是为什么吗？ - leviathanbadger

同样的原因，ArrayList 在 remove 方法中也使用了相同的方法。 - Thihara

好的，我接受这个答案，因为一旦我切换到System.arraycopy，remove与add之间的奇怪惩罚就消失了。我仍然想知道为什么一开始会有这样的惩罚，但现在问题已经解决了。感谢您的回答！ - leviathanbadger

arracopy方法是本地的，并且保证比手动复制操作产生更好的结果... - Thihara

增加了一些有关添加/删除性能的见解。据我所见，它们的平均复杂度相同。因此，差异可能是由JIT和CPU优化等微观效应引起的。 - maxkar

Answer 2

 public E remove(int index) {

     rangeCheck(index);

     modCount++;

     E oldValue = elementData(index);

     int numMoved = size - index - 1;

     if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);

     elementData[--size] = null; // Let gc do its work

     return oldValue;

 }

这是ArrayList的remove方法的源代码。由于它巧妙地使用了System.arraycopy，而你使用循环，所以ArrayList得分更高。尝试实现类似的方法，你会看到类似的性能。

- Thihara