Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Further simplify tag_invoke helpers #5344

Closed
msimberg opened this issue May 19, 2021 · 17 comments
Closed

Further simplify tag_invoke helpers #5344

msimberg opened this issue May 19, 2021 · 17 comments

Comments

@msimberg
Copy link
Contributor

Related to #5332. @hkaiser, @K-ballo, I went back to wg21.link/p1895, and @K-ballo is very correct in saying that they did consider the fallback and override cases in the paper. The "Design Discussion" section contains the relevant parts. With #5283 we get a very viable alternative with if constexpr. The tag* base classes do help reduce boilerplate currently, so it'd be a shame to completely get rid of them, but being able to use if constexpr would quite significantly simplify things without having to keep the fallback/override versions. Until we require C++17 I think they are a reasonable compromise though.

@hkaiser
Copy link
Member

hkaiser commented May 19, 2021

The if constexpr alternative is good only in cases where we want for the base implementation to 'be aware' of all the alternative implementations. The fallback facilities we have is still the only way for cases where the base implementation should be extended by alternatives without changing it (like with the segmented algorithms or the specializations related to datapar).

The fallback and override facilities we have created go beyond what was intended for std::tag_invoke. Those are not only helpers to create customization points, but provide viable tools for flexible and extensible overload resolution.

The main problem I see (as also pointed out by @K-ballo) is that having a tag_invoke in HPX might (ADL) conflict with a future std::tag_invoke.

That said, I still believe that our facilities (tag_invoke, tag_fallback_invoke, and tag_override_invoke) are useful and should stay. We should consider finding better names for those, however. That may help avoiding conflicts with a future std::tag_invoke and may also circumvent possible misconceptions from users that assume semantics as described by wg21.link/p1895.

@K-ballo
Copy link
Member

K-ballo commented May 19, 2021

The uses of tag_invoke for the purposes of segment algorithm separation have no relation whatsoever to the proposed std::tag_invoke design, none of them are customization points, so in that regard it is unsurprising that extensions were needed to take it in different directions. A less misleading name would definitely help.

In the future we can look into approaching the underlying problem differently.

@hkaiser
Copy link
Member

hkaiser commented May 19, 2021

As a first step I'd suggest to add detection of std::tag_invoke (now or in the future once some libraries actually implement it) and -- if it is available -- disable our hpx::functional::tag_invoke API facility. The CPO implementations we have should be usable with a std::tag_invoke without change (it's based on ADL anyways).

The uses of tag_invoke for the purposes of segment algorithm separation have no relation whatsoever to the proposed std::tag_invoke design, none of them are customization points, so in that regard it is unsurprising that extensions were needed to take it in different directions

I agree wrt the segmented algorithms. However for customizing the algorithms for GPUs and/or datapar vectorization (both based on overloading the algorithms on the execution policy), the use of tag_invoke to implement overload resolution is right on the mark. So we're left with a situation where part of the desired overloads do actually 'customize' the algorithms (in the sense of p1895), and other overloads go beyond.

In general, the capabilities enabled by tag_fallback_invoke and friends are not easily available using the envisioned std::tag_invoke, in that I agree that it is unsurprising we had to develop our own extensions.

@msimberg
Copy link
Contributor Author

I'm not sure I follow all of this. I see two points:

  1. Is the concern with the segmented algorithm overloads that they are not overloads but only constrain the arguments through SFINAE? If yes, do I understand it correctly that with concepts that would actually be perfectly fine (with segmented_iterator being a refinement of some iterator concept)? Again, if yes, the way I see those is that they are a hack until we can use appropriate language features for them.
  2. How is the following different from what we do currently with tag_fallback_invoke for the segmented algorithms, and tag_override_invoke for member functions having priority in P0443/P1897:
