Are ArrayLists more than twice as slow as arrays?

user_1768232 0
Viewed 4922

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]);
    }
}
arraylist arrays java performance
4 Answers

If you store millions of objects, then the Add or Contains functions will be super slow. Best way is to split it using hashMap of Arrays. Although similar algorithms can be used for other types of objects, this is how I improved 1000 times faster the processing of 10 million strings (the memory taken is 2-3 times more)

public static class ArrayHashList  {
    private String temp1, temp2;
    HashMap allKeys = new HashMap();
    ArrayList curKeys;  
    private int keySize;
    public ArrayHashList(int keySize) {
        this.keySize = keySize;
    }   
    public ArrayHashList(int keySize, String fromFileName) {
        this.keySize = keySize;
        String line;
        try{
            BufferedReader br1 = new BufferedReader(new FileReader(fromFileName));        
            while ((line = br1.readLine()) != null) 
                addString(line);
            br1.close();
        }catch(Exception e){
            e.printStackTrace();
        }
    }   
    public boolean addString(String strToAdd) {  
        if (strToAdd.length()<keySize)
            temp1 = strToAdd;
        else
            temp1 = strToAdd.substring(0,keySize);
        if (!allKeys.containsKey(temp1))
            allKeys.put(temp1,new ArrayList());
        curKeys =  (ArrayList)allKeys.get(temp1);
        if (!curKeys.contains(strToAdd)){
            curKeys.add(strToAdd);
            return true;
        }
        return false;
    }
    public boolean haveString(String strCheck) { 
        if (strCheck.length()<keySize)
            temp1 = strCheck;
        else
            temp1 = strCheck.substring(0,keySize);
        if (!allKeys.containsKey(temp1))
            allKeys.put(temp1,new ArrayList());
        curKeys =  (ArrayList)allKeys.get(temp1);
        return curKeys.contains(strCheck);
    }
}

to init and use it:

ArrayHashList fullHlist = new ArrayHashList(3, filesPath+"\\allPhrases.txt");       
ArrayList pendingList = new ArrayList();
BufferedReader br1 = new BufferedReader(new FileReader(filesPath + "\\processedPhrases.txt"));
while ((line = br1.readLine()) != null) {
    wordEnc = StrUtil.GetFirstToken(line,",~~~,");
    if (!fullHlist.haveString(wordEnc))
        pendingList.add(wordEnc);
}
br1.close();
user_64130280
Related