11

我在 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）

4

2 回答 2

7

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

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

于 2013-04-09T14:10:48.853 回答
0 
 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 得分。尝试实现类似的东西，你会看到类似的性能。

于 2013-04-09T14:31:55.327 回答