Enable binary comparison operations for internal tuple

[danhoeflinger]

Summary

This PR enables comparison <, >,<=,>= of our internal tuple oneapi::dpl::__internal::tuple<T...> with another oneapi::dpl::__internal::tuple<U...> or std::tuple<U...> with equal number of elements where corresponding elements from rhs and lhs are comparable.

We use the std::tuple implementation for these operations by static casting and repeating the operation.

We extend the same to == and !=, where we previously implemented the operation directly.

Details

We already provide an implicit conversion operator to a std::tuple, and also are able to construct from a std::tuple. However, when a template function is considered for overload resolution it does type deduction and will only use exact matches. It will not use any implicit conversion to build the candidate list. Therefore, this implicit conversion is not used when searching for resolution for operator<, and we cannot take advantage of std::tuple's implementation of these operators (at least without extra effort).

We use a macro to unify implementation of all binary operators in the same fashion and reduce code to a minimum.

[danhoeflinger]

I'm working on adding some unit testing for tuple to the test suite. Once I add that, I will probably revert the changes to zip_iterator.pass .

[adamfidel]

I was curious if the three provided functions in the macro were enough to cover all of the cases to compare. But I enumerated them and it does seem like it is sufficient.

There are three tuple types we would like to compare:

1. tuple (self with T1, T...)
2. tuple<_U1, _U...> (self with potentially different types)
3. std::tuple<_U1, _U...> (standard tuple with potentially different types

lhs	rhs	matching candidate
1	1	__OPERATOR(const tuple& __lhs, const oneapi::dpl::__internal::tuple<_U1, _U...>& __rhs)
1	2	__OPERATOR(const tuple& __lhs, const oneapi::dpl::__internal::tuple<_U1, _U...>& __rhs)
1	3	__OPERATOR(const tuple& __lhs, const std::tuple<_U1, _U...>& __rhs)
2	1	__OPERATOR(const tuple& __lhs, const oneapi::dpl::__internal::tuple<_U1, _U...>& __rhs)
2	2	__OPERATOR(const tuple& __lhs, const oneapi::dpl::__internal::tuple<_U1, _U...>& __rhs)
2	3	__OPERATOR(const tuple& __lhs, const std::tuple<_U1, _U...>& __rhs)
3	1	__OPERATOR(const std::tuple<_U1, _U...>& __lhs, const tuple& __rhs)
3	2	__OPERATOR(const std::tuple<_U1, _U...>& __lhs, const tuple& __rhs)
3	3	defined by standard

Based on this, it seems like the three functions that are defined are sufficient.

[danhoeflinger]

Based on this, it seems like the three functions that are defined are sufficient.

Yes, thanks for doing this enumeration of the possibilities. Working on a test which should prove that out as well.

[danhoeflinger]

OK, now all those options @adamfidel mentioned should be covered by the unit test. I've reverted the zip_iterator test changes in favor of unit testing.

I've also rebased to have 2 commits so that we can separate the unit test addition in the main git log from the tuple changes.

[danhoeflinger]

I think better if we will support all restrictions for these operators like in https://en.cppreference.com/w/cpp/utility/tuple : all these operators will be removed in C++20.

@SergeyKopienko Can you be more specific about what you mean by this comment? Do you mean we should provide a different implementation for C++20 guarded by preprocessor logic?

Also, these operators are removed in C++20, but only in favor of the operator<=> which supports all of them with a single operator. From the outside looking in, there shouldn't be a difference.

[SergeyKopienko]

I think better if we will support all restrictions for these operators like in https://en.cppreference.com/w/cpp/utility/tuple : all these operators will be removed in C++20.

@SergeyKopienko Can you be more specific about what you mean by this comment? Do you mean we should provide a different implementation for C++20 guarded by preprocessor logic?

Also, these operators are removed in C++20, but only in favor of the operator<=> which supports all of them with a single operator. From the outside looking in, there shouldn't be a difference.

For me it's looks like we should implement all these operators only for C++17 version and implement <=> operator for C++20.

[danhoeflinger]

For me it's looks like we should implement all these operators only for C++17 version and implement <=> operator for C++20.

That's fine. I can do that.

[danhoeflinger]

For me it's looks like we should implement all these operators only for C++17 version and implement <=> operator for C++20.

I'm wondering if it is a good idea after some exploration...

The way it is currently, it works for both C++17 and C++20 and offers the support and comparison with std::tuple.

If we change it to be operator<=> when C++20 is defined (removing the individual operators), we need to be in lock step with when std::tuple::operator<=> was included in the implementation of C++20 features, otherwise it will be broken. If we include both individual operators and <=> at the same time, it is technically ambiguous and will at least provide warnings.

I think the only thing we miss out on in c++20 with the current implementation is if someone explicitly uses the <=> operator (which seems both unlikely and not a case we care much about).

[SergeyKopienko]

For me it's looks like we should implement all these operators only for C++17 version and implement <=> operator for C++20.

I'm wondering if it is a good idea after some exploration...

The way it is currently, it works for both C++17 and C++20 and offers the support and comparison with std::tuple.

If we change it to be operator<=> when C++20 is defined (removing the individual operators), we need to be in lock step with when std::tuple::operator<=> was included in the implementation of C++20 features, otherwise it will be broken. If we include both individual operators and <=> at the same time, it is technically ambiguous and will at least provide warnings.

I think the only thing we miss out on in c++20 with the current implementation is if someone explicitly uses the <=> operator (which seems both unlikely and not a case we care much about).

Understood, ok.

[danhoeflinger]

Let me ask: what's a motivation for that internal::tuple functionality extending? Other words, where in OneDPL impl do we need such functionality?

Example: Someone has a zip_iterator of two sequences of integers zipped together. They call oneapi::dpl::sort with no comparator. This will compare each element (onedpl tuple) using operator<. There is a well defined semantic for comparing std::tuple with operator<, so it seems a case we should handle (There is such a use case coming from SYCLomatic).

Then, if we are covering this case, why should it work with one such operator and not others?

Similarly, since we return this tuple type from zip_iterator where the user may then use it, why not allow it to have the same semantics (comparable with different element types) and be interoperable with std::tuple?

I'd say the most important use case is to (1) allow binary comparison between two same element-typed internal tuples as that is what we may encounter within oneDPL algorithm calls. This allows a much simpler implementation.

Second most interesting would be (2) comparisons between onedpl tuples with different element types as users could contrive examples which this is necessary inside of a oneDPL call.

Least interesting is (3) interoperability with std::tuple (it is a "nice to have" feature in my view).

I'd be willing to drop (3) from this PR, it causes the most complication in implementation and has the least utility.

[danhoeflinger]

I'd be willing to drop (3) from this PR, it causes the most complication in implementation and has the least utility.

I've re-organized the code to make clear which code is to support which functionality. The first set of operators covers 1+2, the second and third sets of operators are required to enable (3).

(If we wanted to only support (1), we could reduce the complexity of the first set of operators to just use const tuple& type for rhs and lhs)

[SergeyKopienko]

@danhoeflinger It's not the result of you PR, but for operator=(const tuple<U1, U...>& other) what about the case when `this == &other' ? I mean probably we should avoid self-assignment...

[danhoeflinger]

@danhoeflinger It's not the result of you PR, but for operator=(const tuple<U1, U...>& other) what about the case when `this == &other' ? I mean probably we should avoid self-assignment...

I believe the case you speak of cannot happen here because there is a defaulted copy assignment operator which should handle the cases where the type of the other matches this (when the types don't match, the object instance itself wont either). The implementation you are referring to without the self-assignment check is for a tuple with arbitrary (but convertible element types).

[SergeyKopienko]

@danhoeflinger It's not the result of you PR, but for operator=(const tuple<U1, U...>& other) what about the case when `this == &other' ? I mean probably we should avoid self-assignment...

I believe the case you speak of cannot happen here because there is a defaulted copy assignment operator which should handle the cases where the type of the other matches this (when the types don't match, the object instance itself wont either). The implementation you are referring to without the self-assignment check is for a tuple with arbitrary (but convertible element types).

OK, np.

[danhoeflinger]

After an offline discussion with @rarutyun , we have decided not to target the coming release with this PR, and take some time to investigate some context around it. Specifically, we want to take a look at std::sort with a vector of std::tuple, and with zip_iterator, to understand if there are any other limitations which hold back such a case.

[SergeyKopienko]

@danhoeflinger How do you think, should we support three-way comparison <=> too (https://en.cppreference.com/w/cpp/language/operator_comparison)?

[danhoeflinger]

@danhoeflinger How do you think, should we support three-way comparison <=> too (https://en.cppreference.com/w/cpp/language/operator_comparison)?

I think we discussed this before https://github.com/oneapi-src/oneDPL/pull/1472#issuecomment-2032405450 . I did find the macro which I believe should correspond to the feature implementation: __cpp_lib_three_way_comparison from https://en.cppreference.com/w/cpp/feature_test (https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1614r2.html)

I suppose we can probably follow that macro for when to switch it on and remove the standalone operators. I'll take a little closer look at this.

Thanks

[akukanov]

Regarding operator<=> - since there are internal helpers __equal and __less anyway, why not implement a three-way comparison helper instead and use it in all operators? Then if the feature macro is set, we can define just == and <=> and let the C++ implementation do the rest, otherwise we define everything,

[danhoeflinger]

Regarding operator<=> - since there are internal helpers __equal and __less anyway, why not implement a three-way comparison helper instead and use it in all operators? Then if the feature macro is set, we can define just == and <=> and let the C++ implementation do the rest, otherwise we define everything,

I suppose we could do this, but we would want to implement a three-way comparison helper in different ways different ways depending on if __cpp_lib_three_way_comparison is set, because we rely upon the building block of comparing the elements themselves (and we wont have access to <=> for the elements without that feature macro).

I may be misunderstanding, but I think it may be better to just use __equal and __less directly when __cpp_lib_three_way_comparison is not set, rather than building <=> and then decoding it back into individual operators. If we don't do it this way, I think we may be adding unnecessary instructions in some cases.

[akukanov]

we would want to implement a three-way comparison helper in different ways depending on if __cpp_lib_three_way_comparison is set

Not sure about that. I mean, we can, but that does not mean we should. We can as well do something like this:

template <typename _Tuple1, typename _Tuple2, int I = 0>
constexpr int
__three_way_comp(const _Tuple1& __lhs, const _Tuple2& __rhs)
{
    if constexpr (I < std::tuple_size_v<_Tuple1>)
    {
        auto __left = std::get<I>(__lhs);
        auto __right = std::get<I>(__rhs);
        if (__left == __right)
            return oneapi::dpl::__internal::__three_way_comp<_Tuple1, _Tuple2, I + 1>(__lhs, __rhs);
        else if (__left < __right)
            return -1;
        else
            return 1;
    else
    {
        return 0;
    }
}

The key difference perhaps is that both == and < are always required for tuple parameters.

But I am not that bothered about supporting the spaceship operator. Duplicating essentially the same code three times bothers me much more in this patch.

[danhoeflinger]

The key difference perhaps is that both == and < are always required for tuple parameters.

Yes, these are the extra instructions I was referring to.

But I am not that bothered about supporting the spaceship operator. Duplicating essentially the same code three times bothers me much more in this patch.

Fair enough. Yes, I spent some time trying to figure out how to avoid replication this but was unable to come up with any satisfactory solution. We could decline to support all combinations, but it seems like if we are adding this support we should allow it to work with std::tuple fully and across non-matching but comparable element types. We could possibly consolidate the code some with preprocessor macros, but I think that may be worse in the end.

The helpers at least allow us to only repeat the very simple portion of this.

[danhoeflinger]

@SergeyKopienko @akukanov After exploring this a little bit, and running into a few complexities of the spaceship operator, I propose to merge this PR with the current level of functionality (no spaceship), and if we deem it important to support in the future, we can return to this and add support later.

My reasoning:

1. It does not seem trivial to add, there are some aspects which must be considered. For instance, I believe the type of return value should depend upon the types compared (strong_ordering, partial_ordering, weak_ordering). [edit: I suppose this is worked out with std::common_comparison_category_t, but in any case, it adds complexity]
2. No one is asking for the spaceship, but they are asking for the C++17 comparision operators.
3. It doesn't seem to solve the frustrating things about this PR (repetitions of implementations).
4. The current level of support should not prevent us from implementing the spaceship in the future.

All considered, it seems to me to be not worth the time and effort it would take to accomplish.

I am open to suggestion on how to reduce the redundancy in the current functionality.