Re: [boost] We need a coherent higher level parallelization story for C++ (was [thread] Is there a non-blocking future-destructor?)

Subject: Re: [boost] We need a coherent higher level parallelization story for C++ (was [thread] Is there a non-blocking future-destructor?)
From: Vicente J. Botet Escriba (vicente.botet_at_[hidden])
Date: 2015-10-14 01:56:13

Le 13/10/15 04:02, Vicente J. Botet Escriba a écrit :
> Le 12/10/15 14:52, Hartmut Kaiser a écrit :
>> Sorry for cross-posting.
>>
>> Our
>> group has outlined our current understanding and a possible approach 
>> to this
>> here [1]. I'd like for this to be understood as a seed for a wider
>> discussion. Needless to say, I'd very much like to collaborate on 
>> this with
>> anybody interested in joining the effort.
> I'll read it and come back to you.
Hi,

In general I like the global direction of p0058r0, but have some 
concerns respect to the form. This will be longer than I expected.

I like:

* the fact that we are conceptualizing the interface and allowing to 
customize it

* the additional bulk and synchronous interface execute.

* the way async_execute/when_all/when_any can deduce the returned future 
once we have an executor parameter (even if I would preferred to 
associate them to an execution policy - see below).

* the chaining when_all_execute_and_select

* the future cast that can be used when the single thing important is if 
the task has completed.

* rebind, this type trait should be make generic, and customizable by 
the user
     rebind<par, MyExecutor>
     rebind<future<int>, string>

* the fact that then() continuations consume  value types and not on 
futures (this is in line to my proposed next() function).
have you added some kind of recover continuations (like my recover or 
catch_error)?

* the on(ex).with(p) chaining style (I have used it in order to schedule 
timing operations in Boost.Thread)

     submit(sch.on(ex).at(tp), f);

* we can retrieve the wrapped type,

I like less:

* the fact that executors are aware of futures, I like the split of 
responsibilities, executors have void() work to schedule, and we have a 
free function like async/spaw/submit  that returns a future. The 
question is which future should return async(ex, ...).  p0058r0 propose 
async_execute that deduces the future from the executor.
I believe that in in the same way the execution policy embodies a set of 
the rules about where, when and how to run a submitted function object, 
it should have associated also how the asynchronous result is reported, 
that is, which specific future must be used as result of async; 
when_all,when_any.

IMHO, futures depend on executors, not the opposite. I don't know how to 
implement an executor that can return my special future. However I know 
how to implement a future that can store a specific Executor.

* I don't know if then_execute result should depend on the future 
associated to the executor (or execution policy) as I expect the same 
kind of future as a result.

* the name value_type to retrieve the wrapped type. I' don't know if 
value_type is the most appropriated when we have future<T&>. ValueType 
as defined in the Range proposal removes references and cv qualifications.

* The name future_traits and the fact that future_traits takes a 
specific class as template parameter and not a type constructor (a 
high-order meta-function that transforms types on types). IMO what we 
are mapping is not std::future<T>, but std::future or std::future<_>. 
Given a type future<int>, it is useful to have its type_constructor. E.g.
type_constructor<future<T>> is future<_>

     type_constructor<apply<TC, T>> is TC
     value_type<apply<TC, T>> is T

As a type constructor future<_> apply<future<_>, string> is the same as 
future<string>. While apply<future<_>, string> and rebind<future<int>, 
string> seems similar, apply can be used with any high order 
meta-function as e.g. apply<lift<future>, string>.

I use rebind when you have an instance of a class, as future<int>, 
optional<int>, and apply is used when you have a type constructor as 
future, optional.

rebind can be defined in function of apply and type_constructor.

rebind<X,T> = apply<type_constructor<X>,T>

E.g. if we had a future that takes two parameters T and E (as expected 
does), the type constructor (respect to T) would be future<_, E>.

* wondering if the same applies to execution policies. Could we consider 
that a execution policy wraps an executor?

* I need to think about the separation of the execution_policy and the 
executor. Is the executor copyable?
I see that executor policy provides a function to get a reference, but 
has the executor a reference to its policy? What are the lifetimes of both?
     executor_type& executor();

* functions having almost the same prototype but behaving quite differently.
I see that you propose par(task) policy and that a function can return a 
future or not depending on the policy (par(task)). I like to use 
different names when the functions must be used following a different 
protocol. Do you have an example of an algorithm that is common 
independently of whether the policy is par or par(task)?

