Performance comparison of java.util.ArrayList, javaslang.collection.vector, and it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap

IntLookupPerformanceComparison.java

import it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap;
import javaslang.collection.Vector;

import java.math.BigDecimal;
import java.math.MathContext;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReference;
import java.util.function.Consumer;
import java.util.function.Supplier;

public class IntLookupPerformanceComparison {

  private static int RUNS = 11;
  private static int REPS = 10;
  private static int SIZE = 100000;

  private static long medianTime(Runnable operation) {
    long[] times = new long[RUNS];
    for (int i = 0; i < RUNS; i++) {
      long start = System.nanoTime();
      for (int j = 0; j < REPS; j++) {
        operation.run();
      }
      long end = System.nanoTime();
      times[i] = end - start;
    }
    Arrays.sort(times);
    return times[RUNS / 2];
  }

  private static <C> void printTime(Supplier<C> collection, Consumer<C> operation, String desc) {
    Runnable r = () -> {
      C coll = collection.get();
      operation.accept(coll);
    };
    long medianNanos = medianTime(r);
    System.out.println(desc + ": " + collection.get().getClass().getSimpleName() + " => " + nanosToMillis(medianNanos) + " ms");
  }

  public static void main(String[] args) {
    long start = System.nanoTime();

    AtomicReference<Integer[]> array = new AtomicReference<>();
    printTime(() -> new Integer[SIZE], (a) -> {
      for (int i = 0; i < SIZE; i++) {
        a[i] = Integer.valueOf(i);
      }
      array.set(a);
    }, "'append' " + SIZE + " x " + REPS);

    AtomicReference<Vector<Integer>> vec = new AtomicReference<>();
    printTime(Vector::<Integer>empty, (v) -> {
      Vector<Integer> v1 = v;
      for (int i = 0; i < SIZE; i++) {
        v1 = v1.append(Integer.valueOf(i));
      }
      vec.set(v1);
    }, "append " + SIZE + " x " + REPS);

    AtomicReference<ArrayList<Integer>> list = new AtomicReference<>();
    printTime((Supplier<ArrayList<Integer>>) ArrayList::new, (l) -> {
      for (int i = 0; i < SIZE; i++) {
        l.add(Integer.valueOf(i));
      }
      list.set(l);
    }, "append " + SIZE + " x " + REPS);

    AtomicReference<Int2ObjectOpenHashMap<Integer>> map = new AtomicReference<>();
    printTime((Supplier<Int2ObjectOpenHashMap<Integer>>) Int2ObjectOpenHashMap::new, (m) -> {
      for (int i = 0; i < SIZE; i++) {
        m.put(i, Integer.valueOf(i));
      }
      map.set(m);
    }, "append " + SIZE + " x " + REPS);

    AtomicInteger total = new AtomicInteger(0);

    printTime(array::get, (a) -> {
      for (int i = 0; i < SIZE; i++) {
        int val = a[i].intValue();
        total.addAndGet(val);
      }
    }, "traverse " + SIZE + " x " + REPS);

    printTime(vec::get, (v) -> {
      for (int i = 0; i < SIZE; i++) {
        int val = v.get(i).intValue();
        total.addAndGet(val);
      }
    }, "traverse " + SIZE + " x " + REPS);

    printTime(list::get, (v) -> {
      for (int i = 0; i < SIZE; i++) {
        int val = v.get(i).intValue();
        total.addAndGet(val);
      }
    }, "traverse " + SIZE + " x " + REPS);

    printTime(map::get, (v) -> {
      for (int i = 0; i < SIZE; i++) {
        int val = v.get(i).intValue();
        total.addAndGet(val);
      }
    }, "traverse " + SIZE + " x " + REPS);

    long end = System.nanoTime();

    long totalNanos = end - start;
    double totalSeconds = nanosToSeconds(totalNanos);
    System.out.println("Total: " + totalSeconds + " sec");
  }

  private static double nanosToMillis(long nanos) {
    return new BigDecimal(nanos / 1e6).round(new MathContext(4)).doubleValue();
  }

  private static double nanosToSeconds(long nanos) {
    return new BigDecimal(nanos / 1e9).round(new MathContext(3)).doubleValue();
  }

}

Results (MacBook Pro, 2.6 GHz i5):

'append' 100000 x 10: Integer[] => 7.629 ms
append 100000 x 10: Vector => 226.5 ms
append 100000 x 10: ArrayList => 6.603 ms
append 100000 x 10: Int2ObjectOpenHashMap => 57.33 ms
traverse 100000 x 10: Integer[] => 6.715 ms
traverse 100000 x 10: Vector => 201.9 ms
traverse 100000 x 10: ArrayList => 9.099 ms
traverse 100000 x 10: Int2ObjectOpenHashMap => 36.1 ms
Total: 7.5 sec

'append' 1000000 x 10: Integer[] => 101.3 ms
append 1000000 x 10: Vector => 4343.0 ms
append 1000000 x 10: ArrayList => 157.8 ms
append 1000000 x 10: Int2ObjectOpenHashMap => 808.0 ms
traverse 1000000 x 10: Integer[] => 74.8 ms
traverse 1000000 x 10: Vector => 1849.0 ms
traverse 1000000 x 10: ArrayList => 100.0 ms
traverse 1000000 x 10: Int2ObjectOpenHashMap => 518.8 ms
Total: 90.6 sec

'append' 1000 x 5: Integer[] => 0.3554 ms
append 1000 x 5: Vector => 3.298 ms
append 1000 x 5: ArrayList => 0.4975 ms
append 1000 x 5: Int2ObjectOpenHashMap => 1.779 ms
traverse 1000 x 5: Integer[] => 0.456 ms
traverse 1000 x 5: Vector => 1.573 ms
traverse 1000 x 5: ArrayList => 0.4172 ms
traverse 1000 x 5: Int2ObjectOpenHashMap => 0.4609 ms
'delete' 1000 x 5: Integer[] => 0.1898 ms
delete 1000 x 5: Vector => 289.6 ms
delete 1000 x 5: ArrayList => 0.2413 ms
delete 1000 x 5: Int2ObjectOpenHashMap => 0.8663 ms
Total: 4.38 sec

'append' 5000 x 5: Integer[] => 1.059 ms
append 5000 x 5: Vector => 5.476 ms
append 5000 x 5: ArrayList => 1.187 ms
append 5000 x 5: Int2ObjectOpenHashMap => 2.091 ms
traverse 5000 x 5: Integer[] => 0.4331 ms
traverse 5000 x 5: Vector => 1.539 ms
traverse 5000 x 5: ArrayList => 0.8981 ms
traverse 5000 x 5: Int2ObjectOpenHashMap => 0.7615 ms
'delete' 5000 x 5: Integer[] => 0.2623 ms
delete 5000 x 5: Vector => 10340.0 ms
delete 5000 x 5: ArrayList => 0.2322 ms
delete 5000 x 5: Int2ObjectOpenHashMap => 1.425 ms