t-lutz / parallelstl Goto Github PK
View Code? Open in Web Editor NEWImplementation of n3554, a proposal to include parallelized versions of the STL algorithms into the C++ standard.
Implementation of n3554, a proposal to include parallelized versions of the STL algorithms into the C++ standard.
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::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 );
When using diffract_gather with an algorithm having an init value, this value is repeated for each chunk instead of begin repeated once.
diffract should require Callable instead of FunctionObject
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?
std::adjacent_difference
is no longer part of the proposal.
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!
The dynamic container for the execution policies is not implemented, nor is the specialization of the algorithms for a dynamic container.
for_each_n
returned the function in the older versions of the proposal. Now it returns an iterator.
std::is_heap
is in the table 1 of n3960, but not std::is_heap_until
.
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
The following are missing from the headers, the policies and the test suite:
std::fill_n returns an iterator since c++11.
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.
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
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.
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.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.