Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Are ArrayLists more than twice as slow as arrays?

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
  • ArrayLists are more than twice as slow as the corresponding array.

The Questions

  1. Why is ArrayList so much slower?
  2. 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]);
    }
}
like image 493
durron597 Avatar asked Dec 09 '13 22:12

durron597


People also ask

Why insertion and deletion in ArrayList is slow compared to LinkedList?

Why insertion and deletion in ArrayList is slow compared to LinkedList ? ArrayList internally uses and array to store the elements, when that array gets filled by inserting elements a new array of roughly 1.5 times the size of the original array is created and all the data of old array is copied to new array.

What is the use of ArrayList in Java?

ArrayList internally uses and array to store the elements, when that array gets filled by inserting elements a new array of roughly 1.5 times the size of the original array is created and all the data of old array is copied to new array.

Should we mention the size of the ArrayList while creating its object?

One need not mention the size of the ArrayList while creating its object. Even if we specify some initial capacity, we can add more elements. Base 3: An array can contain both primitive data types as well as objects of a class depending on the definition of the array.

Does ArrayList have dynamic size in Java?

Note: ArrayList in Java (equivalent to vector in C++) having dynamic size. It can be shrunk or expanded based on size. ArrayList is a part of the collection framework and is present in java.util package .


2 Answers

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.

like image 122
Stephen C Avatar answered Nov 15 '22 15:11

Stephen C


Keep in mind that in using ArrayList, you are actually calling a function, which in the case of get() actually makes two other function calls. (One of which is a range check, which I suspect may be part of the delay).

The important thing with ArrayList, is not so much how much faster or slower it is compared with straight arrays, but that it's access time always constant (like arrays). In the real world, you'll almost always find that the added delay is negligible. Especially if you have an application that even thinks about connecting to a database. :)

In short, I think your test (and the results) are legit.

like image 41
matt forsythe Avatar answered Nov 15 '22 15:11

matt forsythe