与 Julia 相比对 C 冒泡排序性能进行基准测试

Question

我想对 C 和 Julia 的性能进行正式比较。为此，我想比较不同的排序算法，从气泡开始。在 Julia 中我这样写：

using BenchmarkTools

function bubble_sort(v::AbstractArray{T}) where T<:Real
    for _ in 1:length(v)-1
        for i in 1:length(v)-1
            if v[i] > v[i+1]
                v[i], v[i+1] = v[i+1], v[i]
            end
        end
    end
    return v
end

v = rand(Int32, 100_000)
@timed bubble_sort(_v)

对于 C 代码（我不知道用 C 编程，所以我对代码表示歉意）：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

static void swap(int *xp, int *yp){
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

void bubble_sort(int arr[], int n){
    int i, j;
    for (j = 0; j < n - 1; j++){
        for (i = 0; i < n - 1; i++){
            if (arr[i] > arr[i+1]){
                swap(&arr[i], &arr[i+1]);
            }
        }
    }
}

int main(){
    int arr_sz = 100000;
    int arr[arr_sz], i;
    for (i = 0; i < arr_sz; i++){
        arr[i] = rand();
    }
    double cpu_time_used;
    clock_t begin = clock();
    bubble_sort(arr, arr_sz);
    clock_t end = clock();
    cpu_time_used = ((double) (end - begin)) / CLOCKS_PER_SEC;
    printf("time %f\n", cpu_time_used);
    return 0;
}

性能差异是（在我的电脑上）：

朱莉娅	C
20多岁	〜50秒

我想我在 C 代码中有一个很大的错误，但我无法找出它，或者只是 Julia 在循环中更快？

更新：性能优化

• 在 Julia 中将类型更改为 int32，因此它与 C 相同
• swap静态方法（平均提高 1 秒）
• 编译优化（详细如下）

我没有gcc main.c使用 ，而是使用了不同的优化标志，以及 clang 编译器。结果：

	时间（秒）
朱莉娅	19.13
gcc -O main.c	47.58
gcc -O1 main.c	15.98
gcc -O2 main.c	19.52
gcc -O3 main.c	19.20
gcc -Os main.c	17.72
clang -O0 main.c	51.59
clang -O1 main.c	16.78
clang -O2 main.c	13.53
clang -O3 main.c	13.57
clang -Ofast main.c	12.39
clang -Os main.c	18.85
clang -Oz main.c	15.64
clang -Og main.c	16.37

Answer 1

在您发现您的初始测量是针对为调试而编译的代码进行的，而不是完全优化的，使用不同的数据集、不同的编译器平台和不同的整数表示形式后，似乎这个问题可能已被重新打开。

我想我在 C 代码中有一个很大的错误，但我无法找出它，或者只是 Julia 在循环中更快？

我可以引用C 标准来回答这个有点令人尴尬的（在我看来）双重问题：“本国际标准中的语义描述描述了与优化问题无关的抽象机器的行为。” 简而言之，C 语言没有速度；这是 C实现中出现的一个属性。如果没有您的实现（例如，包括您的硬件），我们就无法重现您的速度。

朱莉娅的规范中很可能有类似的条款。要点是：一些巧妙的优化可能会确定您的排序数组没有任何必要的副作用，因此理论上这些可能会被优化掉。在这种情况下，我希望这两个程序都能输出接近 0.0 的值。这是您完美的最佳编译器；一种发现对程序逻辑没有实际影响的代码，并优化掉死代码的方法。

我们并不总是具有循环不变的代码运动，因此按理说这里可能有第五个元素：您的编译器版本。如果底层 llvm 不同，您可能会得到不同的统计信息，例如：

与已有 10 多年历史的 LLVM 2.7 相比，LLVM 11 往往需要花费 2 倍的时间来编译经过优化的代码，因此生成的代码运行速度要快 10-20%（在任一方向上偶尔会出现异常值）。

-来源

也许有一天您会用两个程序的输出都读取 0.0s 来更新这个问题。那么这个问题就真的失去了意义。

很难说这里还问什么，@cbk。通过这四项改进，注释部分成功地显着减少了 C 程序的运行时间。这个问题在这里甚至不再有意义，因为它在最后通过回答自己而在很大程度上抵消了自己。

也许这只是新人应该用答案回答自己的问题的情况之一（你可以这样做），而不是通过编辑来回答问题来破坏问题......尽管如此，这是一个现在出现的问题问题列表中未得到答复。我投票结束的原因是“问题应该包含更多细节”，但我怀疑你可能会包含一个在程序集生成后停止编译的示例，当OP似乎掩盖了解决方案时，我们需要的细节更多大致是“对于这些回答你最初问题的评论，你不明白什么？” 然而这个问题的表面意义却变化很大……我们会进行一场近距离/重新开战吗？