title: Unexpected Performance Penalty in Java
body: <p>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.</p>
  
  <p>Here is some benchmarking information:</p>
  
  <pre><code>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.
  </code></pre>
  
  <p>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:</p>
  
  <pre><code>@Override
  public void add(int index, T t)
  {
      if (index &lt; 0 || index &gt; back.length - gapSize) throw new IndexOutOfBoundsException();
      if (gapPos &gt; index)
      {
          int diff = gapPos - index;
          for (int q = 1; q &lt;= diff; q++)
              back[gapPos - q + gapSize] = back[gapPos - q];
      }
      else if (index &gt; gapPos)
      {
          int diff = gapPos - index;
          for (int q = 0; q &lt; 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 &lt; 0 || index &gt;= back.length - gapSize) throw new IndexOutOfBoundsException();
      if (gapPos &gt; index + 1)
      {
          int diff = gapPos - (index + 1);
          for (int q = 1; q &lt;= diff; q++)
              back[gapPos - q + gapSize] = back[gapPos - q];
      }
      else
      {
          int diff = (index + 1) - gapPos;
          for (int q = 0; q &lt; diff; q++)
              back[gapPos + q] = back[gapPos + gapSize + q];
      }
      gapSize++;
      return back[gapPos = index];
  }
  </code></pre>
  
  <p>The code for the gap buffer can be found at <a href="http://pastebin.com/7y4f2g4R">here</a>, and the code for the benchmark entrypoint can be found <a href="http://pastebin.com/mFR7utEK">here</a>. (You can replace any reference to <code>Flow.***Exception</code> with <code>RuntimeException</code>.)</p>