面试题：C++ STL算法sort并行排序的性能优化

可能遇到的性能瓶颈

硬件资源利用方面
- 内存带宽限制：并行排序时，多个线程可能同时访问内存，若内存带宽不足，数据读取和写入会成为瓶颈。例如在处理大规模数据集时，频繁的内存I/O操作导致数据传输速度跟不上计算速度。
- CPU核心利用率不均衡：不同线程处理的数据量或计算复杂度不同，可能使部分CPU核心负载过重，而部分核心闲置，不能充分发挥多核CPU的性能。
数据分布方面
- 数据局部性差：如果数据在内存中分布不连续，缓存命中率会降低。并行排序过程中频繁的非连续内存访问，使得CPU频繁从主存读取数据，增加了访问延迟。
- 数据倾斜：若待排序的数据在某些区域分布不均匀，导致不同线程处理的数据量差异较大，影响整体并行效率。比如在按关键字排序时，某些关键字出现频率极高，集中在某几个线程处理的数据块中。
线程调度方面
- 线程创建和销毁开销：频繁创建和销毁线程会消耗大量系统资源，降低排序性能。例如在短时间内多次启动和停止并行排序任务，线程创建和销毁的时间开销不可忽视。
- 线程同步开销：并行排序需要线程间同步来保证数据一致性，如使用互斥锁等同步机制，过多的同步操作会引入额外开销，降低并行效率。

优化思路及代码修改方向

硬件资源利用优化
- 内存带宽优化
  - 思路：采用分块处理数据的方式，尽量让数据在缓存中停留更长时间。预取数据，提前将即将使用的数据加载到缓存中。
  - 代码修改方向：在排序算法中，根据硬件缓存大小，将数据分成合适大小的块进行处理。可以使用_mm_prefetch等预取指令（针对支持SSE指令集的CPU）。例如，在对数组arr进行排序前，对每个子块数据进行预取：

#include <xmmintrin.h>
// 假设arr是待排序数组，block_size是子块大小
for (size_t i = 0; i < arr.size(); i += block_size) {
    _mm_prefetch(&arr[i], _MM_HINT_T0);
}

CPU核心利用率优化
- 思路：动态分配任务给CPU核心，根据每个核心的负载情况，实时调整分配的数据量。使用任务队列，每个CPU核心从任务队列中获取任务。
- 代码修改方向：引入任务队列数据结构，例如std::queue。在并行排序时，将大的排序任务分解成小任务放入队列，每个线程从队列中取任务执行。

#include <queue>
#include <thread>
#include <mutex>
std::queue<SortTask> taskQueue;
std::mutex queueMutex;
void workerThread() {
    while (true) {
        SortTask task;
        {
            std::lock_guard<std::mutex> lock(queueMutex);
            if (taskQueue.empty()) break;
            task = taskQueue.front();
            taskQueue.pop();
        }
        // 执行排序任务
        std::sort(task.data.begin(), task.data.end());
    }
}
// 主线程中添加任务到队列
for (const auto& subTask : splitTasks(data)) {
    {
        std::lock_guard<std::mutex> lock(queueMutex);
        taskQueue.push(subTask);
    }
}
// 创建并启动线程
std::vector<std::thread> threads;
for (int i = 0; i < std::thread::hardware_concurrency(); ++i) {
    threads.emplace_back(workerThread);
}
// 等待所有线程完成
for (auto& thread : threads) {
    thread.join();
}

数据分布优化
- 数据局部性优化
  - 思路：在排序前对数据进行重排，使数据在内存中连续分布。使用缓存友好的数据结构，如数组代替链表。
  - 代码修改方向：如果数据原本是链表结构，将其转换为数组结构。例如对于链表list<int> dataList，转换为数组vector<int> dataArray：

std::list<int> dataList;
// 填充链表数据
std::vector<int> dataArray(dataList.begin(), dataList.end());
// 对数组进行并行排序
std::sort(dataArray.begin(), dataArray.end());

