在 <numeric> 中的 std::reduce() 中使用 BinaryOp 和并行执行策略

Question

我无法从 <numeric> STL header.

中使用 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；
WindowsSDK版本：10.0.18362.0；
平台工具集：Visual Studio 2019 (v142)
C++ 语言标准：预览 - 来自最新 C++ 工作草案的特性 (/std:c++latest)
电脑：Dell XPS 9570 i7-8750H CPU @ 2.20GHz, 16GB RAM OS: Windows 10 64bit

Answer 1

来自 cppreference：“如果 binary_op 不是关联的或不可交换的，则行为是不确定的。”你观察到的是什么；你的不是可交换的。

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

你真正想要的是std::transform_reduce。如

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

在 <numeric> 中的 std::reduce() 中使用 BinaryOp 和并行执行策略

Using BinaryOp within std::reduce() from <numeric> with parallel execution policy

c++

reduce

multithreading

visual-c++

c++17