Are ArrayLists more than twice as slow as arrays?
arraylist, arrays, java, performance
Solution
Firstly ...
Are ArrayLists more than twice as slow as arrays?
As a generalization, no. For operations that potentially involve "changing" the length of the list / array, an `ArrayList` will be faster than an array ... unless you use a separate variable to represent the array's logical size.
For other operations, the `ArrayList` is likely to be slower, though the performance ratio will most likely depend on the operation and the JVM implementation. Also note that you have only tested one operation / pattern.
Why is ArrayList so much slower?
Because an ArrayList has a distinct array object inside of it.
Operations typically involve extra indirections (e.g. to fetch the list's size and inner array) and there are extra bounds checks (e.g. checking the list's `size` and the array's length). A typical JIT compiler is (apparently) not able to optimize these away. (And in fact, you would NOT want to optimize away the inner array because that's what allows an ArrayList to grow.)
For array's of primitives, the corresponding list types involve wrapped primitive types / objects, and that adds an overhead. For example your `result += ...` involves unboxing, in the "list" cases.
Is my benchmark written well? In other words, are my results accurate?
There's nothing wrong with it technically. But it is not sufficient to demonstrate your point. For a start, you are only measuring one kind of operation: array element fetching and its equivalent. And you are only measuring for primitive types.
Finally, this largely misses the point of using `List` types. We use them because they are almost always easier to use than plain arrays. A difference in performance of (say) 2 is typically not important to overall application performance.
Problem
I wrote a test that attempts to test two things: - Whether the size of a buffer array affects its performance, even if you don't use the whole buffer - The relative performance of arrays and `ArrayList` I was kind of surprised with the results - Boxed arrays (i.e. `Integer` vs `int`) are not very much slower than the primitive version - The size of the underlying array doesn't matter very much - `ArrayList`s are more than twice as slow as the corresponding array. The Questions - Why is `ArrayList` so much slower? - Is my benchmark written well? In other words, are my results accurate? The Results ``` 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 ``` The Code 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). 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. The 6 tests have a big (131072) and a small (128) version of `int[]`, `Integer[]`, and `ArrayList<Integer>`. You can probably figure out which is which from the names. ``` 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<Integer> bigList = new ArrayList<>(131072); List<Integer> smallList = new ArrayList<>(128); @Override protected void setUp() { Random r = new Random(); for(int i = 0; i < 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 < reps; i++) { for(int j = 0; j < 128; j++) { result += bigArray[j]; } } return result; } public long timeSmallArray(int reps) { long result = 0; for(int i = 0; i < reps; i++) { for(int j = 0; j < 128; j++) { result += smallArray[j]; } } return result; } public long timeBigBoxed(int reps) { long result = 0; for(int i = 0; i < reps; i++) { for(int j = 0; j < 128; j++) { result += bigBoxed[j]; } } return result; } public long timeSmallBoxed(int reps) { long result = 0; for(int i = 0; i < reps; i++) { for(int j = 0; j < 128; j++) { result += smallBoxed[j]; } } return result; } public long timeBigList(int reps) { long result = 0; for(int i = 0; i < reps; i++) { for(int j = 0; j < 128; j++) { result += bigList.get(j); } } return result; } public long timeSmallList(int reps) { long result = 0; for(int i = 0; i < reps; i++) { for(int j = 0; j < 128; j++) { result += smallList.get(j); } } return result; } } public static void main(String[] args) { Runner.main(TestBenchmark.class, new String[0]); } } ```