Parallel find_if returns wrong result

[maribu]

Hi!

I get a wrong result from the parallel find_if version in a simple code example. I tried to reproduce the problem in the gtest unit test at test/alg.nonmodifying/alg.gen.find/find.cpp:47, but without success. Maybe it's just me being stupid, but I really cannot figure out whats wrong here.

examples/find_if.cpp

#include <vector>
#include <iostream>
#include <chrono>
#include <random>
#include <experimental/algorithm>

template<typename T, class UnaryPredicate, typename U>
auto myfind(T && policy, const std::vector<U> & values, UnaryPredicate pred)
  -> std::chrono::microseconds
{
    using namespace std;
    using namespace std::experimental; 

    auto start = chrono::high_resolution_clock::now();
    auto result = find_if(policy, begin(values), end(values), pred);
    auto finish = chrono::high_resolution_clock::now();

    if (result != end(values)){ 
        cout << "Value found: " << *result << " at position: "
             << &(*result) - &(*begin(values)) << endl;
    } else {
        cout << "No such value found" << endl;
    }

    return chrono::duration_cast<chrono::microseconds>(finish-start); 
}

int main()
{
    using namespace std;

    vector<int> values(5000000);
    for (size_t i = 0; i < values.size(); i++){
        values[i] = (int)i;
    }

    auto pred = [](int a){
        return false;
    };

    cout << "Using seq:   " 
         << myfind(experimental::parallel::seq, values, pred).count() 
         << " us" << endl;

    cout << "Using par:   " 
         << myfind(experimental::parallel::par, values, pred).count() 
         << " us" << endl;
}

compiled with

clang++ -I../include -std=c++14 -stdlib=libc++ -lc++abi -pthread -o find_if find_if.cpp

gives output

$ ./find_if
Using seq:   No such value found
50152 us
Using par:   Value found: 2500000 at position: 2500000
31982 us

compiled with

g++ -I../include -std=c++14 -pthread -o find_if find_if.cpp

gives output

$ ./find_if
No such value found
Using seq:   69588 us
Value found: 2500000 at position: 2500000
Using par:   40761 us

[t-lutz]

This is indeed a bug. Diffract slices the input range and performs the algorithm on each sub-range. The problem here is that the first range doesn't contain any element satisfying the predicate so returns std::end of the sub-range, which is the first element of the second slice. The reduction operator then takes the iterator with a minimal distance from the start, which is the first element of the second slice.

This requires a change in diffract, I don't have time to fix this right now but i will do it at some point this week. If you want to fix this yourself and submit a PR you are welcome to do so,