Comparing sort Java with c++

main.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>
#include <cmath>
#include <limits>
#include "instrumented.h"

double log2(double x) {
    return std::log(x) / std::log(2.0);
}

void bench() {
    std::mt19937 rng(std::random_device{}());
    std::uniform_int_distribution<int> dist(std::numeric_limits<int>::min(), std::numeric_limits<int>::max());

    const long long minMeasureTime = 1'000'000'000; // 1 sekunda w ns
    std::vector<double> javaResults = {
        0.006228,0.013404,0.038669,
        0.080068,0.173844,0.460390,
        0.991204,2.102784,5.768869,
        12.496220,26.331921,75.622217,
    };

    std::vector<int> sizes = {
        1'000, 2'000, 5'000,
        10'000, 20'000, 50'000,
        100'000, 200'000, 500'000,
        1'000'000, 2'000'000, 5'000'000
    };

    long long sum = 0;
    for (int n = 0; n < sizes.size(); ++n) {
        int size = sizes[n];
        std::cout << "\nsize " << size << "\n";

        long long best = std::numeric_limits<long long>::max();
        long long totalTime = 0;
        int nTrials = 0;

        do {
            std::vector<int> numbers(size);
            for (int& num : numbers) {
                num = dist(rng);
            }

            auto start = std::chrono::high_resolution_clock::now();
            std::sort(numbers.begin(), numbers.end());
            auto end = std::chrono::high_resolution_clock::now();

            auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
            if (elapsed < best) best = elapsed;
            totalTime += elapsed;

            for (int i = 0; i < size; ++i) {
                sum += i + numbers[i];
            }

            ++nTrials;
        } while (totalTime < minMeasureTime || nTrials < 4);

        double avg = static_cast<double>(totalTime) / nTrials;
        std::cout << "avg/best = " << avg / best << "\n";
        std::cout << "vector sort time " << best / 1e6 << " ms\n";
        std::cout << "vector sort time/size/log2(size) = "
                  << best / (size * log2(size)) << " ns\n";
        std::cout << "cpp/java = " << (best/1e6)/javaResults[n] << "\n";
    }

    std::cout << "\n\n" << (sum % 2) << "\n";
}

void instrumentedSort() {
    const int size = 5'000'000;
    std::mt19937 rng(std::random_device{}());
    std::uniform_int_distribution<int> dist(std::numeric_limits<int>::min(), std::numeric_limits<int>::max());
    std::vector<Instrumented> v(size);
    for (auto& num : v) {
        num.value = dist(rng);
    }

    std::sort(v.begin(), v.end());

    std::cout << "Comparisons: " << (double)Counters::comparisons/size << "\n";
    std::cout << "Moves:       " << (double)Counters::moves/size << "\n";
}

int main() {
    bench();
    return 0;
}

Main.java

import java.util.*;
import java.util.stream.Collectors;

class CounterComparator implements Comparator<Integer> {
    public long comparisons = 0;

    @Override
    public int compare(Integer a, Integer b) {
        comparisons++;
        return Integer.compare(a, b);
    }
}

public class Main {
    public static double log2(double x) {
        return Math.log(x) / Math.log(2);
    }
    
