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.)

Answer 1

您手动复制阵列的所有内容.请改用System.arraycopy.它比手动副本(它是原生的并使用特殊魔法)快得多.您也可以查看ArrayList源代码,它肯定会使用System.arraycopy而不是逐个移动元素.

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