Неожиданное наказание за производительность в Java

Я реализовал список GapBuffer на Java, и я не могу понять, почему он получает такое ограничение производительности. Аналогичный код, написанный на С#, ведет себя так, как ожидалось: вставка в середину списка намного быстрее, чем реализация С# 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.)

Ответы

 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;

 }