为什么在 C++17 中添加了 std::reduce？
Why has std::reduce been added in C++17?
我正在寻找 std::reduce 的“Return 值”描述含义的详尽解释，根据 cppreference.com，它是：
也许在我正确理解了这一部分之后，我可以更好地确定什么时候应该选择 std::reduce 而不是 std::accumulate。
std::accumulate iterates over the container in order where as std:reduce 可能不会。因为不能保证顺序，std::reduce 引入了额外的要求：
The behavior is non-deterministic if binary_op is not associative or not commutative. The behavior is undefined if binary_op modifies any element or invalidates any iterator in [first; last], including the end iterator.
但是，std::reduce 提供了支持并行化的重载，std::accumulate 不提供这些重载。 std::reduce 允许您自动并行化您的操作，前提是它满足上述要求。
既然你要求一个详尽的解释，而之前的回答只涵盖基础知识，我冒昧地添加一个更详尽的解释。
std::reduce 旨在执行 MapReduce programming model 的第二个主要步骤。基本思想是平台（在本例中为 C++ 实现）提供 map 和 reduce 这两个原始操作，程序员为执行 "actual work".
的两个中的每一个提供回调操作。
基本上，映射操作的回调将输入值映射到中间值。 reduce 的回调将两个中间值合并为一个中间值。剩下的最后一个中间值成为整个 MapReduce 的输出。它本身似乎是一个非常受限的模型，但它仍然具有广泛的应用范围。
平台当然要做更多的事情，例如"shuffling"（将输入分配给不同的处理单元，通常是分组分配）和调度，但这对应用程序员来说很少关心。
顺便说一句，在C++标准库中，"map"操作被称为transform。它也获得了 C++17 中的并行性支持，但我稍后会介绍并行性。
这是一个虚构的示例：假设我们有一个将整数转换为字符串表示形式的函数。现在，给定一个整数列表，我们想要包含最大辅音与主音比例的文本表示。例如
- 输入：1、17、22、4、8
- 输出：二十二
（不信这个结果你自己试试吧）
我们可以在这里使用 MapReduce，方法是使用我们的 int-to-text 函数作为映射的回调（rsp。std::transform），以及一个计算辅音和人声数量的函数，然后选择相应地左手或右手参数。这里有一些低效之处，特别是 "ratio" 应该被缓存，但这些是细节。
现在你的问题可能而且可能应该是：我为什么要关心？毕竟，到目前为止，您并没有从使用例如std::transform 和 std::reduce 这样，您也可以使用 std::accumulate 代替后者。 给定足够多的输入值，答案当然是执行策略——前两个标准函数模板具有允许隐式并行的重载。但这仍然回避了一个问题，为什么人们会使用 MapReduce 而不是线程池或 std::async，以及一堆手写循环？首先，特别是对于大型向量或其他容器的 "pure" 计算，没有 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
如您所见，每个操作的结果是下一个操作的参数之一。这意味着存在一个线性的数据依赖链，这是所有并行性的祸根。 100万个数相加，需要100万次连续运算，会阻塞一个核，无法使用额外的核。他们大部分时间无事可做，通信开销将大大超过计算成本。 （实际上比这更糟糕，因为现代 CPU 可以每个时钟执行多个简单计算，但是当存在如此多的数据依赖性时这不起作用，因此大多数 ALUs 或 FPU 未被使用。 )
通过取消必须使用左折叠的限制，std::reduce 允许平台更有效地利用计算资源。 即使您使用单线程重载，例如，平台也可以使用 SIMD 在远少于一百万次的操作中添加一百万个整数，并且数据依赖的数量将是大大减少。一个写得很好的整数加法 reduce 的 10 倍加速不会让我感到惊讶。诚然，这个特殊的特殊情况可能会根据 as-if 规则进行优化，因为 C++ 实现 "knows" 整数加法是（几乎，见下文）关联的。
但如前所述，通过支持执行策略，即在大多数情况下支持多核并行性，reduce 比这更进一步。理论上，可以使用平衡的二叉运算树。 （请记住，如果深度小于二，或者左子树的深度与右子树的深度最多相差 1，则树是平衡的。）这样的树只有对数深度。如果我们有 100 万个整数，最小树深度为 20，那么 - 理论上 - 如果有足够的核心并且没有通信开销，我们甚至可以在优化的单线程计算上实现 50,000 倍的加速。当然，在实践中，这是一厢情愿的想法，但我们仍然可以期待大幅加速。
综上所述，让我快速补充一点 disclaimer/reminder 性能与效率不同。使用 64 个内核每个 100ms 意味着比使用一个内核 1,000ms 性能更高，但 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% 运行- for-运行一致性。
另一个可能更令人惊讶的观察结果是有符号整数加法在 C++ 中不是关联的。这样做的原因是有溢出的可能，说白了就是：(-1) + 1 + INT_MAX。根据正常的语法规则，或 accumulate，结果是 INT_MAX。但是，如果您使用 reduce，这可能会被重写为 (-1) + (1 + INT_MAX)，其中包含整数溢出，因此 未定义的行为 。事实上，因为 reduce 可以任意改变操作数的顺序，即使输入是 { INT_MAX, -1, 1 }.
也是如此
我在这里的建议是确保对 reduce 的回调不会产生溢出。这可以通过限制允许的输入范围来完成（例如，如果您添加 1000 ints，请确保其中 none 大于 INT_MAX / 1000 或小于 INT_MIN / 1000 ，四舍五入），例如，或者等效地，通过使用更大的整数类型，或者，作为绝对的最后手段（因为这既昂贵又难以正确处理），在 reduce 回调中进行额外检查.然而，在大多数实际情况下，reduce 在整数溢出方面的安全性仅略低于 accumulate。
允许并行是添加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
我正在寻找 std::reduce 的“Return 值”描述含义的详尽解释，根据 cppreference.com，它是：
也许在我正确理解了这一部分之后，我可以更好地确定什么时候应该选择 std::reduce 而不是 std::accumulate。
std::accumulate iterates over the container in order where as std:reduce 可能不会。因为不能保证顺序，std::reduce 引入了额外的要求：
The behavior is non-deterministic if binary_op is not associative or not commutative. The behavior is undefined if binary_op modifies any element or invalidates any iterator in [first; last], including the end iterator.
但是，std::reduce 提供了支持并行化的重载，std::accumulate 不提供这些重载。 std::reduce 允许您自动并行化您的操作，前提是它满足上述要求。
既然你要求一个详尽的解释，而之前的回答只涵盖基础知识，我冒昧地添加一个更详尽的解释。
std::reduce 旨在执行 MapReduce programming model 的第二个主要步骤。基本思想是平台（在本例中为 C++ 实现）提供 map 和 reduce 这两个原始操作，程序员为执行 "actual work".
基本上，映射操作的回调将输入值映射到中间值。 reduce 的回调将两个中间值合并为一个中间值。剩下的最后一个中间值成为整个 MapReduce 的输出。它本身似乎是一个非常受限的模型，但它仍然具有广泛的应用范围。
平台当然要做更多的事情，例如"shuffling"（将输入分配给不同的处理单元，通常是分组分配）和调度，但这对应用程序员来说很少关心。
顺便说一句，在C++标准库中，"map"操作被称为transform。它也获得了 C++17 中的并行性支持，但我稍后会介绍并行性。
这是一个虚构的示例：假设我们有一个将整数转换为字符串表示形式的函数。现在，给定一个整数列表，我们想要包含最大辅音与主音比例的文本表示。例如
- 输入：1、17、22、4、8
- 输出：二十二
（不信这个结果你自己试试吧）
我们可以在这里使用 MapReduce，方法是使用我们的 int-to-text 函数作为映射的回调（rsp。std::transform），以及一个计算辅音和人声数量的函数，然后选择相应地左手或右手参数。这里有一些低效之处，特别是 "ratio" 应该被缓存，但这些是细节。
现在你的问题可能而且可能应该是：我为什么要关心？毕竟，到目前为止，您并没有从使用例如std::transform 和 std::reduce 这样，您也可以使用 std::accumulate 代替后者。 给定足够多的输入值，答案当然是执行策略——前两个标准函数模板具有允许隐式并行的重载。但这仍然回避了一个问题，为什么人们会使用 MapReduce 而不是线程池或 std::async，以及一堆手写循环？首先，特别是对于大型向量或其他容器的 "pure" 计算，没有 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
如您所见，每个操作的结果是下一个操作的参数之一。这意味着存在一个线性的数据依赖链，这是所有并行性的祸根。 100万个数相加，需要100万次连续运算，会阻塞一个核，无法使用额外的核。他们大部分时间无事可做，通信开销将大大超过计算成本。 （实际上比这更糟糕，因为现代 CPU 可以每个时钟执行多个简单计算，但是当存在如此多的数据依赖性时这不起作用，因此大多数 ALUs 或 FPU 未被使用。 )
通过取消必须使用左折叠的限制，std::reduce 允许平台更有效地利用计算资源。 即使您使用单线程重载，例如，平台也可以使用 SIMD 在远少于一百万次的操作中添加一百万个整数，并且数据依赖的数量将是大大减少。一个写得很好的整数加法 reduce 的 10 倍加速不会让我感到惊讶。诚然，这个特殊的特殊情况可能会根据 as-if 规则进行优化，因为 C++ 实现 "knows" 整数加法是（几乎，见下文）关联的。
但如前所述，通过支持执行策略，即在大多数情况下支持多核并行性，reduce 比这更进一步。理论上，可以使用平衡的二叉运算树。 （请记住，如果深度小于二，或者左子树的深度与右子树的深度最多相差 1，则树是平衡的。）这样的树只有对数深度。如果我们有 100 万个整数，最小树深度为 20，那么 - 理论上 - 如果有足够的核心并且没有通信开销，我们甚至可以在优化的单线程计算上实现 50,000 倍的加速。当然，在实践中，这是一厢情愿的想法，但我们仍然可以期待大幅加速。
综上所述，让我快速补充一点 disclaimer/reminder 性能与效率不同。使用 64 个内核每个 100ms 意味着比使用一个内核 1,000ms 性能更高，但 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% 运行- for-运行一致性。
另一个可能更令人惊讶的观察结果是有符号整数加法在 C++ 中不是关联的。这样做的原因是有溢出的可能，说白了就是：(-1) + 1 + INT_MAX。根据正常的语法规则，或 accumulate，结果是 INT_MAX。但是，如果您使用 reduce，这可能会被重写为 (-1) + (1 + INT_MAX)，其中包含整数溢出，因此 未定义的行为 。事实上，因为 reduce 可以任意改变操作数的顺序，即使输入是 { INT_MAX, -1, 1 }.
我在这里的建议是确保对 reduce 的回调不会产生溢出。这可以通过限制允许的输入范围来完成（例如，如果您添加 1000 ints，请确保其中 none 大于 INT_MAX / 1000 或小于 INT_MIN / 1000 ，四舍五入），例如，或者等效地，通过使用更大的整数类型，或者，作为绝对的最后手段（因为这既昂贵又难以正确处理），在 reduce 回调中进行额外检查.然而，在大多数实际情况下，reduce 在整数溢出方面的安全性仅略低于 accumulate。
允许并行是添加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