    public static void bench() {
        Random rand = new Random();
        ArrayList<Double> results = new ArrayList<>();
        int minMeasureTime = 1_000_000_000;
        int[] sizes = {1_000, 2_000, 5_000,
                10_000, 20_000, 50_000,
                100_000, 200_000, 500_000,
                1_000_000, 2_000_000, 5_000_000};
        long sum1 = 0, sum2 = 0;
        for (int size : sizes) {
            System.out.printf("%nsize %d%n", size);
            long best1 = Long.MAX_VALUE;
            long best1a = Long.MAX_VALUE;
            long best2 = Long.MAX_VALUE;
            long measureTime = 0;
            int nTrials = 0;
            do {
                int[] numbers = new int[size];
                for (int i = 0; i < size; i++) {
                    numbers[i] = rand.nextInt();
                }
                Integer[] boxed = Arrays.stream(numbers)
                        .boxed()
                        .toArray(Integer[]::new);
                ArrayList<Integer> list = new ArrayList<>(
                        Arrays.stream(numbers).boxed().toList()
                );
                long startTime1 = System.nanoTime();
                Arrays.sort(numbers);
                long endTime1 = System.nanoTime();
                long sortTime1 = endTime1 - startTime1;
                if (sortTime1 < best1) best1 = sortTime1;
                measureTime += sortTime1;

                long startTime1a = System.nanoTime();
                Arrays.sort(boxed);
                long endTime1a = System.nanoTime();
                long sortTime1a = endTime1a - startTime1a;
                if (sortTime1a < best1a) best1a = sortTime1a;
                measureTime += sortTime1a;

                long startTime2 = System.nanoTime();
                Collections.sort(list);
                long endTime2 = System.nanoTime();
                long sortTime2 = endTime2 - startTime2;
                if (sortTime2 < best2) best2 = sortTime2;
                measureTime += sortTime2;
                for (int i = 0; i < size; i++) {
                    sum1 += (long) i * numbers[i];
                    sum2 += (long) i * list.get(i);
                }
                nTrials++;
            } while (measureTime < minMeasureTime || nTrials < 4);
            System.out.printf("array sort time %f ms%n", (double) best1 / 1e6);
            results.add((double) best1 / 1e6);
            System.out.printf("array sort time/size/log2(size) %f ns%n", (double) best1 / size / log2(size));
            System.out.printf("boxed sort time %f times worse%n", (double) best1a / best1);
            System.out.printf("list sort time %f times worse%n", (double) best2 / best1);
        }
        System.out.printf("%n%n%d==%d%n%n", sum1, sum2);
        System.out.println("std::vector<double> javaResults = {");
        for (int n = 0; n<results.size(); n++) {
            if (n%3==0) System.out.print("    ");
            double result = results.get(n);
            System.out.printf("%f,", result);
            if (n%3==2) System.out.println();
        }
        System.out.println("};");

    }

    public static void instrumentedSort() {
        List<Integer> list = new ArrayList<>();
        int size = 5_000_000;
        Random rand = new Random();
        for (int i = 0; i < size; i++) {
            list.add(rand.nextInt());
        }

        CounterComparator cmp = new CounterComparator();
        list.sort(cmp);

        System.out.println("Comparisons: " + (double)cmp.comparisons/size);
    }

    public static void main(String[] args) {
        bench();
    }
}

output_clang.out

/home/andrzej/CLionProjects/sort/cmake-build-release/sort

size 1000
avg/best = 1.15886
vector sort time 0.033327 ms
vector sort time/size/log2(size) = 3.34414 ns
cpp/java = 5.35116

size 2000
avg/best = 1.08209
vector sort time 0.074122 ms
vector sort time/size/log2(size) = 3.37969 ns
cpp/java = 5.52984

size 5000
avg/best = 1.06741
vector sort time 0.208089 ms
vector sort time/size/log2(size) = 3.38694 ns
cpp/java = 5.38129

size 10000
avg/best = 1.05818
vector sort time 0.451315 ms
vector sort time/size/log2(size) = 3.39648 ns
cpp/java = 5.63665

size 20000
avg/best = 1.04942
vector sort time 0.971947 ms
vector sort time/size/log2(size) = 3.40134 ns
cpp/java = 5.59091

size 50000
avg/best = 1.05028
vector sort time 2.63349 ms
vector sort time/size/log2(size) = 3.37418 ns
cpp/java = 5.72012

size 100000
avg/best = 1.03115
vector sort time 5.6823 ms
vector sort time/size/log2(size) = 3.42108 ns
cpp/java = 5.73272

size 200000
avg/best = 1.02599
vector sort time 12.0461 ms
vector sort time/size/log2(size) = 3.42033 ns
cpp/java = 5.72866

size 500000
avg/best = 1.01651
vector sort time 32.5397 ms
vector sort time/size/log2(size) = 3.43761 ns
cpp/java = 5.64057

size 1000000
avg/best = 1.01745
vector sort time 68.5338 ms
vector sort time/size/log2(size) = 3.43845 ns
cpp/java = 5.48436

size 2000000
avg/best = 1.01444
vector sort time 143.929 ms
vector sort time/size/log2(size) = 3.43809 ns
cpp/java = 5.46597

