为什么Java在这个简单的BubbleSort基准测试示例中比C更快？

Question

我从同事那里听说C比Java快，在寻找最佳性能时，尤其是对于金融应用程序，这是要走的路。但我的观察有点不同。有人能指出我实验的失败之处，或者在讨论中添加一些科学变量吗？

注意 1：我正在使用 -O3（最大优化）和 -O2 与 C 编译器。

注2:每种语言的简短完整的源代码都包括在内。随意在自己的机器上运行，做出改变，得出结论，分享。

注3：如果您将两个源代码并排放在编辑器中，您将看到它们的实现是等价的。

更新:我已经用各种优化选项(< code>-O2 、< code>-O3 、< code>-Os 、< code>-march=native等)尝试了< code>clang 和< code>g ，它们产生的结果都比Java慢。我认为在这一点上，为了让C更快，我必须深入到生成的汇编代码中，并进行一些汇编编程。我想知道在编写大型实际应用程序时，这种方法(汇编编程和汇编调试)的实用性如何。

基准是做什么的？

• 在堆中（不在堆栈中）创建一个int数组
• 启动时钟
• 填充数组
• 使用气泡排序对数组进行排序
• 停止时钟

做1000万次，丢弃前100万次用于预热，并输出平均、最小和最大时间。

对于C，我得到:(用-O3和-O2)

