Неожиданное наказание за производительность в 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.)

Ответ 1

Вы вручную копируете все содержимое массива. Вместо этого используйте System.arraycopy. Это намного быстрее, чем ручная копия (она родная и использует специальную магию). Также вы можете посмотреть источник ArrayList, он определенно перемещает элементы с помощью System.arraycopy, а не один за другим.

О различной производительности методов добавления/удаления. Написание микрообъектов в java - непростая задача. Подробнее см. Как написать правильный микро-тест в Java? Трудно сказать, что именно происходит в вашем случае. Но я вижу, что вы сначала заполняете свой список и только потом удаляете из него элементы. В этом случае выполняется только ветвь (index > gapPos). Таким образом, если JIT компилирует этот код, тогда может произойти предсказание ветвления процессора, что еще больше ускорит этот код (поскольку в вашем тестовом случае первая ветвь маловероятна). Удаление ударит по обоим ветвям почти такое же количество раз, и оптимизация не может произойти. Так что действительно сложно сказать, что на самом деле происходит. Например, вы должны попробовать другие шаблоны доступа. Или специально-крафт-массив с промежутком внутри него. Или другие примеры. А также вы должны вывести некоторую информацию об отладке из JVM, это может быть полезно.

Ответ 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. Поскольку он использует System.arraycopy (довольно умно), и вы используете циклы, оценки ArrayList. Попробуйте реализовать что-то подобное, и вы увидите аналогичную производительность.