C++ STL 算法 sort 的并行排序实现

在 C++ 编程中，标准模板库（STL）的 sort 算法是对序列进行排序的常用工具。传统的 sort 算法是顺序执行的，在处理大规模数据时，其性能可能会受到单核处理能力的限制。随着多核处理器的普及，并行排序成为提升排序效率的有效手段。本文将深入探讨如何在 C++ 中利用并行算法实现 sort 功能。

并行排序的基本概念

并行排序是将排序任务分解为多个子任务，利用多个处理器核心同时处理这些子任务，从而加速排序过程。并行排序算法的设计需要考虑任务划分、负载均衡以及数据同步等问题。在 C++ 中，我们可以借助线程库或者并行算法库来实现并行排序。

C++ 并行算法库

C++17 引入了并行算法库 <execution>，它提供了执行策略来控制算法的执行方式，包括顺序执行、并行执行和并行矢量化执行。这些执行策略可以与 STL 算法结合使用，使得原本顺序执行的算法能够以并行方式运行。

使用 `<execution>` 库实现并行排序

1. 引入头文件

首先，我们需要引入 <algorithm> 和 <execution> 头文件。

#include <algorithm>
#include <execution>
#include <iostream>
#include <vector>

2. 定义数据和执行策略

我们定义一个 std::vector 来存储待排序的数据，并选择合适的执行策略。<execution> 库提供了三种执行策略：std::execution::seq（顺序执行）、std::execution::par（并行执行）和 std::execution::par_unseq（并行矢量化执行）。

int main() {
    std::vector<int> data = {5, 4, 6, 2, 7, 1, 3};
    // 使用并行执行策略
    std::execution::parallel_policy policy;

3. 调用并行 `sort` 算法

使用 std::sort 并传入执行策略和迭代器范围。

    std::sort(policy, data.begin(), data.end());

4. 输出结果

排序完成后，输出排序后的结果。

    for (int num : data) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

在上述代码中，std::sort(policy, data.begin(), data.end()) 这一行代码利用并行执行策略 policy 对 data 向量进行排序。std::execution::parallel_policy 会尝试将排序任务并行化，利用多个线程来加速排序过程。

并行排序的性能分析

并行排序在处理大规模数据时通常能显著提升性能。然而，对于小规模数据，并行排序可能会因为线程创建、任务划分和同步等开销而导致性能下降。因此，在实际应用中，需要根据数据规模来选择合适的排序方式。

数据规模对性能的影响

我们可以通过实验来观察数据规模对并行排序性能的影响。以下是一个简单的性能测试代码示例：

#include <algorithm>
#include <execution>
#include <chrono>
#include <iostream>
#include <vector>

void testSort(std::vector<int>& data) {
    auto start = std::chrono::high_resolution_clock::now();
    std::sort(std::execution::par, data.begin(), data.end());
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    std::cout << "Parallel sort time: " << duration << " ms" << std::endl;
}

int main() {
    for (int size = 1000; size <= 10000000; size *= 10) {
        std::vector<int> data(size);
        for (int i = 0; i < size; ++i) {
            data[i] = rand();
        }
        std::cout << "Testing with data size: " << size << std::endl;
        testSort(data);
    }
    return 0;
}

在这个代码中，我们生成不同规模的数据向量，并使用并行 sort 算法对其进行排序，记录每次排序所花费的时间。通过运行这段代码，可以发现随着数据规模的增大，并行排序的优势逐渐显现。

并行排序的实现细节

任务划分

并行 sort 算法通常采用分治策略进行任务划分。例如，经典的并行快速排序算法会将数据分成多个子数组，每个子数组由不同的线程进行排序。在 <execution> 库的实现中，它会自动将数据范围划分为多个子范围，并分配给不同的线程处理。

负载均衡

负载均衡是并行排序中的关键问题。如果任务划分不均匀，可能会导致某些线程处理的数据量过多，而其他线程过早完成任务，从而降低整体并行效率。为了解决这个问题，一些并行排序算法采用动态任务分配的方式，在运行时根据线程的负载情况重新分配任务。

数据同步

在并行排序中，由于多个线程同时访问和修改数据，数据同步变得至关重要。<execution> 库通过内部的同步机制来确保数据的一致性和正确性。例如，在合并多个已排序子数组时，需要确保不同线程对共享数据的访问是安全的。

自定义比较函数与并行排序

在实际应用中，我们常常需要根据自定义的比较规则对数据进行排序。在并行 sort 中，同样可以使用自定义比较函数。

定义自定义比较函数

假设有一个结构体 Person，我们希望根据 age 字段对 Person 对象的向量进行排序。

struct Person {
    std::string name;
    int age;
};

bool compareByAge(const Person& a, const Person& b) {
    return a.age < b.age;
}

使用自定义比较函数进行并行排序

int main() {
    std::vector<Person> people = {{"Alice", 25}, {"Bob", 20}, {"Charlie", 30}};
    std::sort(std::execution::par, people.begin(), people.end(), compareByAge);
    for (const Person& person : people) {
        std::cout << person.name << " : " << person.age << std::endl;
    }
    return 0;
}

在上述代码中，std::sort(std::execution::par, people.begin(), people.end(), compareByAge) 使用并行执行策略和自定义的 compareByAge 函数对 people 向量进行排序。

并行排序的潜在问题与解决方案

线程安全问题

虽然 <execution> 库提供了一定的线程安全机制，但在某些复杂场景下，仍然可能出现线程安全问题。例如，如果自定义比较函数中访问了共享资源，并且没有正确同步，可能会导致数据竞争。解决方案是在共享资源访问处使用适当的同步原语，如互斥锁。

缓存一致性问题

在多核系统中，不同核心的缓存可能存在不一致的情况。并行排序过程中频繁的数据访问可能会导致缓存命中率下降，影响性能。为了缓解这个问题，可以优化数据结构和算法，减少数据的跨核心访问，尽量让每个线程处理的数据都在其本地缓存中。

与其他并行排序库的比较

除了 C++ 标准库中的并行算法，还有一些第三方库提供了高性能的并行排序实现，如 Intel 的 TBB（Threading Building Blocks）库。

TBB 的并行排序

TBB 提供了 tbb::parallel_sort 函数，其使用方式与 C++ 标准库的并行 sort 类似。

#include <tbb/parallel_sort.h>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> data = {5, 4, 6, 2, 7, 1, 3};
    tbb::parallel_sort(data.begin(), data.end());
    for (int num : data) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

性能比较

在某些情况下，TBB 的并行排序可能会比 C++ 标准库的并行 sort 性能更好，尤其是在处理大规模数据并且在 Intel 架构的处理器上。这是因为 TBB 针对特定硬件进行了优化。然而，C++ 标准库的并行算法具有更好的可移植性，适用于各种平台。

结论

通过使用 C++ 的并行算法库 <execution>，我们可以轻松地将传统的顺序 sort 算法转换为并行排序，从而在多核处理器上提升排序性能。在实际应用中，需要根据数据规模、硬件环境和具体需求来选择合适的排序方式和库。同时，要注意并行排序中的任务划分、负载均衡、数据同步等问题，以确保程序的正确性和高效性。无论是使用标准库还是第三方库，并行排序都是提升 C++ 程序性能的有力手段。

C++ STL 算法 sort 的并行排序实现