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

可以在 here 找到间隙缓冲区的代码。 ，可以找到基准入口点的代码 here . (您可以将对 Flow.***Exception 的任何引用替换为 RuntimeException。)

Answer 1

您手动复制数组的所有内容。请改用 System.arraycopy。它比手动副本快得多(它是本地的并使用特殊魔法)。您还可以查看 ArrayList 源代码，它肯定会使用 System.arraycopy 移动元素，而不是一个一个地移动元素。

关于添加/删除方法的不同性能。用 Java 编写微基准测试并不是一件容易的事。详情请阅读How do I write a correct micro-benchmark in Java?很难说，你的情况到底发生了什么。但我看到，您首先填充列表，然后才从中删除项目。在这种情况下，只执行 (index > gapPos) 分支。因此，如果 JIT 编译该代码，则可能会发生 CPU 分支预测，这将进一步加速该代码(因为您的测试用例中不太可能出现第一个分支)。删除将对两个分支造成几乎相同的次数，并且无法进行优化。所以真的很难说，到底发生了什么。例如，您应该尝试其他访问模式。或内部有缝隙的特制阵列。或者其他例子。此外，您还应该从 JVM 输出一些调试信息，这可能会有所帮助。