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

Question

我正在寻找对 std::reduce 的“返回值”描述的含义的彻底解释，根据 cppreference.com，它是：

也许在我正确理解本节之后，我可以更好地确定何时应该选择 std::reduce 而不是 std::accumulate 。

原文由 Aria Pahlavan 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

由于您要求进行彻底的解释，而先前的答案仅涵盖基础知识，因此我冒昧地添加更详尽的解释。

std::reduce 旨在执行 MapReduce 编程模型 的第二个主要步骤。基本思想是平台（在本例中为 C++ 实现）提供了这两个原始操作 map 和 reduce，程序员为执行“实际工作”的两者中的每一个提供回调操作。

基本上，映射操作的回调将输入值映射到中间值。 reduce 的回调将两个中间值合并为一个中间值。最后剩下的中间值成为整个 MapReduce 的输出。它本身似乎是一个非常严格的模型，但它仍然具有广泛的应用范围。

当然，平台必须做更多的事情，例如“洗牌”（将输入，通常以组的形式，分配到不同的处理单元）和调度，但这对应用程序程序员来说并不重要。

顺便说一句，在 C++ 标准库中，“映射”操作称为 transform 。它在 C++17 中也获得了并行性支持，但我稍后会介绍并行性。

这是一个虚构的例子：假设我们有一个将整数转换为字符串表示的函数。现在，给定一个整数列表，我们想要包含最大比例的辅音与人声的文本表示。例如

• 输入：1、17、22、4、8
• 输出：二十二

（如果您不相信这个结果，请自行尝试。）

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

现在你的问题可能而且可能应该是：我为什么要关心？毕竟，到目前为止，您并没有从以这种方式使用例如 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çois Andrieux 之前所写的内容的地方。 accumulate 执行数学家所说的左折叠。如果您将操作及其操作数视为二叉树，那么这将是一棵左倾树，例如添加 1、2、3 和 4：

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

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

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

但正如前面提到的，reduce 比这更进一步，它支持执行策略，即在大多数情况下是多核并行。理论上，可以使用平衡的二叉树操作。 （请记住，如果深度小于 2，或者左子树的深度与右子树的深度最多相差 1，则树是平衡的。）这样的树只有对数深度。如果我们有一百万个整数，最小的树深度是 20，所以——理论上——给定足够的内核并且没有通信开销，我们甚至可以比优化的单线程计算实现 50,000 倍的加速。当然，在实践中，这是一厢情愿的想法，但我们仍然可以期待大幅加速。

说了这么多，让我快速添加一个免责声明/提醒，即性能与效率不同。使用 64 个内核每个 100 毫秒意味着比使用一个内核 1,000 毫秒更高的性能，但 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 s，请确保它们都不大于 INT_MAX / 1000 或小于 INT_MIN / 1000 ，向上取整），例如，或者等效地，使用更大的整数类型，或者，作为绝对最后的手段（因为这既昂贵又难以正确处理），在 reduce 中进行额外检查 --- 回调。在大多数实际情况下， reduce 在整数溢出方面仅比 accumulate 安全性稍差。

原文由 Arne Vogel 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

std::accumulate 按顺序迭代容器，而 std:reduce 可能不会。由于订单不保证， std::reduce 引入了额外的要求：

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

但是， std::reduce 提供了支持并行化的重载，这些重载在 std::accumulate 中不可用。 std::reduce 允许您自动并行化您的操作，前提是它满足上述要求。

原文由 François Andrieux 发布，翻译遵循 CC BY-SA 3.0 许可协议