t-lutz / parallelstl Goto Github PK

View Code? Open in Web Editor NEW

25.0 25.0 5.0 222 KB

Implementation of n3554, a proposal to include parallelized versions of the STL algorithms into the C++ standard.

C++ 98.53% CMake 1.47%

parallelstl's People

Contributors

Stargazers

Watchers

Forkers

ivo-leonov mumlax zandry reinventorsofthewheel siwenzhang

parallelstl's Issues

Compatibility with libc++

Thanks for your fast fix for clang. I'd like to annoy you again: ParallelSTL
does not compile against libc++ (http://libcxx.llvm.org):

clang++ -std=c++11 -stdlib=libc++ -lc++abi -pthread prime.cpp -o prime

fails with

prime.cpp:74:46: error: no member named 'parallel' in namespace
      'std::experimental'
    auto time_seq = find_prime(experimental::parallel::seq, numbers);
                               ~~~~~~~~~~~~~~^
prime.cpp:78:46: error: no member named 'parallel' in namespace
      'std::experimental'
    auto time_par = find_prime(experimental::parallel::par, numbers);
                               ~~~~~~~~~~~~~~^
prime.cpp:86:47: error: no member named 'parallel' in namespace
      'std::experimental'
    auto time_seq = count_prime(experimental::parallel::seq, numbers);
                                ~~~~~~~~~~~~~~^
prime.cpp:90:47: error: no member named 'parallel' in namespace
      'std::experimental'
    auto time_par = count_prime(experimental::parallel::par, numbers);
                                ~~~~~~~~~~~~~~^
prime.cpp:100:30: error: no member named 'parallel' in namespace
      'std::experimental'
    replace_if(experimental::parallel::seq, begin(copy), end(copy), isPrime, 0);
               ~~~~~~~~~~~~~~^
prime.cpp:107:30: error: no member named 'parallel' in namespace
      'std::experimental'
    replace_if(experimental::parallel::par, begin(copy), end(copy), isPrime, 0);
               ~~~~~~~~~~~~~~^

Obviously #include <experimental/algorithm> is already used by libc++. Also
e. g. in include/experimental/bits/parallel/algos/par/sort.h the function
diffract expects a functor as third argument, but std::sort is a template in
libc++. I'm not sure what a good fix would be here, but simply writing a wrapper
functor which calls std::sort would work as a quick and dirty solution.

Thanks in advance!

diffract requirements

diffract should require Callable instead of FunctionObject

Keep up with C++14

std::equal will have two new prototypes in C++14, which are not part of the current implementation:

#!c++
template< class InputIt1, class InputIt2 >
bool equal( InputIt1 first1, InputIt1 last1, 
            InputIt2 first2, InputIt2 last2 );

template< class InputIt1, class InputIt2, class BinaryPredicate >
bool equal( InputIt1 first1, InputIt1 last1, 
            InputIt2 first2, InputIt2 last2,
            BinaryPredicate p );

Bitbucket: https://bitbucket.org/tlutz/n3554-aka-n3850-n3960-implementation/issue/4
Originally Reported By: Thibaut Lutz
Originally Created At: 2014-04-12T16:51:01.069

Is_heap implementation is flawed in certain cases

Correct me if I'm wrong, but I don't think the parallel is_heap will work. I can't actually compile the code to test it due to some weird constexpr errors in execution_policy, but here's what I believe is wrong:

Say you have the heap: 9 8 6 7 4 5 2 0 3 1 , which when visualized looks like

Now say you call parallelized is_heap, and your heap is split into 4 separate partitions. These become

9 8 6 7 4 5 2 0 3 1

The problem is that 2 0 3 is not a max heap, but the algorithm will call std::is_heap on that range. the partitions are treating the beginning part as the head node, which is wrong in this case. The first two partitions got lucky because they chose a node which happened to have children, but in the case of a non-complete heap tree this algorithm would fail.

std::is_heap_until not in the proposal

std::is_heap is in the table 1 of n3960, but not std::is_heap_until.

Modify experimental::parallel::rotate to support generic ForwardIterators

The current sequential implementation of rotate does only work with RandomAccess Iterators, as the return value is computed using + and -.
This should be extended to support generic ForwardIterators.

Background:
Since C++11 the the rotate function returns the iterator marking the split location after the rotate was performed.

Bitbucket: https://bitbucket.org/tlutz/n3554-aka-n3850-n3960-implementation/issue/2
Originally Reported By: Michel Steuwer
Originally Created At: 2014-02-26T16:11:17.369

Add std::uninitialized_*

The following are missing from the headers, the policies and the test suite:

Bitbucket: https://bitbucket.org/tlutz/n3554-aka-n3850-n3960-implementation/issue/7
Originally Reported By: Thibaut Lutz
Originally Created At: 2014-04-15T15:33:10.196

Add std::is_heap

std::is_heap is not part of the algorithm header and is not part of any policy.

It also doesn't have a test case.

Bitbucket: https://bitbucket.org/tlutz/n3554-aka-n3850-n3960-implementation/issue/6
Originally Reported By: Thibaut Lutz
Originally Created At: 2014-04-15T15:25:54.472

Missing test case for is_sorted_until

Bitbucket: https://bitbucket.org/tlutz/n3554-aka-n3850-n3960-implementation/issue/3
Originally Reported By: Thibaut Lutz
Originally Created At: 2014-02-26T17:18:07.174

for_each_n now returns an iterator

for_each_n returned the function in the older versions of the proposal. Now it returns an iterator.

Remove garbage files

The files in parallel/bits are mostly useless, since the business logic has been delegated to the policies.
If no code needs to be reused, they should be deleted

Bitbucket: https://bitbucket.org/tlutz/n3554-aka-n3850-n3960-implementation/issue/1
Originally Reported By: Thibaut Lutz
Originally Created At: 2014-02-26T15:04:19.461

Parallel find_if returns wrong result

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

Functions in <numeric> removed

The existing functions std::accumulate and std::inner_product in the numeric header seem to have disappeared from the proposal, but are still present in the policy definition.

Bitbucket: https://bitbucket.org/tlutz/n3554-aka-n3850-n3960-implementation/issue/8
Originally Reported By: Thibaut Lutz
Originally Created At: 2014-04-15T16:59:50.054

return value of std::fill_n

std::fill_n returns an iterator since c++11.

Bitbucket: https://bitbucket.org/tlutz/n3554-aka-n3850-n3960-implementation/issue/9
Originally Reported By: Thibaut Lutz
Originally Created At: 2014-04-15T19:01:02.566

Compiling with clang fails

Compiling examples/prime.cpp with

clang -I../include -pthread -std=c++14 -o prime prime.cpp

fails with:

In file included from prime.cpp:5:
In file included from ../include/experimental/algorithm:7:
In file included from ../include/experimental/execution_policy:134:
../include/experimental/bits/parallel/policy_sequential.h:536:3: error: default initialization of an object of const type 'const class sequential_execution_policy' without a user-provided default constructor
} seq ; //
  ^
     {}
