为什么 Boost 的 QuickSort 比 Julia 的 QuickSort 慢？

Question

我正在比较 Julia 和 C++ 之间的性能。然后我发现 Julia 中的快速排序要快得多（甚至比 C++ 还要快），尤其是当数组的大小非常大时。

任何人都可以解释原因吗？

快速排序文件

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 在算法中使用了特殊的实现。

更多样品

我用更多的样本运行测试。似乎数据的分布是问题。

1. 数据分布广泛的最佳情况：

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; 
}

2. 数据分布广泛的最坏情况：

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;  
}

3. 集中分布式数据

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;  
}

我的源代码

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 个元素的数组切换到插入排序。

Answer 2

概括

TL;DR Julia 和 C++ 的std::sort性能非常接近。Boost 的pdqsort_branchless速度更快。

关键要点

方法：

1. 只衡量重要的事情。在您的代码中，您还测量了生成向量的设置时间。
2. 请注意，测试数据的分布与“生产”数据的分布相当。
3. 确保你用ref编译-march=native -mtune=native

代码：

• Boost 的pdqsort_branchless速度更快。STLstd::sort和 Julia 的排序在运行时性能上相当接近。
• 我还测试了qsort较慢的C。这就是为什么我不再展示它。
• 我还使用了BenchmarkTools Julia 包来对 Julia 的排序进行基准测试。

剧情解释：

• 我使用此脚本进行绘图。
• 如果标签太小：
  • 蓝色/最快：boost 的排序
  • 绿色和红色：std::sort和朱莉娅。

基准测试

C++

在 C++ 上，使用基准库。

为方便起见，您可以在Quick-Bench在线访问。这是此代码：https : //quick-bench.com/q/CVu8y1fjwh19AHJH1iUCogxG6Pk

这使您可以指定要测量的代码部分。它还可以正确地进行测量和统计。

下面是一个例子：

static void Example(benchmark::State &state) {
  std::vector<int> data(1024);
  std::iota(data.begin(), data.end(), 0);

  std::mt19937 mersenne_engine{1234};

  for (auto _ : state) {
    state.PauseTiming();
    std::shuffle(data.begin(), data.end(), mersenne_engine);
    state.ResumeTiming();

    std::sort(data.begin(), data.end());
  }
}
BENCHMARK(Example);

Google Benchmark仅测量for (auto _ : state) {...}块（定时块）内的代码。因此，上面的代码避免了测量设置时间的陷阱。

在每次运行之前，数据为shuffled。

朱莉娅

使用BenchmarkTools库，其中基准是这样完成的：

Random.seed!(1234)
function make_vec(n)
    return Random.randperm(Int32(n));
end

@benchmark sort!(arr; alg=QuickSort) setup=(arr=make_vec(1024));

数据生成

我们需要澄清您生成数据的方式。

正如您发现的那样，这些算法在已经排序的数据上运行速度最快，而在反向排序的数据上运行得更糟。

最后，需要知道基准算法在哪里运行的领域知识。数据分布的形状是什么？

随机数据

首先，让我们在[0, 10 000]. 比对已经排序的数据进行测试要好得多。

我使用的是固定种子，因此每次数据都相同（对于给定的 N）。如果你实例mersenne_engine有rnd_device()，你会得到不同的种子每一次，因此不同的数据。就个人而言，我喜欢使用随机但一致的数据，以使结果的可变性较小。请记住它，以便您以后进行分析。

请注意，生成 0 到 10k 之间的数据将导致输入数量级大于 10k 的许多重复。

混洗数据

如果您不想重复，则生成一个包含元素的向量，[0, 1, 2, ..., N]然后对数据进行洗牌。

这是我的做法：

Random.seed!(1234)
function make_vec(n)
    return Random.randperm(Int32(n));
end

@benchmark sort!(arr; alg=QuickSort) setup=(arr=make_vec(1024));

朱莉娅：

function make_vec(n)
    return Random.randperm(n);
end