* The cumbersome generic interface
I believe in general that we need two different interfaces, the user 
interface and the customization interface. The customization interface 
is often less friendly than the user interface. The executor_traits 
interface is for me one way to customize an interface. Other 
alternatives are also possible (see below)

At the user level, the following example

Iterator for_each_n(random_access_iterator_tag, ExecutionPolicy&& 
policy, InputIterator first, Size n, Function f)
{
     using executor_type = typename 
decay_t<ExecutionPolicy>:::executor_type;
     executor_traits<executor_type>::execute(policy.executor(), [=](auto 
idx)     {         f(first[idx]);     }, n );
}

seems more cumbersome than something more direct like

Iterator for_each_n(random_access_iterator_tag, ExecutorPolicy&& policy, 
InputIterator first, Size n, Function f)
{
     execute(policy.executor(), [=](auto idx)     {         
f(first[idx]);     }, n);
}

The interface for the user could

future_result_type_t<Executor, F> execute(Executor&, F&&, Args...);
future_result_type_t<Executor, F> async_execute(Executor&, F&&, Args...);

future_result_type_t<Executor, F> execute_n(Executor&, size_t, F&&, 
Args...);
future_result_type_t<Executor, F> async_execute_n(Executor&, size_t, 
F&&, Args...);

Note that the interface allows to pass some information to the task to 
execute. Note that the bulk versions have a different name as these 
functions do something different. How to combine the index with the Args 
can be discussed, but I believe that passing the Index as first 
parameter of the continuation is a good compromise.

However the executor customized interface doesn't needs the Args 
parameters, as user functions would pack F and Args to make a 
void(void)/void(size_t) schedulable work.

Another cumbersome example

     using executor_type = typename 
decay_t<ExecutionPolicy>:::executor_type;
     return 
executor_traits<executor_type>::make_future_ready(policy.executor());

or

     return future_traits<future<int>>::make_ready();

Compare this with a more user friendly

     return make_future_ready(policy.executor());

or

     return make<future>();

which of course should be equivalent to the previous code fragment.

I'm working on a on-going factories proposal that would allow 
make<future>();

BTW, the following function is missing from executor_traits as well as 
make_exceptional_future.

static future<void> make_ready_future(executor_type& ex);

* What do you think of using overload and flat type traits in order to 
customize the user interface instead of executor_traits as suggested by 
Eric?
E.g. I would expect that rebind, value_type to be generic and placed at 
the std level. Other traits are more specific like executor_type, 
execution_category, ...

* Inspired from Boost.Hana and Haskell I have been customizing some type 
classes following the following pattern pattern. It is quite close to 
the trait approach, however,
I use an additional level of indirection via a tag type trait that allow 
to dispatch to a common model instead of defining the trait directly.

     executor_traits<T> = 
executors::type_class::instance<executors::type_class::tag<T>>

By default executors::type_class::tag<T> is the same as type<T> instead 
of the type T itself. This in needed to ensure that the associated tag 
is copyable and is very cheep to copy.

The main difference with Boost.Hana is that here the tag depends on the 
type class and in Hana it is a global tag associated to a type (data_type).

I use a namespace for each concept/type class that needs to be 
customized. E.g for the executor concept we could have

   namespace executors
   {
     struct type_class {
       template <class Tag>
       struct instance;

       template <class T>
       struct tag  { using type = type<T>; };
     };
   }

...

We could have a default definition for 
executors::type_class::instance<Tag> if we don't need explicit mapping. 
However, as Hana, I use to define what Hana and Haskel calls Minimum 
Complete Definition (mcd) (related to lowering in the proposal). In this 
case, a mcd is based on the definition of ex.async_execute(), so we 
could have

   namespace executors
   {
     struct async_execute_mcd {...};
     struct type_class {
       template <class Tag>
       struct instance : async_execute_mcd {};
     }
   }

Having a common schema to define the traits allows to define other 
common traits as

     concept_instance_t<executors::type_class, Ex>

     models<Ex, executors::type_class>

I use to place the operations associated with a type class in the same 
namespace. This is not a requirement, but helps to avoid name collision.

   namespace executors
   {
     template <class Ex, class F, class 
Instance=concept_instance_t<executors::traits, Ex>>
     auto execute(Ex& ex, F&& f)
       -> decltype(Instance::execute(ex, forward<F>(f)))
     {
       return Instance::execute(ex, forward<F>(f));
     }
...

Whether execute would merits to go one level up and move to the parent 
namespace is subject to discussion, as would be having an alias for

     executor_instance<T> = concept_instance_t<executors::type_class,T>

Best,
Vicente