在具有并行执行策略的&lt；numeric&gt；中使用std：：Reduce()中的BinaryOp [英] Using BinaryOp within std::reduce() from <numeric> with parallel execution policy

问题描述

我在使用<numeric>STL标头中的std::reduce()函数时找不到问题。

由于我找到了解决方法，我将显示第一个预期行为：

uint64_t f(uint64_t n)
{
   return 1ull; 
}

uint64_t solution(uint64_t N) // here N == 10000000
{
    uint64_t r(0);

    // persistent array of primes
    const auto& app = YTL::AccumulativePrimes::global().items(); 

    auto citEnd = std::upper_bound(app.cbegin(), app.cend(), 2*N);
    auto citBegin = std::lower_bound(app.cbegin(), citEnd, N);

    std::vector<uint64_t> v(citBegin, citEnd);

    std::for_each(std::execution::par,
                    v.begin(), v.end(),
                    [](auto& p)->void {p = f(p); });

    r = std::reduce(std::execution::par, v.cbegin(), v.cend(), 0);
    return r; // here is correct answer: 606028
}

但是如果我想避免中间向量，而是在reduce()本身中就地应用二元运算符，也是并行的，它每次都会给我一个不同的答案：

uint64_t f(uint64_t n)
{
   return 1ull;
}

uint64_t solution(uint64_t N) // here N == 10000000
{
    uint64_t r(0);

    // persistent array of primes
    const auto& app = YTL::AccumulativePrimes::global().items(); 

    auto citEnd = std::upper_bound(app.cbegin(), app.cend(), 2*N);
    auto citBegin = std::lower_bound(app.cbegin(), citEnd, N);

    // bug in parallel reduce?! 
    r = std::reduce(std::execution::par,
                    citBegin, citEnd, 0ull,
                    [](const uint64_t& r, const uint64_t& v)->uint64_t { return r + f(v); });
    return r; // here the value of r is different every time I run!! 
}

有人能解释一下为什么后一种用法是错误的吗？

---

我使用的是MS C++编译器cl.exe：版本19.28.29333.0；
Windows SDK版本：10.0.18362.0；
平台工具集：Visual Studio 2019(V142)
C++语言标准：预览-来自最新C++工作草案的功能(/std：C++LATEST)
计算机：Dell XPS 9570 i7-8750H CPU@2.20 GHz，16 GB RAM操作系统：Windows 10 64位

推荐答案

来自cppreference：binary_op如果binary_op不是关联的或非可交换的，则行为是不确定的。&q；这是您观察到的；您的行为不是可交换的。

您的二元操作假设第一个参数始终是累加器，第二个参数始终是元素值。通常情况并非如此。例如，最简单的并行缩减形式是将范围一分为二，分别缩减，然后使用相同的操作合并结果-在您的情况下，这将丢失一半的值的跟踪。

---

您真正需要的是std::transform_reduce。如

r = std::transform_reduce(
        std::execution::par, citBegin, citEnd, 0ull,
        std::plus<uint64_t>{}, f);

这篇关于在具有并行执行策略的&lt；numeric&gt；中使用std：：Reduce()中的BinaryOp的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！