$ g++ --version
g++ (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0

$ g++ TimeBubbleSort.cpp -o TimeBubbleSort -std=c++11 -O3
$ ./TimeBubbleSort 10000000 1000000 60
Value computed: 18300000000
Iterations: 9000000 | Avg Time: 1202 | Min Time: 1158 | Max Time: 212189

$ g++ TimeBubbleSort.cpp -o TimeBubbleSort -std=c++11 -O2
$ ./TimeBubbleSort 10000000 1000000 60
Value computed: 18300000000
Iterations: 9000000 | Avg Time: 1337 | Min Time: 1307 | Max Time: 36650

对于Java，我得到：

$ java -version
java version "17.0.1" 2021-10-19 LTS
Java(TM) SE Runtime Environment (build 17.0.1+12-LTS-39)
Java HotSpot(TM) 64-Bit Server VM (build 17.0.1+12-LTS-39, mixed mode, sharing)

$ javac -cp . TimeBubbleSort.java
$ java -cp . TimeBubbleSort 10000000 1000000 60
Value computed: 18300000000
Iterations: 9000000 | Avg Time: 837.0 | Min Time: 812 | Max Time: 37196

完整的 C 代码：

#include <iostream>
#include <limits>
#include <sstream>

using namespace std;

// TO COMPILE: g++ TimeBubbleSort.cpp -o TimeBubbleSort -std=c++11 -O3
// TO EXECUTE: ./TimeBubbleSort 10000000 1000000 60

long get_nano_ts(timespec* ts) {
    clock_gettime(CLOCK_MONOTONIC, ts);
    return ts->tv_sec * 1000000000 + ts->tv_nsec;
}

struct mi {
   long value;
};

void swapping(int &a, int &b) {
   int temp;
   temp = a;
   a = b;
   b = temp;
}

void bubbleSort(int *array, int size) {
   for(int i = 0; i < size; i++) {
      bool swaps = false;
      for(int j = 0; j < size - i - 1; j++) {
         if(array[j] > array[j+1]) {
            swapping(array[j], array[j+1]);
            swaps = true;
         }
      }
      if (!swaps) break;
   }
}

void doSomething(int *array, int size) {

    for(int z = 0; z < size; z++) {
        array[z] = size - z;
    }

    bubbleSort(array, size);
}

int main(int argc, char* argv[]) {
    
    int iterations = stoi(argv[1]);
    int warmup = stoi(argv[2]);
    int arraySize = stoi(argv[3]);
    
    struct timespec ts;
    
    long long x = 0;
    long long totalTime = 0;
    int minTime = numeric_limits<int>::max();
    int maxTime = numeric_limits<int>::min();
    
    int * array = (int*) malloc(arraySize * sizeof(int));
    
    for(int i = 0; i < iterations; i++) {
    
        long start = get_nano_ts(&ts);

        doSomething(array, arraySize);  
        
        long end = get_nano_ts(&ts);
        
        for(int j = 0; j < arraySize; j++) {
            x += array[j];
        }

        int res = end - start;
        
        if (res <= 0) res = 1;
        
        if (i >= warmup) {
            totalTime += res;
            minTime = min(minTime, res);
            maxTime = max(maxTime, res);
        }
    }
    
    int count = iterations - warmup;
    
    double avg = totalTime / count;
    
    cout << "Value computed: " << x << endl;
    
    stringstream ss;
    
    ss << "Iterations: " << count << " | Avg Time: " << avg;

    if (count > 0) {
        ss << " | Min Time: " << minTime << " | Max Time: " << maxTime;
    }
    
    cout << ss.str() << endl << endl;
    
    free(array);
        
    return 0;
}

完整的公文代码：

public class TimeBubbleSort {
    
    // javac -cp . TimeBubbleSort.java
    // java -cp . TimeBubbleSort 10000000 1000000 60
    
    private static void swapping(int[] array, int x, int y) {
        int temp = array[x];
        array[x] = array[y];
        array[y] = temp;
    }
    
    private static void bubbleSort(int[] array, int size) {
        for(int i = 0; i < size; i++) {
            int swaps = 0; // flag to detect any swap is there or not
            for(int j = 0; j < size - i - 1; j++) {
                if (array[j] > array[j + 1]) { // when the current item is bigger than next
                    swapping(array, j, j + 1);
                    swaps = 1;
                }
            }
            if (swaps == 0) break; // No swap in this pass, so array is sorted
        }
    }
    
    private final static void doSomething(int[] array, int size) {
        
        for(int z = 0; z < size; z++) {
            array[z] = size - z;
        }

        bubbleSort(array, size);
    }
    
    public static void main(String[] args) {
        
        int iterations = Integer.parseInt(args[0]);
        int warmup = Integer.parseInt(args[1]);
        int arraySize = Integer.parseInt(args[2]);
        
        long x = 0;
        long totalTime = 0;
        long minTime = Long.MAX_VALUE;
        long maxTime = Long.MIN_VALUE;
        
        int[] array = new int[arraySize];
        
        for(int i = 0; i < iterations; i++) {

            long start = System.nanoTime();
            
            doSomething(array, arraySize);
            
            long end = System.nanoTime();
            
            for(int j = 0; j < arraySize; j++) {
                x += array[j];
            }
            
            int res = (int) (end - start);
            
            if (res <= 0) res = 1;
            
            if (i >= warmup) {
                totalTime += res;
                minTime = Math.min(minTime, res);
                maxTime = Math.max(maxTime, res);
            }
        }
        
        int count = iterations - warmup;
        
        double avg = totalTime / count;
        
        StringBuilder sb = new StringBuilder();
        
        sb.append("Value computed: ").append(x).append("\n");
        
        sb.append("Iterations: ").append(count).append(" | Avg Time: ").append(avg);

        if (count > 0) {
            sb.append(" | Min Time: ").append(minTime).append(" | Max Time: ").append(maxTime);
        }
        
        System.out.println(sb.toString() + "\n");
    }
}

Answer 1

考虑到JIT在解决和消除死代码方面有多好，我强烈建议使用合适的基准测试工具重写这两个基准，例如Java端的https://github.com/openjdk/jmh。

Answer 2

在这两种情况下，数组都是按降序填充数字。然后冒泡排序，因此代码的行为应该不同。但是您分配数组的方式不同。

在C中，你马洛克。WHich只是让内核记录您请求的一些内存，但不会将任何物理内存映射到地址。因此，一旦时钟开始，您开始初始化数组，每个页面都会导致页面错误，然后内核将物理页面映射到正确的地址。

在Java中，你分配并初始化数组为0。这导致所有物理页面都被映射，并且内存现在也在cpu缓存中。因此，当您启动时钟时，阵列的初始化会快得多。

但我想这就是热身应该注意的。

也就是说你的测试方法有缺陷。c编译器可以优化整个循环，除了get_nano_ts（）调用。所以你的C代码基本上是

for(int i = warmup; i < iterations; i++) {
    long start = get_nano_ts(&ts);
    long end = get_nano_ts(&ts);
    x += n * (n-1) / 2;
    int res = end - start;
    if (res <= 0) res = 1;
    totalTime += res;
    minTime = min(minTime, res);
    maxTime = max(maxTime, res);
}

这将非常接近minTime=1；maxTime=1；总计时间=迭代-预热；

为什么你把时间0计算为1？如果排序甚至不需要一纳秒，您应该中止，因为您的测试用例对于时钟的精度来说太小了。

让我们讨论一下您测量的结果：

C++: Iterations: 9000000 | Avg Time: 1202 | Min Time: 1158 | Max Time: 212189
Java: Iterations: 9000000 | Avg Time: 837.0 | Min Time: 812 | Max Time: 37196

你用完全相同的数字对完全相同的数组排序9000000次。所以算法每次都应该表现相同，而且每次运行都应该花费完全相同的时间。然而你测量的时间相差超过两个数量级。也就是说，在某些情况下，排序花费的时间是其他情况的200倍（java是40倍）。

让我们看看当我多次重复测试时会发生什么？

# g++ TimeBubbleSort.cpp -o TimeBubbleSort -std=c++11 -O3
# ./TimeBubbleSort 10000000 1000000 60
Value computed: 18300000000
Iterations: 9000000 | Avg Time: 11155 | Min Time: 10950 | Max Time: 315173
# ./TimeBubbleSort 10000000 1000000 60
Value computed: 18300000000
Iterations: 9000000 | Avg Time: 11163 | Min Time: 10950 | Max Time: 234000
# ./TimeBubbleSort 10000000 1000000 60
Value computed: 18300000000
Iterations: 9000000 | Avg Time: 11320 | Min Time: 10950 | Max Time: 334208

只需执行多次运行即可显示更改的最长时间为 50%。至少最小时间和平均时间相对稳定。因此，似乎操作系统很少会中断该过程并将其洗牌到不同的CPU内核，从而导致所有缓存丢失，然后执行时间很糟糕。

让我们稍微玩一下编译器标志：

# g++ TimeBubbleSort.cpp -o TimeBubbleSort -std=c++11 -O2
# ./TimeBubbleSort 10000000 1000000 60
Value computed: 18300000000
Iterations: 9000000 | Avg Time: 2320 | Min Time: 2194 | Max Time: 75442
# ./TimeBubbleSort 10000000 1000000 60
Value computed: 18300000000
Iterations: 9000000 | Avg Time: 2375 | Min Time: 2194 | Max Time: 199976

嘿，优化更少，速度快5倍。请注意，最初Java只是比c快一点。当然，C代码现在必须击败java。

让我们更进一步：

# g++ TimeBubbleSort.cpp -o TimeBubbleSort -std=c++11 -Os
./TimeBubbleSort 10000000 1000000 60
Value computed: 18300000000
Iterations: 9000000 | Avg Time: 2447 | Min Time: 2254 | Max Time: 234702

针对大小进行优化几乎不会对速度产生任何影响（如果有的话）。我会说它低于噪音水平。可能只是代码或其他东西的不同缓存对齐方式的伪像。

或者让我们试试铿锵：

# clang++ TimeBubbleSort.cpp -o TimeBubbleSort -std=c++11 -Os
# ./TimeBubbleSort 10000000 1000000 60
Value computed: 18300000000
Iterations: 9000000 | Avg Time: 2177 | Min Time: 2104 | Max Time: 189857

# clang++ TimeBubbleSort.cpp -o TimeBubbleSort -std=c++11 -O2
# ./TimeBubbleSort 10000000 1000000 60
Value computed: 18300000000
Iterations: 9000000 | Avg Time: 1479 | Min Time: 1293 | Max Time: 236334

# clang++ TimeBubbleSort.cpp -o TimeBubbleSort -std=c++11 -O3
# ./TimeBubbleSort 10000000 1000000 60
Value computed: 18300000000
Iterations: 9000000 | Avg Time: 1080 | Min Time: 1011 | Max Time: 135706

回过头来看我的回答，我完全没有指出gcc经常< code>-O3代码比< code>-O2慢。在很大程度上,< code>-O3中有很多优化器选项的原因是它们通常不会更快。否则它们将位于< code>-O2中。(不包括任何被认为还不够稳定的实验优化)。

不要使用 -O3，除非您已经测试过它确实是有益的，然后非常有选择性地使用 -O3 编译代码的哪一部分。

看着铿锵的输出让我重新思考这个问题。不同的编译器，不同的优化器，不同的-Os/-O2/-O3行为。

现在真正的工作开始了：编译器生成的什么代码会产生如此大的影响？“gcc-O3”慢5倍，“clang-O3”快两倍。

对于我的GCC11，答案是使用-O3时的冒泡排序比使用GCC时的-O2慢。这里的< code>-O3减速是一种非常特殊的反优化，通常会有所帮助，或者至少不会造成太大的伤害，但在没有将< code>array[j 1]临时保留在下一次迭代的< code>array[j]中的冒泡排序中，它会造成很大的伤害。而是作为一对加载的一部分从内存中重新加载，这造成了存储转发停顿。

但是，您的GCC版本没有这个问题，只有GCC11及更高版本。所以不要指望会有很大的加速;您的GCC7 -O3应该已经在没有重大问题的情况下进行了asm，除了可能的事情，例如如何减轻英特尔jcc错误对gcc的影响？如果您使用的是天湖 CPU。

（不过，当将元素从一个数组冒泡到另一个数组时，两个元素的存储和重新加载仍然会创建循环携带的依赖关系，这比只是为下一次html" target="_blank">迭代更新寄存器更糟糕。）

不管clang在做什么，它都比GCC的最佳版本要好，所以您可能会因此得到很大的加速。