Different execution time for HashMap and HashSet based on the order of execution?

Question

I am getting different execution time, if i interchange the HashMap and HashSet. The execution time is always high the one appears first ( either HashMap/ Hashset ). I am not sure about the reason behind this. Any help appreciated

Execution 1 - HashMap first , then HashSet --- Time taken map add: 2071ms, Time taken set add: 794ms

Execution 2 - HashSet first , then HashMap --- Time taken set add: 2147ms, Time taken map add: 781ms

private static Random secureRandom = new SecureRandom();

public static void main(String args[])
{

    int testnumber = 1000000;

    // HashMap
    long starttimemap = System.currentTimeMillis();
    Map<String, String> hashmap = new HashMap<String, String>();
    for (int i = 0; i < testnumber; i++)
    {
        hashmap.put(Long.toHexString(secureRandom.nextLong()), "true");
    }
    long endtimemap = System.currentTimeMillis();
    System.out.println("Time taken map add: " + (endtimemap - starttimemap) + "ms");

    // HashSet
    long starttimeset = System.currentTimeMillis();
    Set<String> hashset = new HashSet<String>();

    for (int i = 0; i < testnumber; i++)
    {
        hashset.add(Long.toHexString(secureRandom.nextLong()));
    }

    long endtimeset = System.currentTimeMillis();
    System.out.println("Time taken set add: " + (endtimeset - starttimeset) + "ms");
}

Answer 1

The reason is the way the JVM works. The JIT compiler needs some time to kick in because it decides which code to compile based on execution count.

So, it's totally natural that the second pass is faster, because the JIT already compiled a lot of Java code to native code.

If you start the program using the -Xint option (which disables the JIT), both runs should be roughly equal in execution time.

Answer 2

One likely reason is that you're not warming up the JIT before performing the benchmarks.

Basically, Java executes bytecode (which is somewhat slower) for a while before figuring out what's used often enough to justify JIT compiling it into native machine code (which is faster). As such, whatever happens first will often be slower.

Run both things a bunch of times before starting the real benchmarks to give it a chance to JIT the relevant code.

Answer 3

You are not getting different execution times, you are getting the same execution times. Regardless of whether you use HashMap or HashSet you get the same time for the first loop and the same time for the second. The difference between the first and second has been explained already, it’s due to the JVM’s optimizations. It’s not surprising that it doesn’t matter whether you use HashMap or HashSet as HashSet uses a HashMap internally. You are executing the same code all the time.