In file included from prime.cpp:5:
In file included from ../include/experimental/algorithm:7:
In file included from ../include/experimental/execution_policy:135:
../include/experimental/bits/parallel/policy_parallel.h:536:3: error: default initialization of an object of const type 'const class parallel_execution_policy' without a user-provided default constructor
} par ; //
  ^
     {}
In file included from prime.cpp:5:
In file included from ../include/experimental/algorithm:7:
In file included from ../include/experimental/execution_policy:135:
In file included from ../include/experimental/bits/parallel/policy_parallel.h:555:
../include/experimental/bits/parallel/algos/par/fill_n.h:16:39: error: reference to non-static member function must be called
      detail::diffract(first, first + count, std::fill<OutputIterator, T>, value);
                                      ^~~~~
../include/experimental/bits/parallel/algos/par/count.h:15:34: note: possible target for call
      parallel_execution_policy::count(InputIterator first, InputIterator last, 
                                 ^
In file included from prime.cpp:5:
In file included from ../include/experimental/algorithm:7:
In file included from ../include/experimental/execution_policy:135:
In file included from ../include/experimental/bits/parallel/policy_parallel.h:575:
../include/experimental/bits/parallel/algos/par/max_element.h:18:36: error: reference to non-static member function must be called
                                   max_element<ForwardIterator>,
                                   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
../include/experimental/bits/parallel/algos/par/max_element.h:14:48: note: possible target for call
    ForwardIterator parallel_execution_policy::max_element(ForwardIterator first, 
                                               ^
../include/experimental/bits/parallel/policy_parallel.h:460:21: note: possible target for call
    ForwardIterator max_element(ForwardIterator first, ForwardIterator last,
                    ^
In file included from prime.cpp:5:
In file included from ../include/experimental/algorithm:7:
In file included from ../include/experimental/execution_policy:135:
In file included from ../include/experimental/bits/parallel/policy_parallel.h:575:
../include/experimental/bits/parallel/algos/par/max_element.h:28:36: error: reference to non-static member function must be called
                                   max_element<ForwardIterator, Compare>,
                                   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
../include/experimental/bits/parallel/algos/par/max_element.h:14:48: note: possible target for call
    ForwardIterator parallel_execution_policy::max_element(ForwardIterator first, 
                                               ^
../include/experimental/bits/parallel/algos/par/max_element.h:24:48: note: possible target for call
    ForwardIterator parallel_execution_policy::max_element(ForwardIterator first, 
                                               ^
In file included from prime.cpp:5:
In file included from ../include/experimental/algorithm:7:
In file included from ../include/experimental/execution_policy:135:
In file included from ../include/experimental/bits/parallel/policy_parallel.h:577:
../include/experimental/bits/parallel/algos/par/min_element.h:18:36: error: reference to non-static member function must be called
                                   min_element<ForwardIterator>,
                                   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
../include/experimental/bits/parallel/algos/par/min_element.h:14:48: note: possible target for call
    ForwardIterator parallel_execution_policy::min_element(ForwardIterator first, 
                                               ^
../include/experimental/bits/parallel/policy_parallel.h:452:21: note: possible target for call
    ForwardIterator min_element(ForwardIterator first, ForwardIterator last,
                    ^
In file included from prime.cpp:5:
In file included from ../include/experimental/algorithm:7:
In file included from ../include/experimental/execution_policy:135:
In file included from ../include/experimental/bits/parallel/policy_parallel.h:577:
../include/experimental/bits/parallel/algos/par/min_element.h:28:36: error: reference to non-static member function must be called
                                   min_element<ForwardIterator, Compare>,
                                   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
../include/experimental/bits/parallel/algos/par/min_element.h:14:48: note: possible target for call
    ForwardIterator parallel_execution_policy::min_element(ForwardIterator first, 
                                               ^
../include/experimental/bits/parallel/algos/par/min_element.h:24:48: note: possible target for call
    ForwardIterator parallel_execution_policy::min_element(ForwardIterator first, 
                                               ^
7 errors generated.

Is support for clang planned/desired?

Implement dynamic execution policy

The dynamic container for the execution policies is not implemented, nor is the specialization of the algorithms for a dynamic container.

Bitbucket: https://bitbucket.org/tlutz/n3554-aka-n3850-n3960-implementation/issue/5
Originally Reported By: Thibaut Lutz
Originally Created At: 2014-04-15T14:46:08.827

std::adjacent_difference has been removed

std::adjacent_difference is no longer part of the proposal.

diffact_gather cannot handle init values

When using diffract_gather with an algorithm having an init value, this value is repeated for each chunk instead of begin repeated once.

Bitbucket: https://bitbucket.org/tlutz/n3554-aka-n3850-n3960-implementation/issue/10
Originally Reported By: Thibaut Lutz
Originally Created At: 2014-04-15T22:32:49.265