数据倾斜优化
- 思路：在并行排序前进行数据预处理，统计数据分布情况，根据分布将数据均匀分配给不同线程。例如采用哈希表统计关键字频率，然后重新划分数据块。
- 代码修改方向：在并行排序前添加数据分布统计和重新划分数据块的代码。

#include <unordered_map>
// 统计数据分布
std::unordered_map<int, int> keyCount;
for (const auto& num : data) {
    keyCount[num]++;
}
// 根据分布重新划分数据块
std::vector<std::vector<int>> newDataBlocks;
// 划分逻辑，这里简单示意根据关键字频率大致均匀划分
for (const auto& pair : keyCount) {
    // 将数据分配到不同块
}
// 对新的数据块进行并行排序

线程调度优化
- 线程创建和销毁开销优化
  - 思路：使用线程池，线程池中的线程可以重复利用，减少线程创建和销毁的开销。
  - 代码修改方向：引入线程池类，例如使用boost::thread_pool或自行实现一个简单线程池。以下是一个简单线程池实现的示意代码：

#include <vector>
#include <queue>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <functional>
class ThreadPool {
public:
    ThreadPool(size_t numThreads) {
        for (size_t i = 0; i < numThreads; ++i) {
            threads.emplace_back([this] {
                while (true) {
                    std::function<void()> task;
                    {
                        std::unique_lock<std::mutex> lock(this->queueMutex);
                        this->condition.wait(lock, [this] {
                            return this->stop ||!this->tasks.empty();
                        });
                        if (this->stop && this->tasks.empty()) return;
                        task = std::move(this->tasks.front());
                        this->tasks.pop();
                    }
                    task();
                }
            });
        }
    }
    ~ThreadPool() {
        {
            std::unique_lock<std::mutex> lock(queueMutex);
            stop = true;
        }
        condition.notify_all();
        for (std::thread& thread : threads) {
            thread.join();
        }
    }
    template<class F, class... Args>
    auto enqueue(F&& f, Args&&... args) -> std::future<typename std::result_of<F(Args...)>::type> {
        using return_type = typename std::result_of<F(Args...)>::type;
        auto task = std::make_shared<std::packaged_task<return_type()>>(std::bind(std::forward<F>(f), std::forward<Args>(args)...));
        std::future<return_type> res = task->get_future();
        {
            std::unique_lock<std::mutex> lock(queueMutex);
            if (stop) throw std::runtime_error("enqueue on stopped ThreadPool");
            tasks.emplace([task]() { (*task)(); });
        }
        condition.notify_one();
        return res;
    }
private:
    std::vector<std::thread> threads;
    std::queue<std::function<void()>> tasks;
    std::mutex queueMutex;
    std::condition_variable condition;
    bool stop = false;
};
// 使用线程池进行并行排序
ThreadPool pool(std::thread::hardware_concurrency());
std::vector<std::future<void>> futures;
for (const auto& subTask : splitTasks(data)) {
    futures.emplace_back(pool.enqueue([&subTask] {
        std::sort(subTask.begin(), subTask.end());
    }));
}
for (auto& future : futures) {
    future.get();
}

线程同步开销优化
- 思路：减少不必要的同步操作，采用无锁数据结构或乐观锁机制替代传统的互斥锁。例如在一些场景下，使用std::atomic类型的数据结构来避免频繁的锁操作。
- 代码修改方向：如果在并行排序中使用互斥锁保护共享资源，将部分共享资源替换为std::atomic类型。比如共享的计数器int count，改为std::atomic<int> count。

std::atomic<int> count(0);
// 在需要修改计数器的地方
count++;
// 在需要读取计数器的地方
int value = count.load();

星途面试题库

面试题：C++ STL算法sort并行排序的性能优化

知识考点

面试题答案

可能遇到的性能瓶颈

优化思路及代码修改方向