size 5000000
avg/best = 1.01038
vector sort time 385.187 ms
vector sort time/size/log2(size) = 3.46181 ns
cpp/java = 5.09357

output_gcc.out

/home/andrzej/CLionProjects/sort/cmake-build-release/sort

size 1000
avg/best = 1.19691
vector sort time 0.035248 ms
vector sort time/size/log2(size) = 3.5369 ns
cpp/java = 5.6596

size 2000
avg/best = 1.10845
vector sort time 0.077661 ms
vector sort time/size/log2(size) = 3.54106 ns
cpp/java = 5.79387

size 5000
avg/best = 1.0838
vector sort time 0.216494 ms
vector sort time/size/log2(size) = 3.52375 ns
cpp/java = 5.59864

size 10000
avg/best = 1.05856
vector sort time 0.469807 ms
vector sort time/size/log2(size) = 3.53565 ns
cpp/java = 5.8676

size 20000
avg/best = 1.04441
vector sort time 1.01574 ms
vector sort time/size/log2(size) = 3.55458 ns
cpp/java = 5.8428

size 50000
avg/best = 1.05035
vector sort time 2.75506 ms
vector sort time/size/log2(size) = 3.52995 ns
cpp/java = 5.98419

size 100000
avg/best = 1.03828
vector sort time 5.83131 ms
vector sort time/size/log2(size) = 3.5108 ns
cpp/java = 5.88306

size 200000
avg/best = 1.0233
vector sort time 12.4982 ms
vector sort time/size/log2(size) = 3.54868 ns
cpp/java = 5.94364

size 500000
avg/best = 1.02808
vector sort time 33.3995 ms
vector sort time/size/log2(size) = 3.52844 ns
cpp/java = 5.78961

size 1000000
avg/best = 1.01708
vector sort time 70.9006 ms
vector sort time/size/log2(size) = 3.5572 ns
cpp/java = 5.67377

size 2000000
avg/best = 1.01057
vector sort time 149.871 ms
vector sort time/size/log2(size) = 3.58003 ns
cpp/java = 5.69163

size 5000000
avg/best = 1.00991
vector sort time 398.634 ms
vector sort time/size/log2(size) = 3.58267 ns
cpp/java = 5.27139

output_Java.out

size 1000
array sort time 0.006228 ms
array sort time/size/log2(size) 0.624938 ns
list sort time 17.749839 times worse

size 2000
array sort time 0.013404 ms
array sort time/size/log2(size) 0.611174 ns
list sort time 17.874217 times worse

size 5000
array sort time 0.038669 ms
array sort time/size/log2(size) 0.629393 ns
list sort time 16.961597 times worse

size 10000
array sort time 0.080068 ms
array sort time/size/log2(size) 0.602572 ns
list sort time 17.727906 times worse

size 20000
array sort time 0.173844 ms
array sort time/size/log2(size) 0.608369 ns
list sort time 17.922569 times worse

size 50000
array sort time 0.460390 ms
array sort time/size/log2(size) 0.589879 ns
list sort time 18.955961 times worse

size 100000
array sort time 0.991204 ms
array sort time/size/log2(size) 0.596764 ns
list sort time 19.279222 times worse

size 200000
array sort time 2.102784 ms
array sort time/size/log2(size) 0.597055 ns
list sort time 20.321212 times worse

size 500000
array sort time 5.768869 ms
array sort time/size/log2(size) 0.609444 ns
list sort time 23.377127 times worse

size 1000000
array sort time 12.496220 ms
array sort time/size/log2(size) 0.626956 ns
list sort time 28.939637 times worse

size 2000000
array sort time 26.331921 ms
array sort time/size/log2(size) 0.629000 ns
list sort time 32.180012 times worse

size 5000000
array sort time 75.622217 ms
array sort time/size/log2(size) 0.679643 ns
list sort time 34.303462 times worse


-5970757083185248406==-5970757083185248406

std::vector<double> javaResults = {
    0.006228,0.013404,0.038669,
    0.080068,0.173844,0.460390,
    0.991204,2.102784,5.768869,
    12.496220,26.331921,75.622217,
};