Почему Java's Arrays.sort (int []) в 5 × быстрее, чем c ++ std :: sort (vector )? ⇐ C++

[Anonymous]

Я использую эталон для сравнения производительности сортировки между Java и C ++.
Удивительно, что java's Arrays.sort (int []) более чем на 5 × быстрее, чем C ++ 'S std :: sort (std :: vector) -даже при составлении в режиме выпуска с -O3. более 30 × быстрее, чем сборы. СПОРТ (СПИСОК) В одном и том же процессе JVM, одни и те же данные (хотя используются целочисленные вместо INT, но .. 30x?), То же размер.
Это показывает огромный разрыв в производительности между примитивной сортировкой массива и на основе объектов. Свеже сгенерированный int []
[*] java также тестирует сборы. Список (список), созданный с того же входа
[*] C ++ использует std :: sort (std :: vector) с MT19937, сгенерированным входом
Все тесты, пока не будут выполнены все измеренное время, не будет выдвинуть второе время. /> c ++ Скомпилирован с: < /p>
set(CMAKE_CXX_STANDARD 20)
target_compile_options(sort PRIVATE $)
(though CMake’s Release config already applies -O3)
< /code>
одинаковые результаты как в GCC, так и в Clang Builds < /p>
включает в себя: < /p>
Main.java (Java benchmark for int[] and List)
main.cpp (C++ benchmark)
Output from Java, GCC, and Clang runs
< /code>
Мои вопросы:
Есть ли что-то не так в том, как я измеряю время или использую std :: sort () в c ++ или java?
-это массив Java (int []) просто так оптимизирован? /> хотел бы ваши мысли! < /p>
import java.util.*;
import java.util.stream.Collectors;

class CounterComparator implements Comparator {
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 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 = rand.nextInt();
}
Integer[] boxed = Arrays.stream(numbers)
.boxed()
.toArray(Integer[]::new);
ArrayList 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;
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 javaResults = {");
for (int n = 0; n
#include
#include
#include
#include
#include
#include
#include
#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 dist(std::numeric_limits::min(), std::numeric_limits::max());

const long long minMeasureTime = 1'000'000'000; // 1 sekunda w ns
std::vector 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 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

Подробнее здесь: https://stackoverflow.com/questions/796 ... tvectorint