为什么在C++ 17中添加了std :: reduce？

Question

我正在寻找对"返回值"描述的含义的详尽解释std::reduce,根据cppreference.com,它是:

也许在我能够正确地理解"返回值"部分背后的想法之后,我可以更好地确定我应该选择std::reduce的位置std::accumulate.

Answer 1

既然你要求一个彻底的解释,而前面的答案仅涵盖基础知识,那我就冒昧地添加一个更彻底的解释.

std::reduce旨在执行MapReduce编程模型的第二个主要步骤.基本思想是平台(在这种情况下,C++实现)提供这两个原始操作map和reduce,并且程序员为执行"实际工作"的两个中的每一个提供回调操作.

基本上,映射操作的回调将输入值映射到中间值.reduce的回调将两个中间值组合成一个中间值.剩下的最后一个中间值成为整个MapReduce的输出.它本身似乎是一个非常严格的模型,但它仍然有很多应用.

当然,平台必须做更多工作,例如"改组"(通常以组的形式分配输入到不同的处理单元)和调度,但这对应用程序员来说并不重要.

顺便说一句,在C++标准库中,调用"map"操作transform.它在C++ 17中也得到了并行支持,但我稍后会进入并行性.

这是一个简单的例子:假设我们有一个将整数转换为字符串表示的函数.现在,给定一个整数列表,我们希望文本表示包含辅音与人声的最大比例.例如

• 输入:1,17,22,4,8
• 输出:二十二

(如果你不相信这个结果,请亲自试试.)

我们可以通过使用我们的int-to-text函数作为map的回调(rsp.std::transform)来使用MapReduce ,并使用一个计算辅音和人声数量的函数,然后相应地选择左手或右手参数.这里存在一些效率低下的问题,特别是应该缓存"比率",但这些都是细节.

现在你的问题可能也许应该是:我为什么要关心？毕竟,到目前为止,你并没有从使用eg std::transform和std::reduce这种方式获得太多收益,你也可以用std::accumulate它代替后者.当然,给定足够多的输入值,答案是执行策略 - 前两个标准函数模板具有允许隐式并行的重载.但这仍然引出了一个问题,为什么人们会使用MapReduce而不是线程池std::async,还有一堆手写的循环？首先,特别是对于大型向量或其他容器的"纯"计算,没有I/O,编写两个MapReduce回调通常更方便,因为您不必处理输入数据的所有细节.传播到不同的线程然后合并.

其次,MapReduce鼓励以可以非常有效地并行化的方式构建计算的规则.当然,在支持命令式范例的编程语言(如C++)中,您仍然可以通过锁定一堆互斥锁或者以其他方式干扰其他线程来解决问题.但MapReduce范例鼓励编写独立的映射回调.作为一个简单的经验法则,如果这些任务共享数据,那么它应该是只读的,以便它的副本可以同时存储在多个CPU缓存中.编写良好的任务,结合底层算法的高效平台实现,可以扩展到数百甚至数千个CPU内核,如已经常用的MapReduce平台所示(如Apache Hadoop,但仅作为必要例如,而不是无偿的广告).

但问题主要在于std::reduce- 我们仍然可以执行这种高度可扩展的映射,然后运行std::accumulate中间结果,对吗？这就是我们对FrançoisAndrieux之前写过的内容的看法.accumulate执行数学家称之为左折叠的东西.如果您将操作及其操作数视为二叉树,那么这将是一个左倾树,例如添加1,2,3和4:

   +
  / \
  + 4
 / \
 + 3
/ \
1 2

如您所见,每个操作的结果是下一个操作的参数之一.这意味着存在数据依赖性的线性链,这是所有并行性的祸根.要添加一百万个数字,您需要一百万次连续操作,这将阻止单个核心,并且您无法使用其他核心.他们大部分时间都无所事事,通信开销将大大超过计算成本.(它实际上比这更糟糕,因为现代CPU可以在每个时钟执行多个简单计算,但是当存在如此多的数据依赖性时这不起作用,因此大多数ALU或FPU未使用.)

通过解除必须使用左折叠的限制,std::reduce允许平台更有效地使用计算资源.即使你使用单线程重载,平台也可以使用SIMD在不到一百万次操作中添加一百万个整数,并且数据依赖性的数量将大大减少.一个写得很好的整数加法减少10倍的加速不会让我感到惊讶.当然,这个特殊情况可能会在as-if规则下进行优化,因为C++实现"知道"整数加法(几乎,见下文)是关联的.

