User defined execution policies

Apr 18, 2014 at 5:01 PM
Edited Apr 18, 2014 at 5:07 PM
One of the goals of the proposal is (I think) to allow users to define their own execution policies for new exotic targets (GPUs for example). With your current implementation, I don't see how it is possible.

One way to do it would be to register a new policy by specializing is_execution_policy (which is technically undefined behavior with the current wording of the spec), and the algorithms should (or could really) accept the new policy if a specialization exists. The problem is the dynamic container execution_policy would not recognize the new policy, since it has a hard coded type switch between the three default policies and throws an exception if it is not any of those.

Another way would be to inherit from an existing policy (since the implementation checks for is_base_of instead of is_same) and re-specialize some algorithms. However that would open up a pandora's box of ambiguous definitions and undesired runtime behavior. A nightmare.

So have user defined policies been considered for the implementation? Should they be allowed? What would be the best way to allow them?
Coordinator
Apr 18, 2014 at 7:04 PM
Hi,

Some of the motivational text that was in the earlier versions of the proposal was removed, but you can still access it here:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3554.pdf

Specifically, scroll to page 14, and look at the example with some_api.

Essentially, you can view execution_policy as a base class for other policies (it isn't really, and the reasons why this design was rejected is also in N3554). Clearly, the existing algorithms will not 'magically' work for every user-defined policy -- you actually have to implement a new algorithm. The main reason for execution_policy is that you can pass the policy object around in a standardized way, without templatizing every function that accepts it (which would be impossible for binary interfaces).

Bottom line: user-defined policies are supported, but they only make sense together with algorithms that "understand" them.
Apr 18, 2014 at 7:19 PM
Ok, I didn't see it like that. In my implementation I actually used delegation to the policy object instance itself for executing an algorithm. This makes creating new policies from scratch or extending existing policies easy, but I am stuck for the implementation of the generic execution_policy wrapper.

So user defined policies will not be able to interact with the standard algorithms directly, only with user-defined algorithms outside the std namespace. That's a shame, I was thinking the design was more modular than that.

I haven't read n3554 for a while, I should probably go through it again.
Coordinator
Apr 18, 2014 at 11:23 PM
So user defined policies will not be able to interact with the standard algorithms directly
Actually, I didn't say that -- you can still delegate by adding overloads in std namespace:
namespace std {
    void sort(MyQuirkyPolicy policy, RandomAccessIterator first, RandomAccessIterator last)
    {
        quirksort(first, last);
    }
}
Your approach would also work, but it requires an additional contract between the library and the user -- it would have to be specified that the implementation must call policy.sort etc. for every algorithm.
Apr 19, 2014 at 12:00 AM
Right, but the interaction with execution_policy would be broken, which makes the code not very intuitive:
MyQuirkyPolicy policy;
sort(policy, being(v), end(v)); // this works

execution_policy exec = policy; // this works provided is_execution_policy is overloaded
sort(exec, being(v), end(v)); // this breaks and throws an exception
I don't really see the point of having a dynamic container if it is just limited to the three proposed policies. Having a dynamic container to also accept user defined types is tricky to implement.

Just to clarify, with you current implementation, i think clause 4.1.1.6 is broken (or just not implemented):
Algorithms invoked with an execution policy object of type execution_policy execute internally as if invoked with instances of type sequential_execution_policy, parallel_execution_policy, or an implementation-defined execution policy type depending on the dynamic value of the execution_policy object.
I am not filing that as a bug since I am still a bit confused about the role of user defined policies.
Coordinator
Apr 19, 2014 at 1:58 AM
execution_policy was designed to support any types, not just the three built-in types. Perhaps our current implementation doesn't do it justice (and we should fix it, and add a sample showing it), but here is another example I put together earlier when we were designing it.

You will see how I can put a custom policy ppl::par_with_fixed_chunk_size in it.

I'd be interested in how you solve the dynamic policy case without imposing the cost of dynamic dispatch (such as virtual call) on all callers. Note that a base class solution would solve it, but that means that every policy needs to implement every algorithm, not to mention the cost of a virtual call.

One option (don't quite me on this, I just came up with this idea) is to have a special other_policy type with a virtual dispatch on it, and use it as follows:
void some_api(std::execution_policy exec, int arg1, double arg2)
{
    if(exec.target_type() == typeid(std::sequential_execution_policy))
...
    else if(exec.target_type() == typeid(std::parallel_execution_policy))
...
    else
    {
        if(exec.target_type() == typeid(other_policy))
        {
            other_policy *exec_ptr = exec.target<other_policy>();
            exec_ptr->sort(...);
        }
    }
}
Coordinator
Apr 19, 2014 at 2:01 AM
@tlutz: one more thing -- thanks for the great feedback, exactly why we made it public.
Apr 19, 2014 at 9:38 AM
I think it is an important feature. An example of a user defined policy interacting with a standard algorithm would be good to see. A specialization of std::sort for example.

The static dispatch followed by a default dynamic one is pretty much exactly what I had in mind too, but we can probably do better, which is why I haven't started implementing it. The problem is that the type erasure hides template function; and mixing subtype polymorphism and parametric one doesn't sound like a good idea.

I'll think about it over the weekend.
Apr 19, 2014 at 11:31 AM
Edited Apr 19, 2014 at 11:32 AM
Just to be sure we agree on this, should the last line in the following code work? I think it should, but your implementation (and mine) doesn't allow it.
#include <iostream>
#include <vector>
#include <experimental/algorithm>

struct MyPolicy {};

namespace std {
namespace experimental {
namespace parallel {

template<> struct is_execution_policy<MyPolicy> : true_type{};

template<class RandomAccessIterator>
inline void sort(const MyPolicy &, RandomAccessIterator, RandomAccessIterator)
{
  cout << "my clever sort" << endl;
}

}}} // std::experimental::parallel


int main(){
  using namespace std;
  using namespace std::experimental::parallel;
  vector<int> v(10);
  
  MyPolicy policy;

  sort(seq, begin(v), end(v));    // this works
  sort(par, begin(v), end(v));    // this works
  sort(policy, begin(v), end(v)); // this works (in my implementation)

  // using execution_policy
  execution_policy dyn = seq;
  sort(dyn, begin(v), end(v)); // this works

  dyn = par;
  sort(dyn, begin(v), end(v)); // this works
  
  dyn = policy;
  sort(dyn, begin(v), end(v)); // this breaks...
}
You can find the example above and a simplified implementation of the proposal here for anyone who is interested in prototyping or investigating a solution.
May 6, 2014 at 5:14 PM
Edited May 9, 2014 at 10:59 AM
I finally had a bit of time to play with this. It is not an easy problem to solve. Here are my observations though:
  • implementing the dispatcher is tricky. Actually I think it can't be done in a truly generic way using the current (as in C++14) standard.
  • it can be done using hacks, I prototyped something which makes code like shown in the post above or like this work (the uglyness is contained to lines 55-60)
  • I think using template function overload is not the right approach, because it does not allow users to define their own policies. If the overloads are declared after the dispatch, they will never be instantiated. Forcing the user to define their own policies before they include a system header is not a nice requirement. Using delegation of the algorithms to the policy type allows the dispatcher to force instantiation whenever possible and solves this problem.
The current draft implementation has the following qualities:
  • a user policy can be defined anywhere
  • it does not have to define all the algorithms
  • it can inherit from another policy and overload some algorithms, using the other ones as default
  • an almost concept-like checking throws nice runtime errors (like "This policy does not support sort")
  • nothing is virtual, policies are just any types that defines some algorithms as member functions (and specialize the type trait as required by the proposal)
And the following drawbacks:
  • the implementation is rather ugly, although it is contained to the system headers
  • the current implementation only allows 5 user defined policies (this can probably be fixed)
  • the user has to register all the policy types to the dispatcher explicitly (see example)
  • this would most likely break for several translation units (I haven't even tried)
  • there is a lot of template magic going on, the compile time would not scale very well
This is a very first draft, I will try to improve on the limitations. The main point I am trying to make is that the same method would not work with template overloads.