1

I know that Java can be faster than C++ for some programs, but I definitely did not expect Java to beat C++ at sorting 1000000 elements.

Here is my code for Java:

import java.io.*;
import java.util.*;

public class TestProgram {
    public static void main (String[] args) throws IOException{
        int[] arr = new int[1000000];
        for(int i = 0; i < 1000000; ++i){arr[i] = i;}
        
        for(int i = 0; i < 1000000; ++i){ // shuffles elements
            int temp = arr[i], next = Math.random() % 1000000;
            arr[i] = arr[next];
            arr[next] = temp;
        }
        
        double start = System.nanoTime();
        Arrays.sort(arr);
        System.out.println((System.nanoTime() - start)/1000000); // prints number of milliseconds elapsed
    }
}

And this is for C++:

#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

int main(){
    int arr[1000000];
    for(int i = 0; i < 1000000; ++i){arr[i] = i;}
    
    srand(time(nullptr));
    for(int i = 0; i < 1000000; ++i){swap(arr[i], arr[rand() % 1000000]);}
    
    double start = clock();
    sort(arr, arr + 1000000);
    cout << (clock()-start)/(CLOCKS_PER_SEC/1000) << '\n';
    
    return 0;
}

Compiling with -O3 on the C++ program, I get results of around 70 milliseconds. However, the Java program can run in only 27-30 milliseconds, which is quite surprising for me.

Can somebody explain why this happens?

ahskdjfk
  • 919
  • 5
  • 8
  • 3
    Tip: Run the sort function enough times you get a ~20-30s run. Milliseconds is just noise statistically speaking. You may be measuring the jitter in the clock function. – tadman Sep 02 '20 at 02:45
  • How are you running the C++ code? Looks like someone else had this [observation](https://stackoverflow.com/questions/6428444/java-seems-to-be-executing-bare-bones-algorithms-faster-than-c-why) but they were (among other things) running it through a debugger. I've not coded C++ in many years, so I can't say how the IDE might have changed since 2011. Of course, maybe Java is that much better over the past 9 years, but I am somewhat dubious. – Gryphon Sep 02 '20 at 02:53
  • 1
    Without `-O3` or equivalent this benchmark is meaningless. `-O2` is "sort of kind of optimized-ish". – tadman Sep 02 '20 at 03:02
  • Alright, I compiled the C++ program with `-O3` and got between around 70 milliseconds as a result. – ahskdjfk Sep 02 '20 at 03:05
  • 3
    rand() may only be producing a value between 0 and 32767, so most of the array will still be sorted, which is bad for quicksort to try and sort. Also the Java array will still be sorted (Math.random produces a number between 0 and 1), and Java uses Timsort which is good on already sorted data. – CraigR Sep 02 '20 at 03:07
  • Java doesn't use timsort. Java uses dual pivot quicksort. – John Sep 02 '20 at 03:28
  • Arrays class does use a variety of sorts (including TimSort), but in this case (primitives) it will use the dual pivot quicksort. – Gryphon Sep 02 '20 at 03:41
  • To add to @CraigR's comment, the Java code does not even compile because the result of `Math.random() % 1000000` is a `double`, not an `int` (and the compiler complains about this). Additionally both shuffling algorithms are [flawed](https://blog.codinghorror.com/the-danger-of-naivete/), but since both are flawed in the same way this likely has no effect. – Marcono1234 Sep 02 '20 at 10:40
  • 1
    I had a similar case where java was sorting twice as fast, i then compiled the C++ code with the -O3 flag as @tadman suggested and the C++ code finished ~3 sec faster. – tf3 Nov 25 '20 at 13:36

0 Answers0