c - c 和 Julia 中的排序速度

Question

我正在开发排序算法，并惊讶地发现 c 的 qsort 是 Julia 的默认排序算法的 1.6 倍。我想我正在犯某种基准测试错误。以下是我的基准测试程序及其结果:
Julia :

# time (julia bench.jl)
using Printf
function main()
    len = 100_000_000
    x = rand(Int64, len)
    t = @elapsed sort!(x)
    @printf "%d elements:\nclaim\t%fs" len t
end
main()

C

// time (gcc -O3 bench.c && ./a.out)

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

int comp (const void * elem1, const void * elem2)
{
    int f = *((int*)elem1);
    int s = *((int*)elem2);
    if (f > s) return  1;
    if (f < s) return -1;
    return 0;
}
long long utime()
{
    struct timeval now_time;

    gettimeofday(&now_time, NULL);

    return now_time.tv_sec * 1000000LL + now_time.tv_usec;
}
int main(int argc, char* argv[])
{
        long length = 100000000;
        long long *x;
        x = (long long *) malloc(length * sizeof(long long));
        if (x == NULL)
        {
            printf("Malloc failed\n");
            return 1;
        }

        for (long cnt = 0 ; cnt < length ; cnt++)
            x[cnt] = rand();

        long long start = utime();
    qsort (x, length, sizeof(*x), comp);
        long long end = utime();

        //for (long cnt = 0 ; cnt < length ; cnt += length/10)
        //      printf("%lld\n", x[cnt]);

        free(x);

        printf ("%ld elements:\nclaim\t%fs", length, (end-start)/1000000.0);

    return 0;
}

结果

bash-3.2$ time (julia bench.jl)
100000000 elements:
claim   12.405531s
real    0m16.560s
user    0m13.883s
sys 0m1.297s
bash-3.2$ time (gcc -O3 bench.c && ./a.out)
100000000 elements:
claim   20.592641s
real    0m24.604s
user    0m21.352s
sys 0m2.479s

Julia 的算法(3 个快速排序的中位数，对于少于 20 个元素的插入排序基本情况)是否比 c 的 qsort 快得多？我可以比 c 中的 qsort 更快地排序吗？

Answer 1

比 C 的排序更容易 qsort .例如，您可以使用 C++ 的 std::sort . C++ 库不是更快，因为它使用了更好的算法；相反，这是因为 C++ 的泛型允许编译器避免调用比较函数的开销以及需要处理任意大小元素的 qsort 交换中的较​​小开销。
下面，sortbench-c 和 sortbench-cc 的唯一区别是使用 std::sort在后者中:

$ diff sortbench-c.c sortbench-cc.cc
1c1
< // time (gcc -O3 sortbench-c.c && ./a.out)
---
> // time (gcc -O3 sortbench-cc.cc && ./a.out)
2a3
> #include <algorithm>
7,14d7
< int comp (const void * elem1, const void * elem2)
< {
<     int f = *((int*)elem1);
<     int s = *((int*)elem2);
<     if (f > s) return  1;
<     if (f < s) return -1;
<     return 0;
< }
38c31
<     qsort (x, length, sizeof(*x), comp);
---
>         std::sort(x, x+length);

差异是巨大的:

$ time (gcc -O3 sortbench-c.c && ./a.out)
100000000 elements:
claim   16.673827s
real    0m17.774s
user    0m17.387s
sys     0m0.379s
$ time (gcc -O3 sortbench-cc.cc && ./a.out)
100000000 elements:
claim   9.948971s
real    0m11.133s
user    0m10.926s
sys     0m0.204s