Unexpected Performance Penalty in Java

Question

I implemented a GapBuffer list in Java, and I can't figure out why it's getting such a performance penalty. Similar code written in C# behaves as expected: inserting to the middle of the list is much faster than C#'s implementation of List. But the Java version is behaving strangely.

Here is some benchmarking information:

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.

As you can see, when you insert to the beginning of the list, the gap buffer behaves as expected: it is many, many, many times better than ArrayList. However, when inserting and removing at a random spot in the list, the gap buffer has a strange performance penalty that I can't explain. Even stranger is the fact that removing items from the GapBufferList is slower than adding items to it - according to every test I've run so far, it takes about three times longer to remove an item than it does to add one, despite the fact that their code is almost identical:

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

The code for the gap buffer can be found at here, and the code for the benchmark entrypoint can be found here. (You can replace any reference to Flow.***Exception with RuntimeException.)

Answer 1

You manually copy all content of the array. Use System.arraycopy instead. It is much faster, than a manual copy (it's native and use special magic). Also you can look at ArrayList source, it definitely moves elements with System.arraycopy and not one-by-one.

About different performance of add/remove methods. Writing microbenchmarks in java is not an easy task. For details, read How do I write a correct micro-benchmark in Java? It's hard to say, what exactly happens in your case. But I see, that you first populate your list and only then remove items from it. In this scenario, only (index > gapPos) branch is executed. So, if JIT compiles that code, then CPU branch prediction may take place, which will further speedup this code (because first branch is unlikely in your test case). Removal will hit both branches almost same number of times and no optimization can take place. So it's really hard to say, what actually happens. You should try other access patterns, for example. Or specially-crafter array with gap inside it. Or other examples. And also you should output some debugging info from JVM, it may be helpful.