有什么理由 Java 在使用手动插入/选择/基数排序对 int 数组进行排序时比 C 执行得更快？
Is there any reason why Java would be performing faster than C for sorting int arrays with manual Insertion / Selection / Radix sorts?
平台：OpenBSD，编译器：gcc、javac（OpenJDK 版本 17）
我已经用各种语言做了一些排序基准，我对 Java 程序优于 C 程序的性能感到相当惊讶。
我用两种语言编写了完全相同的排序算法，Java 程序完成速度几乎快两倍，除了 Java 之外，所有其他语言都比 C 实现慢。
基准测试涉及运行对随机数字数组进行排序算法一定次数。
我正在用 -O3 和 -Ofast 编译程序，所以我不能再应用任何编译器优化。
可以找到确切的代码 here，但这里是它的摘录：
Java:
public static void benchmark(SortingFunction func, int arraySize, int numTimes, String name, BufferedOutputStream bo) throws IOException {
int[][] arrs = new int[numTimes][arraySize];
for (int i = 0; i < numTimes; i ++) {
arrs[i] = genRandArray(arraySize);
}
long start = System.nanoTime();
for (int i = 0; i < numTimes; i ++) {
func.sort(arrs[i]);
}
long end = System.nanoTime();
double time = (double)(end - start) / 1e9;
System.out.println("It took " + time + " seconds to do " + name + " sort " +
numTimes + " times on arrays of size " + arraySize
);
String out = name+","+numTimes+","+arraySize+","+time;
for (char c : out.toCharArray()) {
bo.write(c);
}
bo.write('\n');
}
public static void insertionSort(int[] array) {
for (int i = 1; i < array.length; i ++) {
int temp = array[i];
int j;
for (j = i - 1; j >= 0 && array[j] > temp; j --) {
array[j+1] = array[j];
}
array[j+1] = temp;
}
}
C:
void benchmark(void (*f)(int *, int), int arr_size, int num_times, char *name,
FILE *fp) {
int *arrs[num_times];
struct timeval start, end;
double t;
for (int i = 0; i < num_times; i++) {
arrs[i] = gen_rand_arr(arr_size);
}
gettimeofday(&start, NULL);
for (int i = 0; i < num_times; i++) {
f(arrs[i], arr_size);
}
gettimeofday(&end, NULL);
for (int i = 0; i < num_times; i++) {
free(arrs[i]);
}
t = ((double)(end.tv_sec * 1000000 + end.tv_usec -
(start.tv_sec * 1000000 + start.tv_usec))) /
1000000;
printf("It took %f seconds to do %s sort %d times on arrays of size %d\n", t,
name, num_times, arr_size);
if (fp != NULL) {
fprintf(fp, "%s,%d,%d,%f\n", name, num_times, arr_size, t);
}
}
void insertion_sort(int *arr, int arr_size) {
for (int i = 1; i < arr_size; i++) {
int temp = arr[i];
int j;
for (j = i - 1; j >= 0 && *(arr + j) > temp; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = temp;
}
return;
}
Java 是否进行了一些优化以提高 运行 的速度，从而以某种方式改变了算法？这是怎么回事？
如有任何解释，我们将不胜感激。
这里有 table 个可能有助于解释差异的结果：
Java:
name
rep
size
time
Insertion
10000
1200
1.033
Insertion
10000
5000
15.677
Insertion
10000
12000
88.190
Selection
10000
1200
3.118
Selection
10000
5000
48.377
Selection
10000
12000
268.608
Radix
10000
1200
0.385
Radix
10000
5000
1.491
Radix
10000
12000
3.563
Bogo
1
11
1.330
Bogo
1
12
0.572
Bogo
1
13
122.777
C:
name
rep
size
time
Insertion
10000
1200
1.766
Insertion
10000
5000
26.106
Insertion
10000
12000
140.582
Selection
10000
1200
4.011
Selection
10000
5000
60.442
Selection
10000
12000
340.608
Radix
10000
1200
0.430
Radix
10000
5000
1.788
Radix
10000
12000
4.295
Bogo
1
11
1.378
Bogo
1
12
2.296
Bogo
1
13
1586.73
编辑：
我修改了基准函数来预先生成数组，在Java中它溢出了堆，在C中它使它更快（大约25%，但Java仍然更快).
fwiw 我还改变了我在 C 中索引事物的方式，从 *(arr + i) 到 arr[i]。
这是 Java 和 C:
中随机数组生成器的实现
Java:
public static int[] genRandArray(int arraySize) {
int[] ret = new int[arraySize];
Random rand = new Random();
for (int i = 0; i < ret.length; i ++) {
ret[i] = rand.nextInt(100);
}
return ret;
}
C:
int *gen_rand_arr(int arr_size) {
int *arr;
if ((arr = malloc(arr_size * sizeof(int))) == NULL) {
exit(1);
}
for (int i = 0; i < arr_size; i++) {
arr[i] = arc4random_uniform(100);
}
return arr;
}
TL;DR
一般来说，像这样的简短片段不是比较语言的公平方式。有很多因素在起作用。当您用 C 而不是 Java 编写代码时，代码不会自动变快。如果是这样的话，你可以写一个 Java2C 转换器。编译器标志很重要，还有程序员的技能。
更长的解释
我不能肯定地说，但是这个：
for (j = i - 1; j >= 0 && arr[j] > temp; j--) {
arr[j + 1] = arr[j];
}
缓存不是很友好，因为你是在向后遍历列表。我会尝试更改循环，以便外循环而不是内循环进行向后遍历。
但我要说你的问题存在根本性的缺陷。代码不会因为您将代码从 Java 重写为 C 而自动获得性能提升。同样，C 程序不会因为您将它们重写为汇编而自动变得更快。可以说 C 允许 你写出比 Java 更快的程序，但最终，结果取决于程序员。
可以加速 Java 程序的一件事是 JIT 编译器，它可以在运行时针对特定条件进行统计以优化代码。虽然可以使 C 编译器针对 typical 工作负载进行优化，但它无法针对 current 工作负载进行优化。
你说你使用了 -O3 作为 C 代码。但是你用的是什么目标？您是针对您的机器还是一般机器进行了优化？ JIT 编译器知道要优化的目标。尝试使用 -march=native
您确定 int 使用相同的尺码吗？它在 Java 中是 32 位，但在 C 中可能是 64 位。如果您改用 int32_t，它可能会加速 C 代码。但它也可能会减慢速度。 （这不太可能是原因，但我只是想提一下它的可能性）
当涉及到非常低级的东西时，C 通常会大放异彩。
如果我们查看您的 Java 代码：
for (int i = 1; i < array.length; i ++) {
int temp = array[i];
在这个例子中，聪明的编译器可以很容易地看出array永远不会被越界访问。但是，如果我们有类似的东西怎么办：
while(<condition>) {
int temp = array[foo()];
哪里不能事先确定array不会出界？然后 Java 被迫进行不断的边界检查以便能够抛出异常。代码将被翻译成类似：
while(<condition>) {
int i = foo();
if(i >= array.length)
throw exception;
int temp = array[i];
这提供了安全性，但会降低性能。 C 只会允许您越界访问，这样速度更快，但可能会导致难以发现的错误。
我发现了一个包含更多信息的好问题：Why would it ever be possible for Java to be faster than C++?
除此之外，我可以看到您在基准测试中包括了数据生成。那很糟糕。在启动定时器之前生成数据。像这样：
int *arrs[num_times];
for (int i = 0; i < num_times; i++)
arrs[i] = gen_rand_arr(arr_size);
gettimeofday(&start, NULL);
for (int i = 0; i < num_times; i++)
f(arrs[i], arr_size);
gettimeofday(&end, NULL);
平台：OpenBSD，编译器：gcc、javac（OpenJDK 版本 17）
我已经用各种语言做了一些排序基准，我对 Java 程序优于 C 程序的性能感到相当惊讶。
我用两种语言编写了完全相同的排序算法，Java 程序完成速度几乎快两倍，除了 Java 之外，所有其他语言都比 C 实现慢。
基准测试涉及运行对随机数字数组进行排序算法一定次数。
我正在用 -O3 和 -Ofast 编译程序，所以我不能再应用任何编译器优化。
可以找到确切的代码 here，但这里是它的摘录：
Java:
public static void benchmark(SortingFunction func, int arraySize, int numTimes, String name, BufferedOutputStream bo) throws IOException {
int[][] arrs = new int[numTimes][arraySize];
for (int i = 0; i < numTimes; i ++) {
arrs[i] = genRandArray(arraySize);
}
long start = System.nanoTime();
for (int i = 0; i < numTimes; i ++) {
func.sort(arrs[i]);
}
long end = System.nanoTime();
double time = (double)(end - start) / 1e9;
System.out.println("It took " + time + " seconds to do " + name + " sort " +
numTimes + " times on arrays of size " + arraySize
);
String out = name+","+numTimes+","+arraySize+","+time;
for (char c : out.toCharArray()) {
bo.write(c);
}
bo.write('\n');
}
public static void insertionSort(int[] array) {
for (int i = 1; i < array.length; i ++) {
int temp = array[i];
int j;
for (j = i - 1; j >= 0 && array[j] > temp; j --) {
array[j+1] = array[j];
}
array[j+1] = temp;
}
}
C:
void benchmark(void (*f)(int *, int), int arr_size, int num_times, char *name,
FILE *fp) {
int *arrs[num_times];
struct timeval start, end;
double t;
for (int i = 0; i < num_times; i++) {
arrs[i] = gen_rand_arr(arr_size);
}
gettimeofday(&start, NULL);
for (int i = 0; i < num_times; i++) {
f(arrs[i], arr_size);
}
gettimeofday(&end, NULL);
for (int i = 0; i < num_times; i++) {
free(arrs[i]);
}
t = ((double)(end.tv_sec * 1000000 + end.tv_usec -
(start.tv_sec * 1000000 + start.tv_usec))) /
1000000;
printf("It took %f seconds to do %s sort %d times on arrays of size %d\n", t,
name, num_times, arr_size);
if (fp != NULL) {
fprintf(fp, "%s,%d,%d,%f\n", name, num_times, arr_size, t);
}
}
void insertion_sort(int *arr, int arr_size) {
for (int i = 1; i < arr_size; i++) {
int temp = arr[i];
int j;
for (j = i - 1; j >= 0 && *(arr + j) > temp; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = temp;
}
return;
}
Java 是否进行了一些优化以提高 运行 的速度，从而以某种方式改变了算法？这是怎么回事？
如有任何解释，我们将不胜感激。
这里有 table 个可能有助于解释差异的结果：
Java:
| name | rep | size | time |
|---|---|---|---|
| Insertion | 10000 | 1200 | 1.033 |
| Insertion | 10000 | 5000 | 15.677 |
| Insertion | 10000 | 12000 | 88.190 |
| Selection | 10000 | 1200 | 3.118 |
| Selection | 10000 | 5000 | 48.377 |
| Selection | 10000 | 12000 | 268.608 |
| Radix | 10000 | 1200 | 0.385 |
| Radix | 10000 | 5000 | 1.491 |
| Radix | 10000 | 12000 | 3.563 |
| Bogo | 1 | 11 | 1.330 |
| Bogo | 1 | 12 | 0.572 |
| Bogo | 1 | 13 | 122.777 |
C:
| name | rep | size | time |
|---|---|---|---|
| Insertion | 10000 | 1200 | 1.766 |
| Insertion | 10000 | 5000 | 26.106 |
| Insertion | 10000 | 12000 | 140.582 |
| Selection | 10000 | 1200 | 4.011 |
| Selection | 10000 | 5000 | 60.442 |
| Selection | 10000 | 12000 | 340.608 |
| Radix | 10000 | 1200 | 0.430 |
| Radix | 10000 | 5000 | 1.788 |
| Radix | 10000 | 12000 | 4.295 |
| Bogo | 1 | 11 | 1.378 |
| Bogo | 1 | 12 | 2.296 |
| Bogo | 1 | 13 | 1586.73 |
编辑：
我修改了基准函数来预先生成数组，在Java中它溢出了堆，在C中它使它更快（大约25%，但Java仍然更快).
fwiw 我还改变了我在 C 中索引事物的方式，从 *(arr + i) 到 arr[i]。
这是 Java 和 C:
中随机数组生成器的实现Java:
public static int[] genRandArray(int arraySize) {
int[] ret = new int[arraySize];
Random rand = new Random();
for (int i = 0; i < ret.length; i ++) {
ret[i] = rand.nextInt(100);
}
return ret;
}
C:
int *gen_rand_arr(int arr_size) {
int *arr;
if ((arr = malloc(arr_size * sizeof(int))) == NULL) {
exit(1);
}
for (int i = 0; i < arr_size; i++) {
arr[i] = arc4random_uniform(100);
}
return arr;
}
TL;DR
一般来说，像这样的简短片段不是比较语言的公平方式。有很多因素在起作用。当您用 C 而不是 Java 编写代码时，代码不会自动变快。如果是这样的话，你可以写一个 Java2C 转换器。编译器标志很重要，还有程序员的技能。
更长的解释
我不能肯定地说，但是这个：
for (j = i - 1; j >= 0 && arr[j] > temp; j--) {
arr[j + 1] = arr[j];
}
缓存不是很友好，因为你是在向后遍历列表。我会尝试更改循环，以便外循环而不是内循环进行向后遍历。
但我要说你的问题存在根本性的缺陷。代码不会因为您将代码从 Java 重写为 C 而自动获得性能提升。同样，C 程序不会因为您将它们重写为汇编而自动变得更快。可以说 C 允许 你写出比 Java 更快的程序，但最终，结果取决于程序员。
可以加速 Java 程序的一件事是 JIT 编译器，它可以在运行时针对特定条件进行统计以优化代码。虽然可以使 C 编译器针对 typical 工作负载进行优化，但它无法针对 current 工作负载进行优化。
你说你使用了 -O3 作为 C 代码。但是你用的是什么目标？您是针对您的机器还是一般机器进行了优化？ JIT 编译器知道要优化的目标。尝试使用 -march=native
您确定 int 使用相同的尺码吗？它在 Java 中是 32 位，但在 C 中可能是 64 位。如果您改用 int32_t，它可能会加速 C 代码。但它也可能会减慢速度。 （这不太可能是原因，但我只是想提一下它的可能性）
当涉及到非常低级的东西时，C 通常会大放异彩。
如果我们查看您的 Java 代码：
for (int i = 1; i < array.length; i ++) {
int temp = array[i];
在这个例子中，聪明的编译器可以很容易地看出array永远不会被越界访问。但是，如果我们有类似的东西怎么办：
while(<condition>) {
int temp = array[foo()];
哪里不能事先确定array不会出界？然后 Java 被迫进行不断的边界检查以便能够抛出异常。代码将被翻译成类似：
while(<condition>) {
int i = foo();
if(i >= array.length)
throw exception;
int temp = array[i];
这提供了安全性，但会降低性能。 C 只会允许您越界访问，这样速度更快，但可能会导致难以发现的错误。
我发现了一个包含更多信息的好问题：Why would it ever be possible for Java to be faster than C++?
除此之外，我可以看到您在基准测试中包括了数据生成。那很糟糕。在启动定时器之前生成数据。像这样：
int *arrs[num_times];
for (int i = 0; i < num_times; i++)
arrs[i] = gen_rand_arr(arr_size);
gettimeofday(&start, NULL);
for (int i = 0; i < num_times; i++)
f(arrs[i], arr_size);
gettimeofday(&end, NULL);