inline constexpr struct​ for_each_t {
    ​template​<typename ExPolicy, typename... Args>
    ​decltype​(​auto​) ​operator​()(ExPolicy p, Args... args) ​const​ {
    if constexpr (have_override_v<ExPolicy, Args...>) {// Optional. E.g. have member function connect.
        // Override implementation
    }
    else ​if constexpr​ (std::tag_invocable<for_each_t, ExPolicy, Args...>) {
        return​ std::tag_invoke(*this, p, args...);
    } else​ {
        // Fallback implementation
    }
} for_each{};

@K-ballo
Copy link
Member

K-ballo commented May 19, 2021

Is the concern with the segmented algorithm overloads that they are not overloads but only constrain the arguments through SFINAE?

Segmented algorithms are actually overloads. They are not customizations (nor algorithms should be customization points).

do I understand it correctly that with concepts that would actually be perfectly fine (with segmented_iterator being a refinement of some iterator concept)?

Concepts would bring subsumption, some SegmentedIterator concept would subsume some plain Iterator concept, overload resolution would then prefer SegmentedIterator overloads to Iterator ones all else being equal. Just like RandomAccessIterator subsumes BidirectionalIterator and so on, but along an orthogonal axis.

This would not work for algorithms as objects, as it applies to overloads. Algorithm objects would still have to dispatch to actual overloads for concepts to be advantageous for resolution.

@K-ballo
Copy link
Member

K-ballo commented May 19, 2021

How is the following different from ... tag_fallback_invoke/tag_override_invoke

I am not familiar with those two, so I couldn't say.

The fallback part in the snippet looks suspicious, with std::tag_invoke as designed/proposed one would simply do std::tag_invoke(*this, p, args...), for when there is a fallback it would match the base (fallback) implementation. Ignoring override entirely, I'd imagine something along the lines of:

inline constexpr struct​ for_each_t {
    ​template​<typename ExPolicy, typename... Args>
    ​decltype​(​auto​) ​operator​()(ExPolicy p, Args... args) ​const​ {
      if constexpr (have_override_v<ExPolicy, Args...>) {// Optional. E.g. have member function connect.
        // Override implementation
      } else {
        return​ std::tag_invoke(*this, p, args...);
      }
    }
    
    ​template​<typename ExPolicy, typename... Args>
    friend ​decltype​(​auto​) tag_invoke(for_each, ExPolicy p, Args... args) ​const​ {
       // Fallback implementation
    }
} for_each{};

@msimberg
Copy link
Contributor Author

(nor algorithms should be customization points).

Is this a theoretical or practical view, or both? Being able to do std::for_each(my_execution_policy, ...) (where that specific call is customized, not somewhere internally with an executor attached to the execution_policy) is very much something we would like to do. If not std::for_each, then hpx::for_each. I don't know how practical it would be for standard library implementations to ever make e.g. std::for_each a customization point (ABI...), but it is attractive, and currently I don't know what the alternative would be if that is not possible.

This would not work for algorithms as objects, as it applies to overloads. Algorithm objects would still have to dispatch to actual overloads for concepts to be advantageous for resolution.

Dispatch to tag_invoke overloads?

How is the following different from ... tag_fallback_invoke/tag_override_invoke

I am not familiar with those two, so I couldn't say.

Fair enough. In short they're an overelaborate way of implementing exactly that override/fallback behaviour over here:

template <typename... Args,
typename Enable = typename std::enable_if<
is_nothrow_tag_override_invocable_v<Tag, Args&&...>>::type>
HPX_HOST_DEVICE HPX_FORCEINLINE constexpr auto operator()(
Args&&... args) const noexcept
-> tag_override_invoke_result_t<Tag, Args&&...>
{
return tag_override_invoke(static_cast<Tag const&>(*this),
std::forward<Args>(args)...);
}
// Is not nothrow tag-override-invocable, but nothrow tag-invocable
template <typename... Args,
typename Enable = typename std::enable_if<
!is_nothrow_tag_override_invocable_v<Tag, Args&&...> &&
is_nothrow_tag_invocable_v<Tag, Args&&...>>::type>
HPX_HOST_DEVICE HPX_FORCEINLINE constexpr auto operator()(
Args&&... args) const noexcept
-> tag_invoke_result_t<Tag, Args&&...>
{
return tag_invoke(static_cast<Tag const&>(*this),
std::forward<Args>(args)...);
}
// Is not nothrow tag-override-invocable, not nothrow tag-invocable, but
// nothrow tag-fallback-invocable
template <typename... Args,
typename Enable = typename std::enable_if<
!is_nothrow_tag_override_invocable_v<Tag, Args&&...> &&
!is_nothrow_tag_invocable_v<Tag, Args&&...> &&
is_nothrow_tag_fallback_invocable_v<Tag, Args&&...>>::type>
HPX_HOST_DEVICE HPX_FORCEINLINE constexpr auto operator()(
Args&&... args) const noexcept
-> tag_fallback_invoke_result_t<Tag, Args&&...>
{
return tag_fallback_invoke(static_cast<Tag const&>(*this),
std::forward<Args>(args)...);
}
. Except that instead of using if constexpr the operator() overloads are ordered using is_tag_x_invocable and sfinae. Overelaborate because there should be only one override or fallback, but the mechanism right now in principle allows for multiple overloads of the override/fallback. Users are, however, only meant to provide tag_invoke overloads.

The fallback part in the snippet looks suspicious, with std::tag_invoke as designed/proposed one would simply do std::tag_invoke(*this, p, args...), for when there is a fallback it would match the base (fallback) implementation. Ignoring override entirely, I'd imagine something along the lines of:

Could you expand on why it looks suspicious? The example is essentially what's in P1895 "Strategies for defining default implementations of CPOs" section 1 and 2. The motivation for us to introduce tag_fallback_invoke (however weird the actual implementation might be), and the motivation in P1895 is to avoid having the fallback implementation be more specific, unless one provides exactly all the appropriate tag_invoke overloads for whichever type one is customizing. Now that section is called "Design Discussion" so you might simply be disagreeing with that approach?

Keep in mind my ignorance in how practical these kind of things are in reality in standard library implementations. Hence my question in the beginning about "theoretical or practical view", and I'm trying to understand where your concerns are.

@hkaiser
Copy link
Member

hkaiser commented May 19, 2021

The fallback part in the snippet looks suspicious, with std::tag_invoke as designed/proposed one would simply do std::tag_invoke(*this, p, args...), for when there is a fallback it would match the base (fallback) implementation. Ignoring override entirely, I'd imagine something along the lines of:

inline constexpr struct​ for_each_t {
    ​template​<typename ExPolicy, typename... Args>
    ​decltype​(​auto​) ​operator​()(ExPolicy p, Args... args) ​const​ {
      if constexpr (have_override_v<ExPolicy, Args...>) {// Optional. E.g. have member function connect.
        // Override implementation
      } else {
        return​ std::tag_invoke(*this, p, args...);
      }
    }
    
    ​template​<typename ExPolicy, typename... Args>
    friend ​decltype​(​auto​) tag_invoke(for_each, ExPolicy p, Args... args) ​const​ {
       // Fallback implementation
    }
} for_each{};

Frankly, this is exactly what we try to avoid. The main dispatch point above shouldn't be aware of the override implementations as those might not even be known ATM. All it should do is to dispatch to the proper override (based on overload resolution), which is exactly what our tag_fallback implementation does.

@K-ballo
Copy link
Member

K-ballo commented May 19, 2021

Frankly, this is exactly what we try to avoid.

Yeah, I definitely agree that this is not how one would go about this.

@K-ballo
Copy link
Member

K-ballo commented May 19, 2021

Could you expand on why it looks suspicious?

My attempt at expanding was in the pseudo-code. The std::tag_dispatch mechanism as designed accounts for the existence of a fallback, the implementation doesn't need to do two steps on this. Put another way std::tag_invocable<Tag, ...> should yield true when tag dispatching picks the fallback too.

@K-ballo
Copy link
Member

K-ballo commented May 19, 2021

Is this a theoretical or practical view, or both?

I'm not sure what the differences would be...

A customization is a way for a type or a family of types to override some concept's implementation. It is a virtual/override equivalent for static polymorphism. From this stems that customizations have to be found by argument dependent lookup, and by argument dependent lookup only. This further constrains customization points to be implemented as objects (in the absence of some extension or future language feature like final "free" functions that disables ADL).

Algorithms aren't concepts, nor they are pieces of some larger concepts. They are not some interface's virtual for types to fullfill.

Segmented iterators are not a type. There is no namespace associated with all possible segmented iterators.

Execution policies were designed as tags, to be used with traditional overloading. When doing tag dispatching, overloads must NOT be found by argument dependent lookup, since the tag and only the tag itself is used for dispatch, and no user defined argument that happens to be passed along should interfere with that.

If the set of overloads that a call is being dispatched to is closed, then the overheads associated with the overloading machine can be avoided by taking advantage of constexpr-if.

(*) While for algorithms as originally designed customization would defeat the purpose, there's something to consider after the introduction of range-based algorithms. For instance, std::list<T> could in principle customize std::ranges::[stable_]sort. This would require figuring out what the Sort concept is, and how it interacts with other characteristics, notably an algorithm's ability to be parallelized (both in isolation as well as as part of a larger chain).

@hkaiser
Copy link
Member

hkaiser commented May 19, 2021

Segmented iterators are not a type. There is no namespace associated with all possible segmented iterators.

Execution policies were designed as tags, to be used with traditional overloading. When doing tag dispatching, overloads must NOT be found by argument dependent lookup, since the tag and only the tag itself is used for dispatch, and no user defined argument that happens to be passed along should interfere with that.

Still, we need a single mechanism that helps handling both cases in a convenient way.

If the set of overloads that a call is being dispatched to is closed, then the overheads associated with the overloading machine can be avoided by taking advantage of constexpr-if.

Our algorithm overloads are not a closed set.


Let's not call the objects implementing the algorithms 'Customization Point Objects' but 'Dispatch Point Objects' (or something similar). I believe that if we do that, many of the issues discussed will be resolved. Instead of naming the dispatch points tag_invoke or similar, we should use a different name, something like tag_dispatch or dispatch_point, perhaps.

@K-ballo
Copy link
Member

K-ballo commented May 19, 2021

Still, we need a single mechanism that helps handling both cases in a convenient way.

It's not possible to have a mechanism that does both exclusively ADL at the same time it avoids ADL entirely.

@hkaiser
Copy link
Member

hkaiser commented May 19, 2021

Still, we need a single mechanism that helps handling both cases in a convenient way.

It's not possible to have a mechanism that does both exclusively ADL at the same time it avoids ADL entirely.

I can agree with that these two things are mutually exclusive.

However, I don't think we do need both ADL and non-ADL at the same time. What we need is ADL and tag dispatching together. This however shouldn't be problematic, as even the dispatching of std::tag_invoke itself relies on both, ADL (to find the proper tag_invoke dispatch point), and tag dispatching (the CPO itself is passed along as the first argument for a reason).

@K-ballo
Copy link
Member

K-ballo commented May 19, 2021

I think we do not want ADL in general, except for the very specific case of customization. Many of the uses mentioned in here are not, in fact, customizations. For instance, there's no associated namespace for models of the segmented iterator in which to "customize" algorithms for them, nor a conceptual model of how these interact with executors in the case I want to "customize" an algorithm for my own concrete executor type without dropping segmented-ness on the floor. Neither of these sound like good fits for customization anyways.

I'm convinced a better encompassing design can be reached by understanding all the use cases involved, and how they interact with each other. I don't think it can ever be a single mechanism, as some of the goals are mutually exclusive. I don't think it can just be tag_invoke on its own either, as that's explicitly designed to handle a very specific use case in the best possible library way. In the mean time, overload hell may just work enough (and for the most part it does).

@msimberg msimberg changed the title Further simplify tag_invoke Further simplify tag_invoke helpers May 20, 2021
@hkaiser
Copy link
Member

hkaiser commented Mar 13, 2022

I think we can close this as resolved. @K-ballo any objections?

@K-ballo
Copy link
Member

K-ballo commented Mar 13, 2022

@K-ballo any objections?

None from me.

@hkaiser hkaiser closed this as completed Mar 13, 2022
@hkaiser hkaiser added this to the 1.8.0 milestone Mar 13, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

3 participants