浅谈The C Executors

就在2021年7月6号,Executors提案又有了亿点点的更新。新的Paper, P2300R1(http://open-std.org/JTC1/SC22/WG21/docs/papers/2021/p2300r1.html), 正式命名为std::execution, 相较于The Unified Executor for C++, P0443R14(http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p0443r14), 更系统地阐述了Executors的设计思路;给出了在实现上的更多的说明;删除了Executor Concept,保留并确立了Sender/Receiver/Scheduler模型;给出了库里应有的初始算法集合,并对之前的算法设计有不小的改动;还有更多明确的语义如任务的多发射(multi-shot)和单发射(single-shot),任务的惰性(lazy)与及时(eager)提交,等等。笔者业余时间实践的Excutors库也正好实践完成了P1879R3(http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p1897r3.html)的内容,在std::execution发布的里程碑,借鄙文与大家简单聊聊Executors.

1. Why Executors?

C++一直缺乏可用的并发编程的基础设施,而从C++11以来新引入的基础设施,还有boost,folly等第三方库的改进,都有或多或少的问题和一定的局限性。

1.1 std::async并不async

让时间回到C++11标准的近代。C++11标准正式引入了统一的多线程设施,如<thread><atomic><mutex><conditional_variable>等low level的building blocks. 也引入了发起异步函数调用的接口std::async. 可std::async并不async. 我们借用cppreference上的示例来说明:

    std::async([]{ f(); }); /*a temp std::future<void> is constructed*//* blocked by the destructor of std::future<void> */std::async([]{ g(); });

    以一般理性而言,执行函数g的任务可能在函数f执行的时候,发起调度。但是如上所列代码使用std::async的方式,发起执行函数g的任务调度,一定发生在执行函数f的任务返回之后。原因是:

    1. 第一行std::async创建了一个类型为std::future<void>的临时变量Temp;

    2. 临时变量Temp在开始执行第二行之前发生析构;

    3. std::future<void>的析构函数,会同步地等操作的返回,并阻塞当前线程。

    std::async在初期还会为每一个发起的任务,创建一个新的执行线程。因此,std::async臭名昭著。这里既然提到了std::future,它同样也有不少的问题。

    1.2 Future/Promise模型的演进

    Future/Promise(https://en.wikipedia.org/wiki/Futures_and_promises)模型是一个经典的并发编程模型,它提供给程序员完整的机制来控制程序的同步和异步。C++11中也引入了Future/Promise机制。本质上,Future是我们发起的操作,而Promise则是操作的回调。我们可以通过Future对象等待该操作和获取操作的结果,而Promise对象则负责写入返回值并通知我们。C++中典型的Future/Promise的实现如下图所示:

    如图所示,Future与Promise会有指向同一个共享的状态对象Shared State的共享指针(std::shared_ptr of Shared State),当Promise对象接受到返回值或者错误之后,通过条件变量通知另一端等待的Future对象。Future对象则可以通过Shared State对象中的状态,来判断接收到回调之后是继续处理业务还是处理错误。由于C++标准中的Future/Promise并不能表达任务的前置与后置的依赖关系,该模型很难满足实际的生产环境。

    时间来到的当代,也就是C++14至C++17的时代,有不少类库试图解决这些问题。例如给予Future/Promise表达前置后置依赖的能力(folly::future),还有能够Fork与Join的能力(boost::future). 还有为Future/Promise模型的后置任务,绑定操作Executor等。Future/Promise则改进为如下的实现:

    任务的前置后置关系,我们可以通过在Shared State中新增Continuations对象来表达。如果需要表达Fork,Continuations对象则是一个容器,同时为了保证线程安全,需要为Continuations额外准备一个Mutex对象。为了表达Join,很多库也实现了WhenAll/WhenAny算法。再就是Continuations有时候也需要制定在哪个Execution Context上执行,很多库都抽象出了SemiFutureContinuableFuture等概念。还有SharedFuture可以在多个Execution Context上被等待。

    以上这些优化,让C++中的Future/Promise模型逐步完善,逐渐有了与DAG相同的表达能力。

    1.3 Future/Promise模型的缺点

    虽然Executors提案从12年就开始起草,但早期的Executor提案还并没有提出Sender/Recevier模型,并依然基于Future/Promsie模型来表达任务图的关系。例如,来自Google专注于并发的提案N3378(http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3378.pdf)和来自NVIDIA专注于并行的提案N4406(http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4406.pdf),依旧使用Future/Promise,他们主要把关注点放在了任务调度的抽象上。

    大家在逐步推进提案的进程,一统并发与并行的抽象时,发现Future/Promise模型并不能胜任表达任务图的工作。主要有以下几个原因:

    1. Future/Promise模型总是及时地,积极地提交任务,而没有惰性提交的特性;

    2. 任务图中并不是所有的节点都需要Sync Point,但Shared State都创建了同步对象(CondVar和Mutex);

    3. Shared State总是类型擦除的;

    4. 只能用并发来实现并行。

    首先,惰性提交可以保证我们创建完任务图之后再发起整个任务图的执行。这样可以带来两个好处,一个是创建任务图的过程中可以避免链接Continuations而使用锁,其次就是我们有机会分析依赖关系来应用更为复杂的调度算法。

    问题2,3和4,笔者都归因于类型擦除。类型擦除的实现,使得我们把所有的问题都抛给了程序的运行时,而完全抛弃了C++强大的编译期能力。我们在使用Future/Promise的时候,已经表明了我们只关心Task的返回值:

      std::future<int> f = /* ..... */;

      std::future<int>表达了任意可以返回int类型的操作,因此它不得不丢掉任务图中的类型信息。如Continuation的函数对象类型,前置与后置任务的类型,任务图中的节点是否有同步点,Executor Context的类型等等。而泛滥的使用类型擦除的结果就是抽象不足。而抽象不足则往往会引起语法有效语义无效的实现(例如OOP中的空实现),严重的性能问题还有表达能力的缺失。例如Continuations的类型擦除会丢失inline的优化机会,Shared State的类型擦除会导致问题2与问题4的发生。

      1.4 亟需更为泛型的抽象

      市面上已有的一些基于TaskNode抽象的库,例如Unity的JobSystem和UE4的TaskGraph,还有C++ TaskFlow(https://github.com/taskflow/taskflow),他们都是类型擦除的实现,除了它们支持了惰性提交之外,其他的问题也无法解决。

      问题的答案已经很明朗了,那就是更多的泛型抽象。我们需要一个更为泛型的Executors抽象,来表达任务图,调度策略,并带上执行器的类型信息;使得编译器能够有足够的机会进行激进的优化,使得调度器能够聪明地选择最优的算法,使得执行器能调度到除CPU之外的硬件中执行。这就是下一节将要介绍的The Unified C++ Executors.

      2. The Unified C++ Executors

      The Unified C++ Executors的首要任务,就是将Future/Promise改造得更为Generic. 于是就有了提案中的Sender/Receiver. 这一节主要介绍关于Sender/Receiver模型的一些概念,关于Properties的内容则放到以后的文章详细介绍。

      2.1 Sender/Receiver是泛型的Future/Promise

      笔者在这里就不介绍Sender/Receiver的技术细节了,例如The Receiver Contract(http://open-std.org/JTC1/SC22/WG21/docs/papers/2021/p2300r1.html#receiver-contract)和各种啰嗦的Concepts与接口设计等。笔者尽量以示例和图表来阐述Executors的设计思想。我们先来看一个例子:

        using namespace std::execution;sender auto s = just(1) | transfer(thread_pool_scheduler) | then([](int value){ return 2.0 * value; });
        auto const result = std::this_thread::sync_wait(s);

        s是一个Sender对象,它的类型可能形如:

          then_sender<transfer_sender<just_sender<1>, thread_pool_scheduler_type>, lambda_type>

          它的对象结构如下图:

          再给出一个用folly的Futures库表达的,不那么严谨的等价示例:

            auto f = folly::makeFuture<int>(1) .via(thread_pool_executor) .thenValue([](int value){ return 2.0 * value });auto const result = f.get();

            很显然,f的类型是future<double>,其对象结构如下图:

            我们可以从对象结构中看到,sender对象在类型上保留了全部的类型信息:

            • then算法的传递进入的lambda类型

            • transfer算法的sender类型

            • 线程池的类型

            • just(1)返回的sender的类型

            • 还有它们之间完整的链接关系!

            相比之下,future对象结构则在类型上将这些信息完全丢弃了,只是作为运行期的数据保存于Shared State当中。

            Sender是泛型的Future,Receiver是泛型的Promsie,但sender/receiver模型的表达能力远远高于Future/Promise模型,表达能力的分析我们稍后详细展开来谈。这里值得提及的是,Sender的对象结构,大家是否似曾相识?其实Sender的这种结构,是一个典型的表达式模板(expression template)。表达式模板常用于Linear Algebra Math Library和Lexer的设计与实现中,因为表达式模板天性就是惰性求值(Lazy Evaluation)的,非常适合这些应用场景。Expression Template的设计模式在这里应用到Sender/Receiver模型中,再适合不过了。

            2.2 通过算法来组合Senders

            2.1节中的代码使用了链式的pipe operator. 如果我们用原始的算法来实现,就如下代码所示:

              using namespace std::execution;sender auto s =     then(        transfer(            just(1),             thread_pool_scheduler),         [](int value){ return 2.0 * value; });auto const result = this_thread::sync_wait(s);

              其中just不以任何Sender对象作为输入,而返回一个新的Sender,它是Sender的工厂(Factories). 同样Scheduler也是工厂,因为scheduler.schedule()通常也会返回一个Sender对象。transferthen则以Sender对象,或带有其他对象作为输入,并输出Sender. 这类的算法是Sender的适配器(Adaptor). 最后,std::this_thread::sync_wait则以Sender作为输入,而并不返回一个新的Sender,它是Sender对象的消费者(Consumer). 其中,消费者算法一般都不支持pipe operator,原因是担心对用户造成消费者算法还能继续有后继的误导。

              Executors中的算法,一定属于这三类中的一个。当用户需要根据自己的业务情况,扩展自己的算法时,就需要确定算法属于那一类。并且还需要实现好算法对应的Sender和Receiver. 通常工厂还需要实现自己的Operation State对象,因为工厂创建出的Sender往往都是一切操作的起点。P2300R1中的[4.12](http://open-std.org/JTC1/SC22/WG21/docs/papers/2021/p2300r1.html#design-sender-factories),[4.13]与[4.14],分别介绍了库中默认的三类算法的集合。

              2.3 连接Sender与Receiver

              如果我们要发起Sender对象所代表的任务时,我们需要将Sender与Recevier对象连接在一起。std::execution::connect(sender, receiver)则会返回一个Concepts为operator_state的对象,并通过调用std::execution::start(operation_state)发起任务。例如,std::this_thread::sync_wait`的实现,可能如下代码所示:

                struct sync_wait_t{ template <sender S> auto operator() (S&& s) const{ using promise_t = get_promise_type_t<S>; // get promise type promise_t promise{}; // construct a promise _sync_primitive sync{}; // construct a synchronise primitive object sync_wait_receiver receiver{ promise, sync };
                // start the operation execution::start(execution::connect(forward<S>(s), move(receiver)));
                sync.wait(); // wait on this thread return promise.get_value(); // return value }};

                代码中可以看到std::this_thread::sync_wait中调用连接Sender和Receiver,并发起返回的OperationState的代码。除此之外,还在当前线程上同步地等待发起操作的完成。

                Sender的组合是一个创建任务图的过程,而连接Sender与Receiver则是遍历任务图的过程。整个过程是一个深度优先的遍历,直到遍历至工厂创建的Sender. 前面有提及过,工厂创建的Sender才会在与连接Receiver的时候,创建出可以发起的Operation State对象。那么,还是以文章一开始的代码为例,我们来模拟一下Connect的过程,如下图所示:

                上图展示了Sender表达式与sync_wait_receiver连接过程的每一个步骤,可以较为清晰的看到sync_wait_receiver最终与just_sender连接起来,并创建了Operation State对象。而且,中间的每个算法的Receiver对象,以Sender相反的顺序,保存在各个连接的层级当中。任务启动以后,Operation State就会以Receiver的关系作为顺序,驱动整个任务的执行进程。

                2.4 Sender/Receiver模型与编译期优化

                泛型与惰性提交,给了编译器足够多的信息和机会进行优化。相较于Future/Promise模型,其中最大的优化就是Sender/Receiver可以抹除掉Shared State的运行期开销。我们把2.1节中用Sender/Receiver实现的代码的执行过程,用图表示:

                整个过程实际上只在std::this_thread::sync_wait那里创建了一次Shared State对象。不仅如此,如果大家阅读过libunifex还可以得知,该Shared State是一个栈上对象,并没有堆分配。除此之外,lambda对象也有内联优化的机会,而不会如同Future/Promise中使用std::function进行类型擦除后,而失去内联优化的机会。内联优化,也意味着对于并行算法,还有矢量化加速的优化机会。Future/Promise不仅没有内联优化的机会,而且每一次使用链接Futures的算法API,会实打实地创建一个Shared State,也就是一个Task,这也会给运行期带来不小的开销。实际上,Future/Promise并不适合性能要求很高的生产环境,比如游戏引擎任务框架等。

                Sender/Receiver可以让编译器在编译期将这些负担丢除,提升性能的同时还了增强了表达能力。激进的优化导致的结果是,代码中的s并不是表达了一个任务链,而是一个Monad,真是有函数式那味儿了。Sender/Receiver模型的粒度比Future/Promise的粒度更细。

                3. 未来的展望

                P2300R1的发布,意味着Executors的迭代稳定了下来,未来将不会出现类似P0443这样脑洞大开的重构,希望std::execution能够早日进入TS阶段。std::execution中仍有不少脑洞大开的想法,在提案中悬而未决。

                3.1 Sender/Receiver 与 Awaitable/Coroutine

                笔者在学习[The Ongoing Saga of ISO-C++ Executors](https://www.youtube.com/watch?v=iYMfYdO0_OU)演讲的时候发现了[P1341R0](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p1341r0.pdf).它的核心观点是:

                • Awaitable 可以是一个 Sender

                • Coroutine 可以是一个 Receiver

                在我们的合理封装下,协程也能够统一起来:

                  auto const result = this_thread::sync_wait(s);auto const result = this_fiber::sync_wait(s);

                  3.2 异构计算

                  标准委员会的大佬们,不遗余力地尝试使用泛型来设计Executors,还有一个原因是为了布局异构计算。Execution Context(http://open-std.org/JTC1/SC22/WG21/docs/papers/2021/p2300r1.html#design-contexts)与Scheduler(http://open-std.org/JTC1/SC22/WG21/docs/papers/2021/p2300r1.html#design-schedulers)等概念的抽象,可以让Executor不拘泥于只是CPU Thread. 它可以是一个常规的CPU Thread,可以是一个GPU,甚至是一个Remote System. 有且只有泛型,才能胜任这个工作,试问被Future中std::function类型擦出的函数对象,如何进行矢量化加速,如何优雅地调度到GPU上?泛型可以让代码的编译期上下文完整地保留到最后,也为未来创造了更多可能。

                  4. 引用参考

                  1. P2300R1 - std::execution(http://open-std.org/JTC1/SC22/WG21/docs/papers/2021/p2300r1.html#design-schedulers);

                  2. P0443R14 - The Unified Executors Proposal for C++(http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p0443r14);

                  3. N3378 - A preliminary proposal for work executors(http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3378.pdf);

                  4. N4406 - Parallel Algorithms Need Executors(http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4406.pdf);

                  5. P1341R0 - UNIFING ASYNCHRONOUS APIs IN C++ STANDARD LIBRARY(http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p1341r0.pdf);

                  6. P1897R3 - Towards C++23 executors: A proposal for an initial set of algorithms(http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p1897r3.html);

                  7. P1054R0 - A Unified Futures Proposal for C++(http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p1054r0.html);

                  8. Facebook - Lib Unified Executor(https://github.com/facebookexperimental/libunifex);

                  9. Youtube - The Ongoing Saga of ISO-C++ Executors(https://www.youtube.com/watch?v=iYMfYdO0_OU).

                  (0)

                  相关推荐

                  • SpringBoot为异步任务规划线程池及实现定时任务

                    上一篇文章中我们学会了如何使用异步的方式去执行任务,在实际的开发当中,应用服务的并发量比较大时,频繁的创建和销毁线程是非常消耗性能和资源的,并且一个进程能够创建的线程数量也是有上限的.为了解决这些问题 ...

                  • cargo expand用于查看被宏隐藏的代码

                    目录 一,目前这个需要安装nightly的toolchain,rustup toolchain install nightly-x86_64-unknown-linux-gnu 二,用这个命令安装:c ...

                  • 浅谈乡村治理模式发生了哪些变化?

                    随着乡村现代化的发展,越来越多的乡村走上了建设数字乡村的道路,从传统的乡村治理到使用互联网数字化治理的模式,乡村的风貌和农民的生活也发生了巨大的变化,接下来就让我们一起来了解一下乡村治理模式到底发生了 ...

                  • 汽车是怎么开发出来的?浅谈汽车开发流程

                    许良  汽车话题下的优秀答主你知道汽车是怎么开发出来的吗?你的脑海中很可能浮现出来这样一个画面:一个非常有艺术气息的设计师,在草图上帅气的描绘着看起来非常犀利的线条.对,但不全对.对于汽车工程师的我而 ...

                  • 浅谈办公室装修的发展前景和趋势

                    未来办公室装修的发展趋势会是怎样的?这是这个行业未来前景的重要话题.在这样一个新时代里,所有的事物都会以最新颖的方式出发.科技的发展也让每个行业都转遍了方向,同时对行业的要求和品质也有了更高的要求. ...

                  • 颧骨浅谈

                    ​骨过高 颧骨过于发达的人,单从脸部看上去就给人以高傲的感觉.而他们也得确有这种个性,常固执已见,虚张声势或显得自负是他们的特色.在工作上,也不愿意接受他人的忠告,总认为自己的就是最好的,这一点不利于 ...

                  • 浅谈地龙在治疗咳喘中的运用

                    浅谈地龙在治疗咳喘中的运用 笔者从事中医临床工作十多年来,在运用地龙治疗痰湿壅肺型.肺络瘀阻型.心肺两虚型.肾不纳气型的咳喘上有了一些心得,现介绍如下.   咳喘是现代医学中呼吸系统.心血管系统疾病的 ...

                  • [鉴史释疑]曹操是英雄还是汉贼 浅谈曹操的英雄之处

                    时间:2021-04-16 08:30:03    来源:本站(吾爱诗经网)整理       作者:魁哥说历史 在不同人眼里,曹操的形象和品格都是不一样的.有人觉得曹操是汉贼,但也有人说曹操是英雄,其 ...

                  • 油车的教学真能开电车? 从驾校角度浅谈电动汽车事故

                    可能是因为电动汽车正处汽车变革的"风口"中,所以因为电动汽车造成的事故在今年都能成为热搜榜的常客,刨去产品本身的原因不谈,在驾校的培训体系中有没有需要提升的部分? 我们都知道目前驾 ...

                  • ​浅谈中医:心、肝、脾、肺、肾五脏异常会出现这些症状【推荐好文】

                    在中医里,心.肝.脾.肺.肾这五脏不仅仅是身体器官,更是人体养生的最终落脚点.在繁忙的社会环境中,五脏承受了许多本不应该承受的负担,一些不良的习惯往往在潜移默化中伤害着五脏以及我们的身体健康.那么在这 ...

                  • 瓷器鉴定基础知识(3):浅谈瓷器鉴定的基本方法

                    古代瓷器,是历史的产物,其上会有历史的烙印.它们犹如文学作品一样,有其产生的时代背景,因此,鉴定一件瓷器就如同鉴赏一本书籍,需要从它的内容去进行解读和分析.瓷器的内容,不以文字形式呈现,而是以它的造型 ...