title: Are ArrayLists more than twice as slow as arrays?
body: <p>I wrote a test that attempts to test two things:</p>
  
  <ul>
  <li>Whether the size of a buffer array affects its performance, even if you don't use the whole buffer</li>
  <li>The relative performance of arrays and <code>ArrayList</code></li>
  </ul>
  
  <p>I was kind of surprised with the results</p>
  
  <ul>
  <li>Boxed arrays (i.e. <code>Integer</code> vs <code>int</code>) are not very much slower than the primitive version</li>
  <li>The size of the underlying array doesn't matter very much</li>
  <li><code>ArrayList</code>s are more than twice as slow as the corresponding array.</li>
  </ul>
  
  <h3>The Questions</h3>
  
  <ol>
  <li>Why is <code>ArrayList</code> so much slower?</li>
  <li>Is my benchmark written well? In other words, are my results accurate?</li>
  </ol>
  
  <h3>The Results</h3>
  
  <pre><code> 0% Scenario{vm=java, trial=0, benchmark=SmallArray} 34.57 ns; ?=0.79 ns @ 10 trials
  17% Scenario{vm=java, trial=0, benchmark=SmallBoxed} 40.40 ns; ?=0.21 ns @ 3 trials
  33% Scenario{vm=java, trial=0, benchmark=SmallList} 105.78 ns; ?=0.09 ns @ 3 trials
  50% Scenario{vm=java, trial=0, benchmark=BigArray} 34.53 ns; ?=0.05 ns @ 3 trials
  67% Scenario{vm=java, trial=0, benchmark=BigBoxed} 40.09 ns; ?=0.23 ns @ 3 trials
  83% Scenario{vm=java, trial=0, benchmark=BigList} 105.91 ns; ?=0.14 ns @ 3 trials
  
   benchmark    ns linear runtime
  SmallArray  34.6 =========
  SmallBoxed  40.4 ===========
   SmallList 105.8 =============================
    BigArray  34.5 =========
    BigBoxed  40.1 ===========
     BigList 105.9 ==============================
  
  vm: java
  trial: 0
  </code></pre>
  
  <h3>The Code</h3>
  
  <p>This code was written in Windows using Java 7 and Google caliper 0.5-rc1 (because last I checked 1.0 doesn't work in Windows yet).</p>
  
  <p>Quick outline: in all 6 tests, in each iteration of the loop, it adds the values in the first 128 cells of the array (no matter how big the array is) and adds that to a total value. Caliper tells me how many times the test should run, so I loop through that addition 128 times.</p>
  
  <p>The 6 tests have a big (131072) and a small (128) version of <code>int[]</code>, <code>Integer[]</code>, and <code>ArrayList&lt;Integer&gt;</code>. You can probably figure out which is which from the names.</p>
  
  <pre><code>import java.util.ArrayList;
  import java.util.List;
  import java.util.Random;
  
  import com.google.caliper.Runner;
  import com.google.caliper.SimpleBenchmark;
  
  public class SpeedTest {    
      public static class TestBenchmark extends SimpleBenchmark {
          int[] bigArray = new int[131072];
          int[] smallArray = new int[128];
          Integer[] bigBoxed = new Integer[131072];
          Integer[] smallBoxed = new Integer[128];
          List&lt;Integer&gt; bigList = new ArrayList&lt;&gt;(131072);
          List&lt;Integer&gt; smallList = new ArrayList&lt;&gt;(128);
  
          @Override
          protected void setUp() {
              Random r = new Random();
              for(int i = 0; i &lt; 128; i++) {
                  smallArray[i] = Math.abs(r.nextInt(100));
                  bigArray[i] = smallArray[i];
                  smallBoxed[i] = smallArray[i];
                  bigBoxed[i] = smallArray[i];
                  smallList.add(smallArray[i]);
                  bigList.add(smallArray[i]);
              }
          }
  
          public long timeBigArray(int reps) {
              long result = 0;
              for(int i = 0; i &lt; reps; i++) {
                  for(int j = 0; j &lt; 128; j++) {
                      result += bigArray[j];
                  }
              }
              return result;
          }
  
          public long timeSmallArray(int reps) {
              long result = 0;
              for(int i = 0; i &lt; reps; i++) {
                  for(int j = 0; j &lt; 128; j++) {
                      result += smallArray[j];
                  }
              }
              return result;
          }
  
          public long timeBigBoxed(int reps) {
              long result = 0;
              for(int i = 0; i &lt; reps; i++) {
                  for(int j = 0; j &lt; 128; j++) {
                      result += bigBoxed[j];
                  }
              }
              return result;
          }
  
          public long timeSmallBoxed(int reps) {
              long result = 0;
              for(int i = 0; i &lt; reps; i++) {
                  for(int j = 0; j &lt; 128; j++) {
                      result += smallBoxed[j];
                  }
              }
              return result;
          }
  
          public long timeBigList(int reps) {
              long result = 0;
              for(int i = 0; i &lt; reps; i++) {
                  for(int j = 0; j &lt; 128; j++) {
                      result += bigList.get(j);
                  }
              }
              return result;
          }
  
          public long timeSmallList(int reps) {
              long result = 0;
              for(int i = 0; i &lt; reps; i++) {
                  for(int j = 0; j &lt; 128; j++) {
                      result += smallList.get(j);
                  }
              }
              return result;
          }
      }
  
      public static void main(String[] args) {
          Runner.main(TestBenchmark.class, new String[0]);
      }
  }
  </code></pre>