Java Collection- Speedup between ArrayList and Vector

Question

From some resources, I had come to know that under Java collection, ArrayList is faster than Vector. To check that, I was trying with a small program in which one method adds some data to an ArrayList and then retrieve those and the another method adds and retrieves same data to and from a Vector. Now the main() method calls two of them under two different time calculation process which calculates the execution time of those method separately. In the result, I am getting the execution time for ArrayList is 18385831 ns and for Vector is 2190242 ns. My project lead also said that the ArrayList is faster than Vector. But the result of my program is saying something different. Can anyone please explain me the correct thing with its reason? And also the reason of this result if ArrayList is really faster than the Vector.

This is my source code:

import java.util.*;

public class TestArraylist {

    void Arraylistpart() {
        ArrayList<Object> a1 = new ArrayList<Object>();
        ArrayList<Object> a2 = new ArrayList<Object>();
        a2 = a1;

        a1.add(1);
        a1.add('c');
        a1.add("gh");
        a1.add(2);
        a1.set(2, "ab");
        int count = 0;
        System.out.println(a1);
        try {
            for (Object i : a1) {
                a2.set(count, i.toString());
                count = count + 1;
            }
            a2.sort(null);
            System.out.println(a2);
        } catch (ClassCastException e) {
            System.err.println("Exception occurs");
        }
    }

    void vectorpart() {
        Vector<Object> v1 = new Vector<Object>();
        Vector<Object> v2 = new Vector<Object>();
        v2 = v1;
        v1.add(1);
        v1.add('c');
        v1.add("ab");
        v1.add(2);
        int count1 = 0;
        System.out.println(v1);
        try {
            for (Object i : v1) {
                v2.setElementAt(i.toString(), count1);
                count1 = count1 + 1;
            }
            v2.sort(null);
            System.out.println(v2);
        } catch (ClassCastException e) {
            System.err.println("Exception occurs");
        }
    }

    public static void main(String[] args) {
        TestArraylist objct = new TestArraylist();
        System.out.println("Arraylist program");
        long startmili = System.currentTimeMillis();
        long starttime = System.nanoTime();
        objct.Arraylistpart();
        long endtime = System.nanoTime();
        long endmili = System.currentTimeMillis();
        long totaltime = endtime - starttime;
        long totaltimemili = endmili - startmili;
        System.out.println(totaltime);
        System.out.println("Time in mili is: " + totaltimemili);

        System.out.println("\nVector program");
        long startmili1 = System.currentTimeMillis();
        long starttime1 = System.nanoTime();
        objct.vectorpart();
        long endtime1 = System.nanoTime();
        long endmili1 = System.currentTimeMillis();
        long totaltime1 = endtime1 - starttime1;
        long totaltimemili1 = endmili1 - startmili1;
        System.out.println(totaltime1);
        System.out.println("Time in mili is: " + totaltimemili1);
    }
}

Answer 1

Your benchmark is wrong. First, you've measured not only the time of array/vector-based operations, but also time of printing which could be several magnitudes slower than everything else. Second, you did no warmup, so most of your code is likely to be executed by interpreter, not JIT-compiled. Third, you launch two tests in the same JVM, putting them into unequal conditions: during the first test execution JVM does more warm-up steps (e.g. JIT compilation), so the first test is handicapped from the very start. Let's try to write somewhat equivalent using the JMH:

import org.openjdk.jmh.annotations.*;

import java.util.*;
import java.util.concurrent.TimeUnit;

@Warmup(iterations = 20, time = 500, timeUnit = TimeUnit.MILLISECONDS)
@Measurement(iterations = 20, time = 500, timeUnit = TimeUnit.MILLISECONDS)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@Fork(1)
@State(Scope.Benchmark)
public class TestArraylist {

    @Benchmark
    public String Arraylistpart() {
        ArrayList<Object> a1 = new ArrayList<>();
        ArrayList<Object> a2 = new ArrayList<>();
        a2 = a1;

        a1.add(1);
        a1.add('c');
        a1.add("gh");
        a1.add(2);
        a1.set(2, "ab");
        int count = 0;
        for (Object i : a1) {
            a2.set(count, i.toString());
            count = count + 1;
        }
        a2.sort(null);
        return a1.toString()+a2.toString();
    }

