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

由于您要求进行全面的解释，并且上一个答案仅涵盖基础知识，因此我很乐意添加更全面的解释。

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

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

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

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

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

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

（如果您不相信此结果，请自己尝试。）

我们可以在这里使用MapReduce，方法是使用int-to-text函数作为map的回调（rsp。std::transform），该函数计算辅音和人声的数量，然后相应地选择左手或右手参数。这里存在一些效率低下的问题，特别是应缓存“比率”，但这是细节。

现在您的问题可能并且可能应该是：我为什么应该关心？毕竟，到目前为止std::transform，std::reduce以这种方式使用eg 和并没有太大的好处，并且您也可以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倍，这不会令我感到惊讶。诚然，这种特殊情况可能会在按条件规则下进行优化，因为C ++实现“知道”整数加法是关联的（几乎见下文）。

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

所有这些，让我补充一下免责声明：性能与效率不一样。每个使用64个内核100ms意味着比使用一个内核1000ms更高的性能，但是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 ints，请确保它们都不大于INT_MAX / 1000或小于INT_MIN / 1000，舍入），或者等效地，使用更大的整数类型，或者，作为绝对的最后手段（因为这既昂贵又难以正确处理），请在reduce回调中添加其他检查。但是，在大多数实际情况下，reduce整数溢出的安全性仅略差于accumulate。