c++ - 为什么 Boost 的 QuickSort 比 Julia 的 QuickSort 慢？

Question

我正在比较 Julia 和 C++ 之间的性能。然后我发现 Julia 中的快速排序要快得多(甚至比 C++ 还要快)，尤其是当数组的大小非常大时。
任何人都可以解释原因吗？
quickSort.jl

include("../dimension.jl")
function execute()  
    n = getDimension()
    print(stderr, "Julia,quickSort_optim,$n,");  # use default delimiter
    arr = zeros(Int32, n)
    for i = 1:n
        arr[i] = (777*(i-1)) % 10000
    end
    if n > 0
        sort!(arr; alg=QuickSort)
    end
end

# executing ...
execute()

quickSort_boost.cpp

#include "dimension.h" 
#include <boost/lambda/lambda.hpp>
#include <boost/sort/pdqsort/pdqsort.hpp>
#include <iostream>
#include <iterator>
#include <algorithm>
 
using namespace std;
using namespace boost::sort; 

int main()
{
    int n = getDimension();
    cerr << "C++,quickSort_boost," << n << ",";
    
    vector<int> arr(n);
    unsigned long long w;
    for(int i = 0; i < n; ++i){  // array for sorting
        w = (777*i) % 10000; // Array with values between 0 and 10000
        arr[i] = w;
    }
    
    if (n > 0){
        pdqsort_branchless(arr.begin(), arr.end(), [](const int &a, const int &b){return ( a < b );});
    }
    
    return 0;
}

对比

备注
函数 getDimension() 用于获取数组大小。
执行时间在 Ubuntu 下使用 shell 命令:/usr/bin/time 测量。编译器:clang 版本 6.0.0-1ubuntu2。优化级别:-02。 CPU:英特尔 i7-3820QM
我之所以比较整个执行时间，而不仅仅是算法本身，是因为我想比较这两种语言的性能，模拟一个真实的应用场景。
在 Julia 官方文档中，它写道: QuickSort: good performance for large collections。
这是因为 Julia 在算法中使用了特殊的实现。
更多 sample
我用更多的样本运行测试。看来 数据的分布是问题。

数据分布广泛的最佳情况:

function execute()  # julia code segment for specifying data
    for i = 1:n
        arr[i] = i
    end

for(int i = 0; i < n; ++i){  // c++ boost code segment for specifying data
    arr[i] =  i + 1; 
}

数据分布广泛的最坏情况:

function execute()  # julia code segment for specifying data
    for i = 1:n
        arr[i] = n - i + 1
    end

for(int i = 0; i < n; ++i){  // c++ boost code segment for specifying data
    arr[i] =  n - i;  
}

集中分布式数据

function execute()  # julia code segment for specifying data
    for i = 1:n
        arr[i] = i % 10
    end

for(int i = 0; i < n; ++i){  // c++ boost code segment for specifying data
    arr[i] =  (i + 1) % 10;  
}

My source code

Answer 1

不知道时间是怎么回事——你没有包含足够的代码来测试或重现。 QuickSort 的 Julia 代码非常简单，您可以在此处查看其源代码:
https://github.com/JuliaLang/julia/blob/77487611fd9751c0f31ac3853072e6ca11efaf05/base/sort.jl#L518-L579
我也会在此处包含代码以便于阅读:

@inline function selectpivot!(v::AbstractVector, lo::Integer, hi::Integer, o::Ordering)
    @inbounds begin
        mi = midpoint(lo, hi)

        # sort v[mi] <= v[lo] <= v[hi] such that the pivot is immediately in place
        if lt(o, v[lo], v[mi])
            v[mi], v[lo] = v[lo], v[mi]
        end

        if lt(o, v[hi], v[lo])
            if lt(o, v[hi], v[mi])
                v[hi], v[lo], v[mi] = v[lo], v[mi], v[hi]
            else
                v[hi], v[lo] = v[lo], v[hi]
            end
        end

        # return the pivot
        return v[lo]
    end
end

function partition!(v::AbstractVector, lo::Integer, hi::Integer, o::Ordering)
    pivot = selectpivot!(v, lo, hi, o)
    # pivot == v[lo], v[hi] > pivot
    i, j = lo, hi
    @inbounds while true
        i += 1; j -= 1
        while lt(o, v[i], pivot); i += 1; end;
        while lt(o, pivot, v[j]); j -= 1; end;
        i >= j && break
        v[i], v[j] = v[j], v[i]
    end
    v[j], v[lo] = pivot, v[j]

    # v[j] == pivot
    # v[k] >= pivot for k > j
    # v[i] <= pivot for i < j
    return j
end

function sort!(v::AbstractVector, lo::Integer, hi::Integer, a::QuickSortAlg, o::Ordering)
    @inbounds while lo < hi
        hi-lo <= SMALL_THRESHOLD && return sort!(v, lo, hi, SMALL_ALGORITHM, o)
        j = partition!(v, lo, hi, o)
        if j-lo < hi-j
            # recurse on the smaller chunk
            # this is necessary to preserve O(log(n))
            # stack space in the worst case (rather than O(n))
            lo < (j-1) && sort!(v, lo, j-1, a, o)
            lo = j+1
        else
            j+1 < hi && sort!(v, j+1, hi, a, o)
            hi = j-1
        end
    end
    return v
end

没有什么特别的，只是一个基本的优化的快速排序。所以真正的问题是为什么 C++/Boost 版本很慢，我无法回答。也许在这里闲逛的众多 C++ 专家之一可以解决这个问题。
似乎 C++ 可能不像 Julia 那样选择枢轴。支点选择是一种平衡行为:一方面，如果你选择不好的支点，渐近行为会变得非常糟糕；另一方面，如果您花费太多时间和精力挑选支点，则会大大减慢整个排序的速度。
另一种可能性是，一旦数组大小变小，Boost 的快速排序实现就不会使用不同的算法作为基本情况。这是良好性能的关键，因为快速排序在小数组上表现不佳。 Julia 版本对少于 20 个元素的数组切换到插入排序。