但正如所提到的,通过支持执行策略,即在大多数情况下,多核并行性,还可以进一步降低.理论上,可以使用平衡的二元运算树.(请记住,如果深度小于2,或者左子树的深度与右子树的深度相差最多1,则树是平衡的.)这样的树只有对数深度.如果我们有一百万个整数,那么最小树深度为20,因此 - 理论上 - 给定足够的内核并且没有通信开销,即使优化的单线程计算,我们也可以实现50,000倍的加速.当然,在实践中,这是一种一厢情愿的想法,但我们仍然可以期待大幅加速.

所有这一切,让我添加一个快速免责声明/提醒,性能与效率不同.使用64个内核,每个100毫秒,意味着比使用一个内核1000毫秒更高的性能,但CPU效率要低得多.另一种说法是,性能是最小化经过时间的效率,但还有其他效率指标 - 使用的总CPU时间,使用的RAM,使用的能量等等.并行MapReduce的主要动机是提供更高的性能.是否减少CPU时间或能耗还不清楚,它很可能会增加峰值RAM的使用.

最重要的是,这里有一些警告.如上所述,reduce如果操作不是关联的或不是可交换的,则是非确定性的.幸运的是,最重要的算术运算如加法和乘法是关联和可交换的,对吗？我们都知道,例如,整数和浮点加法都具有这两个属性.当然,我很滑稽.在C++中,有符号整数加法和浮点加法都不是关联的.对于浮点数,这是由于中间结果的舍入可能存在差异.如果我们选择一个带有两位有效数字的简单十进制浮点格式,并考虑总和10 + 0.4 + 0.4,这很容易看到.如果这是通过正常的C++语法规则作为左折完成的,我们得到(10 + 0.4)+ 0.4 = 10 + 0.4 = 10,因为每次将结果舍入回到10.但是如果我们这样做为10 +(0.4 + 0.4),第一个中间结果为0.8,然后将10 + 0.8向上舍入为11.此外,操作树的高深度会使舍入误差大大放大,因此左侧折叠实际上是一个在准确性方面,人们可以做的最糟糕的事情.有几种方法可以处理这种行为,从排序和分组输入到使用增加的中间精度,但是当涉及到reduce可能根本没有办法获得100%的运行一致性.

另一个可能更令人惊讶的观察是,有符号整数加法在C++中不是关联的.这样做的原因是溢出的可能性,直言不讳地说:(-1) + 1 + INT_MAX.根据正常的语法规则,或者accumulate,结果是INT_MAX.但是如果你使用reduce,这可能会被重写,因为(-1) + (1 + INT_MAX)它包含整数溢出,因此包含未定义的行为.事实上,因为reduce可以任意改变操作数的顺序,如果输入是这样的话,这甚至是正确的{ INT_MAX, -1, 1 }.

我在这里的建议是确保回调reduce不能产生溢出.这可以通过限制允许的输入范围来完成(例如,如果你添加1000 int秒,确保它们都不大于INT_MAX / 1000或小于INT_MIN / 1000,向上舍入),或者等效地,通过使用更大的整数类型,或者,作为绝对的最后手段(因为这既昂贵又难以正确处理),在reduce回调中添加额外的检查.然而,在大多数实际情况中,reduce关于整数溢出的安全性略低于安全溢出accumulate.

Answer 2

std::accumulate迭代在容器上按顺序迭代std:reduce.由于订单无法保证,因此std::reduce引入了额外要求:

如果binary_op不是关联的或不可交换的,则行为是不确定的.如果binary_op修改任何元素或使[first;]中的任何迭代器无效,则行为是未定义的.最后],包括结束迭代器.

但是,std::reduce提供了支持并行化的重载,这些重载是不可用的std::accumulate.std::reduce允许您自动并行化您的操作,前提是它符合上述要求.

Answer 3

• 允许并行是添加 std::reduce 的主要原因

• 还需要确保要与 std::reduce 一起使用的操作既是关联的又是可交换的。

  • 例如，加法是关联的，并且在使用 std::reduce 并行完成累加时给出相同的结果。
    100 + 50 + 40 + 10 = 200 (100 + 40) + (50 + 10) = 200

  • 但是减法不是关联的， std::reduce 可能会给出错误的结果。
    100 - 50 - 40 - 10 = 0 NOT SAME AS (100 - 40) - (50 - 10) = 20

• 效率
  std::vector<double> v(100000, 0.1); double result = std::accumulate(v.begin(), v.end(), 0.0); double result = std::reduce(std::execution::par,v.begin(),v.end()) //Faster