首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >为什么在这个简单的C++基准测试示例中,Java比BubbleSort更快?

问为什么在这个简单的C++基准测试示例中,Java比BubbleSort更快?
EN

Stack Overflow用户
提问于 2022-06-24 12:54:08
回答 2查看 789关注 0票数 1

我从同事那里听说,C++比Java更快,在寻找最佳性能时,尤其是在金融应用程序中,这是一条必经之路。但我的观察有点不同。有人能指出我的实验失败或者在讨论中增加一些科学变量吗?

Note1: I在C++编译器中使用-O3 (最大优化)和-O2。

Note2:包括每种语言的简短和简单的完整源代码。可以自由地在你自己的机器上运行,做出改变,得出结论和分享。

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

更新:--我尝试了clang++和g++的各种优化选项(-O2、-O3、-Os、-march=native等),结果都比Java慢。我认为在这一点上,为了使C++更快,我必须深入研究生成的组装代码,并执行一些程序集编程。我想知道这种方法(组装编程和程序集调试)在编写大型实际应用程序时有多实际。

基准是做什么的?

在堆中(而不是在堆栈中)创建一个int数组,启动clock

  • Populate
  • ,用气泡排序
  • 来排序数组,停止时钟

F 231

这样做1000万次,放弃前100万的热身,并输出平均,最小和最大的时间。

对于C++,我得到:(使用-O3和-O2)

代码语言:javascript
复制
$ 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

对于,我得到:

代码语言:javascript
复制
$ 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++代码:

代码语言:javascript
复制
#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;
}

完整的Java代码:

代码语言:javascript
复制
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");
    }
}
EN

回答 2

Stack Overflow用户

发布于 2022-06-24 13:51:38

在这两种情况下,数组都按降序填充数字。然后对气泡进行排序,以便代码的行为应该有所不同。但是分配数组的方式是不同的。

在C++ you malloc中。WHich只会使内核记录您已经请求了一些内存,但是没有将任何物理内存映射到这些地址。因此,一旦时钟启动,并开始初始化数组,每个页面都会导致一个页面错误,然后内核映射一个物理页面并找到正确的地址。

但是,在Java中,将数组分配并初始化为0。这将导致映射所有物理页面,并且内存现在也在cpu缓存中。因此,当您启动时钟时,数组的初始化要快得多。

但我想这就是热身应该处理的问题。

也就是说你的测试方法是有缺陷的。c++编译器可以优化整个循环,但get_nano_ts()调用除外。所以你的C++代码基本上是

代码语言:javascript
复制
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; totalTime = iterations - warmup;

你为什么把0数成1?如果排序甚至不需要纳秒,那么您应该中止,因为您的测试用例太小,无法保证时钟的准确性。

让我们来讨论一下您测量到的结果:

代码语言:javascript
复制
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次。因此,算法每次的行为都应该是相同的,而且每次运行都需要完全相同的时间。然而,你测量的时间相差超过2个数量级。在某些情况下,这种类型花费的时间是其他情况下的200倍(java是40倍)。

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

代码语言:javascript
复制
# 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%的最大时间。至少是Min Time和Avg。时间相对稳定。因此,操作系统似乎很少会中断进程并将其洗牌到不同的CPU核心,从而导致所有缓存丢失,然后执行时间就会变得糟糕。

让我们稍微使用编译器标志:

代码语言:javascript
复制
# 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。

让我们更进一步:

代码语言:javascript
复制
# 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++:

代码语言:javascript
复制
# 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经常使用-O3代码比-O2慢。在大多数情况下,许多优化器选项都在-O3中,原因是它们通常不是更快。否则,他们将在-O2。(不包括任何被认为还不够稳定的实验优化)。

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

查看clang++输出会让我重新思考这个问题。不同的编译器,不同的优化器,不同的-Os / -O2 / -O3行为。

现在真正的工作开始了:编译器生成什么样的代码才能产生如此大的差异?对于"gcc -O3“来说,速度是”gcc -O3“的5倍,而对于"clang++ -O3”则是前者的两倍。

对我的GCC11来说,答案是Bubble sort slower with -O3 than -O2 with GCC,-O3的减速是一个非常具体的反优化,它通常会有帮助,或者至少不会带来太大的伤害,但是在这里,它会带来很大的伤害,因为它不会让array[j+1]暂时地成为下一个迭代的array[j]。相反,将其从内存中重新加载,作为一对负载的一部分,这是它在一个大负载下所做的工作,从而创建了一个存储转发延迟。

不过,你的GCC版本没有这个问题,只有GCC11和更新版本。所以不要期望会有很大的加速;您的GCC7 -O3应该已经没有什么大问题了,除了可能的事情,比如How can I mitigate the impact of the Intel jcc erratum on gcc?,如果您使用Skylake。

(但是,当将一个元素从一个数组冒泡到另一个数组时,两个元素的存储和重新加载仍然会创建一个循环携带的依赖项,这比为下一次迭代更新寄存器更糟糕。)

不过,无论clang在做什么,都比GCC最好的版本要好,所以你可能会因此得到一个很大的加速。

票数 4
EN

Stack Overflow用户

发布于 2022-06-26 08:45:54

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

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/72744401

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档