    @Benchmark
    public String vectorpart() {
        Vector<Object> v1 = new Vector<>();
        Vector<Object> v2 = new Vector<>();
        v2 = v1;
        v1.add(1);
        v1.add('c');
        v1.add("ab");
        v1.add(2);
        int count1 = 0;
        for (Object i : v1) {
            v2.setElementAt(i.toString(), count1);
            count1 = count1 + 1;
        }
        v2.sort(null);
        return v1.toString()+v2.toString();
    }
}

I returned a1.toString()+a2.toString() instead of printing to preserve the .toString() calls (which were done in your test inside System.out.println).

The summary result is the following:

Benchmark                    Mode  Cnt  Score   Error  Units
TestArraylist.Arraylistpart  avgt   20  0,382 ± 0,003  us/op
TestArraylist.vectorpart     avgt   20  0,421 ± 0,002  us/op

See, your tests actually performed much, much faster. Only 382 nanoseconds and 421 nanoseconds. Vector is indeed somewhat slower, due to additional synchronization. But seems that C2 JIT compiler did a good job removing some unnecessary synchronization sections, so the time difference is not very big. It's also interesting to check the per-iteration stats. For ArrayList:

# Warmup Iteration   1: 0,544 us/op
# Warmup Iteration   2: 0,471 us/op
# Warmup Iteration   3: 0,383 us/op
# Warmup Iteration   4: 0,377 us/op
# Warmup Iteration   5: 0,377 us/op
# Warmup Iteration   6: 0,373 us/op
...
Iteration  14: 0,374 us/op
Iteration  15: 0,376 us/op
Iteration  16: 0,381 us/op
Iteration  17: 0,376 us/op
Iteration  18: 0,379 us/op
Iteration  19: 0,383 us/op
Iteration  20: 0,385 us/op

For Vector:

# Warmup Iteration   1: 0,889 us/op
# Warmup Iteration   2: 0,630 us/op
# Warmup Iteration   3: 0,689 us/op
# Warmup Iteration   4: 0,662 us/op
# Warmup Iteration   5: 0,671 us/op
# Warmup Iteration   6: 0,673 us/op
# Warmup Iteration   7: 0,669 us/op
# Warmup Iteration   8: 0,657 us/op
# Warmup Iteration   9: 0,427 us/op
# Warmup Iteration  10: 0,421 us/op
# Warmup Iteration  11: 0,421 us/op
...
Iteration  17: 0,423 us/op
Iteration  18: 0,420 us/op
Iteration  19: 0,422 us/op
Iteration  20: 0,419 us/op

As you can see, ArrayList reaches the full speed on iteration#3, while Vector reaches it on iteration#9.

Answer 2

There are multiple things wrong with your benchmark which makes it look like Vector is faster than ArrayList. To see that it is broken, just execute the Vector benchmkar before you execute the ArrayList benchmark and suddenly you get the inverse results.

Here a list of things you have to keep in mind when benchmarking Java code:

Warm up the code - never benchmark cold code: The JIT optimizer does some pretty amazing things at runtime to optimize the Java code. But it does that only after the code got executed multiple times. The performance difference can be very significant. So execute your benchmark methods a few times without measuring the time to allow the JIT compiler to do its work. It also makes sure that all classes you need have been loaded and that this time is not counted towards the runtime. Your benchmark does not do that.

Make sure the benchmark runs long enough: In your benchmark, just 5 objects get added to the Vector/ArrayList. This code executes in about 1ms which is too short to get any usefull results. If your benchmark does not run long enough, "random" effects (i.e. scheduling of threads) the will influence the results too much. Try adding a few million elements.

Make sure you consume the result of your benchmark code: Imagine that you benchmark how long it takes to sum up 1 million values but you do not do anything with the result. The JIT optimizer might figure out that you do not need it and throw away the entire computation which renders the benchmark useless. Make sure you consume the result e.g. by printing it.

There are some more things to consider if you want to get really serious about it, but these are maybe the most important ones.

You might want to take a look at some frameworks that help with benchmarking like JMH.