基于C++/P2300发送者/接收者模型的递归并行算法实现问询

核心原则：规避类型擦除，基于发送者组合 #

首先解决你提到的any_sender_of<>类型擦除的性能问题——正确的做法是让递归函数返回具体的发送者类型，而非擦除后的通用类型。C++20及之后的自动返回类型推导（auto）可以完美支持这一点，编译器会为每个递归实例生成对应发送者类型，完全避免堆分配和类型擦除带来的开销。

同时，要将函数参数从调度器改为发送者（或可转换为发送者的调度器），这样能直接与其他发送者适配器组合。比如接收stdexec::scheduler auto参数时，用stdexec::schedule(scheduler)将其转换为发送者，再进行后续逻辑组合。

结构化并行的正确姿势：复用async_scope（未来的counting_scope） #

针对结构化并行中任务生命周期的问题，核心是在单个递归层级的根任务中创建async_scope，并向同一个scope提交所有子任务，而非在每个递归步骤创建独立的scope。这样能保证所有子任务完成前，当前层级的根任务不会结束，符合结构化并行“父任务等待所有子任务完成”的核心要求。

递归快速排序的示例实现 #

以下是基于stdexec的正确实现框架：

#include <stdexec/execution.hpp>
#include <algorithm>
#include <vector>
#include <random>

namespace exec = stdexec;

template <exec::scheduler Sched, typename RandomIt>
auto parallel_quicksort(Sched sched, RandomIt first, RandomIt last)
{
    // 基准情况：区间长度小于阈值，切换串行排序避免调度开销
    if (last - first <= 1000) {
        return exec::then(exec::schedule(sched), [=] {
            std::sort(first, last);
        });
    }

    // 选择基准元素并完成分区
    auto pivot = *std::next(first, (last - first) / 2);
    auto mid1 = std::partition(first, last, [pivot](const auto& elem) {
        return elem < pivot;
    });
    auto mid2 = std::partition(mid1, last, [pivot](const auto& elem) {
        return !(pivot < elem);
    });

    // 在当前层级创建async_scope，提交左右子任务
    return exec::let_value(exec::schedule(sched), [=](auto) {
        exec::async_scope scope;

        // 提交左半区递归任务
        scope.spawn(parallel_quicksort(sched, first, mid1));
        // 提交右半区递归任务
        scope.spawn(parallel_quicksort(sched, mid2, last));

        // 等待所有子任务完成后返回
        return scope.join();
    });
}

// 使用示例
int main()
{
    std::vector<int> vec(1000000);
    std::iota(vec.begin(), vec.end(), 0);
    std::shuffle(vec.begin(), vec.end(), std::mt19937{std::random_device{}()});

    exec::sync_wait(parallel_quicksort(exec::thread_pool{}, vec.begin(), vec.end()));
}

关键细节说明 #

• 避免递归层级重复创建async_scope：上述实现中，每个递归层级仅创建一次async_scope，所有子任务都提交到该scope中，既符合结构化并行的任务树结构，也避免了死锁风险。
• 发送者链式组合：函数接收调度器后先转换为发送者，再通过then、let_value等适配器组合逻辑，确保整个流程基于发送者链式调用，可无缝与其他发送者适配器（如when_all、transform）组合。
• 基准情况的串行优化：当区间长度较小时切换为串行排序，是分治并行算法的通用优化，能避免递归和任务调度的额外开销。

死锁问题的核心解决思路 #

你提到的“每个递归步骤创建独立async_scope并sync_wait导致死锁”，本质是因为sync_wait会阻塞当前线程，若线程池所有线程都被这类阻塞操作占用，就无法执行子任务，最终引发死锁。正确的做法是永远不要在发送者的执行流程中调用sync_wait，而是通过let_value、join等发送者适配器来组合等待逻辑，让执行器异步处理任务等待。

内容的提问来源于stack exchange，提问作者akreuzkamp