在具有并行执行策略的<numeric>中使用std::Reduce()中的BinaryOp

2022-02-25 00:00:00 multithreading visual-c++ reduce c++ c++17

我在使用<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);

相关文章