1

I made a serial MergeSort and a parallel MergeSort. Both divide the input list in a left and right half and call sort on those. The source code is almost identical; the difference between them is that parallel MergeSort has an if-statement that checks if it needs to make threads or just calls sort like the serial version. Codesnippet:

    if (threadDepth < maxThreadDepth) {
        // make threads that call sort
    } else {
        sort(left, threadDepth + 1, maxThreadDepth);
        sort(right, threadDepth + 1, maxThreadDepth);
    }

When I use maxThreadDepth = 0 the if-statement is always false and the parallel works the same as the serial version.

I calculate the time both algorithms take and see something very strange. When maxThreadDepth = 0 the parallel version is faster than the serial version! I expected it to be slower, since it has an extra if-statement to process. Even when the JVM optimises this if-statement (it knows it is always false), it should never be faster!

I ran both algorithms 1000 times and kept track of the time they took like this:

List<Long> times = new ArrayList<>();
for(int i = 0, i < 1000, i++){
    long start = System.nanoTime();
    serial.MergeSort.sort(...); // or parallel.MergeSort.sort(...)
    long end = System.nanoTime();
    times.add(end - start);
}

I discarded the first 900 times and calculated the average time it took both algorithms to run. Does someone have any idea why the no-extra-threaded parallel version is faster than the serial? As input, I used a list of integers with various sizes (1000, 10000, 100000) and all of them had this suprising behaviour.

J. Kamans
  • 575
  • 5
  • 17
  • Please start by making sure your benchmark is accurate. i.e. do not roll your own benchmark. Use a framework like [jmh](http://tutorials.jenkov.com/java-performance/jmh.html). Almost always, when people post an unintuitive benchmark result here, it's because they simply didn't measure it correctly. – Michael Jun 14 '19 at 15:56

0 Answers0