[libc++][pstl] Implement tag dispatching

[rarutyun]

Summary

I believe the approach is agreed.

Tag dispatching implementation is complete with all planned changes to do.

Welcome again for review:)

Depends on: https://reviews.llvm.org/D114624

[rarutyun]

pstl/include/pstl/internal/parallel_backend_serial.h

57

Note that this overload supposed to go away when all the changes are made. Currently there is a code that depends on that.

[• Quuxplusone]

pstl/include/pstl/internal/algorithm_fwd.h

19

I believe you need to add pstl/include to
https://github.com/google/llvm-premerge-checks/blob/main/scripts/clang-tidy.ignore
(Although why this file is in a Google repo instead of the llvm-project repo, I don't know!)

255

Throughout: On function declarations, I think it's unhelpful to have parameter names like _Tag __tag or (below) _ExecutionPolicy&& __exec. I would remove those parameter names. The names __first, __last, __pred are arguably more helpful; but for consistency I'd probably remove them too. (Or rather, don't add them.)

pstl/include/pstl/internal/execution_impl.h

31–33

decltype(T{}) is just T.

39–42

Could this be:

template <typename... _IteratorTypes>
using __are_random_access_iterators = decltype(__internal::__is_iterator_of<
    std::random_access_iterator_tag, _IteratorTypes...>(0));

(Notice the ADL-proofing on __is_iterator_of.)

IIUC, the intent is that __are_random_access_iterators<int*, char*> is true_type but __are_random_access_iterators<int*, std::list<int>::iterator> is false_type, right?

Or if C++17 is permitted, then

template <typename... _IteratorTypes>
using __are_random_access_iterators = std::bool_constant<
    (std::is_base_of_v<std::random_access_iterator_tag,
                       typename std::iterator_traits<_IteratorTypes>::iterator_category> && ...)
>;

107

Rather than split the declaration across #ifs, it would be easier to read (for both humans and computers) if this were just

#if defined(_PSTL_PAR_BACKEND_TBB)
 using __par_backend_tag = __tbb_backend;
#elif _PSTAL_PAR_BACKEND_SERIAL
 using __par_backend_tag = __serial_backend;
#else
 #error "A parallel backend must be specified"
#endif

(also note the probably-accidental inconsistent use of defined versus non-zero, and the bogus semicolon at the end of line 126)

116–129

IIUC, __is_vector is always true_type or false_type?
Would it be simpler to define...

template<bool _IsParallel, bool _IsVector>
struct __bikeshed_tag {
    using __is_vector = std::bool_constant<_IsVector>;
    using __is_parallel = std::bool_constant<_IsParallel>;
    using __backend_tag = std::conditional_t<_IsParallel, __par_backend_tag, void>;
};

template<bool _IsVector>
using __parallel_tag = __bikeshed_tag<true, _IsVector>;

template<bool _IsVector>
using __serial_tag = __bikeshed_tag<false, _IsVector>;

And then if you ever found any need to pattern-match on __bikeshed_tag<X, true>, it wouldn't be so awkward.

[zoecarver]

pstl/include/pstl/internal/algorithm_fwd.h

19

Additionally, it looks like these files may be nested one level too deep. I think this should be pstl/include/algorithm_fwd.h not pstl/include/pstl/include/algorithm_fwd.h.

[• Quuxplusone]

pstl/include/pstl/internal/algorithm_fwd.h

19

@zoecarver: No, I bet the nesting is right. Notice that it's

    pstl/include/pstl/internal/algorithm_fwd.h
not                   ^^^^^^^^
    pstl/include/pstl/include/algorithm_fwd.h

The pattern of "foo/include/foo/" ends up being pretty common in codebases I've seen, because there'll be a "foo/src" and a "foo/include", and then in order to make #include <foo/bar.h> to work after -I foo/include, you need to put your actual header file in "foo/include/foo/bar.h".

[rodgert]

pstl/include/pstl/internal/execution_impl.h

39–42

At least as it relates to libstdc++'s consumption of pstl, C++17 is the baseline expectation.

[rarutyun]

pstl/include/pstl/internal/algorithm_fwd.h

255

100% agree. Done

pstl/include/pstl/internal/execution_impl.h

31–33

There reason of decltype was SFINAE. iterator_category is not always the part of iterator_traits. I thought it might be useful when we adopt take this approach from PSTL upstream to oneDPL.

On the other hand, we don't have much to do when the passed types by users are not iterators. So, yeah, let's keep it simple. Probably if we need additional logic in our code we can make it in other place.

39–42

Or if C++17 is permitted, then

Sure, C++17 is permitted. std::conjunction is already C++17 API.

IIUC, the intent is that __are_random_access_iterators<int*, char*> is true_type but __are_random_access_iterators<int*, std::list<int>::iterator> is false_type, right?

right.

I think I made it even simpler (at least from my point of view) and I would prefer to leave it as is if no strong objections. I also would prefer to have such a logic separation for __are_random_access_iterators and __are_iterators_of

116–129

It probably would be simpler from searching standpoint but I don't think it's more correct comparing with what we have in the patch. serial_tag should not know about parallelism and backend. I don't tend to think that adding stubs (like void) is a good idea.

Probably I misunderstood the idea but I cannot find the applicability for using __is_parallel = std::bool_constant<_IsParallel>; line. It seems unnecessary to me because everything that we already have what we need to build the dispatch (I mean that __parallel_tag and __serial_tag are different types in your suggestion). Currently there is no need to read __is_parallel from somewhere.

What I do believe is we need to find better names for tags.

For backend tags I would propose serial_backend_tag and tbb_backend_tag instead of serial_backend and tbb_backend correspondently
For top level tags I would tend to think about parallel_pattern_tag, serial_pattern_tag, but probably "serial" is a bad word and "pattern" word makes the name too verbose. I am open for ideas

[• Quuxplusone]

pstl/include/pstl/internal/execution_impl.h

31–33

IIUC, you were thinking that using the decltype syntax would somehow "enable" SFINAE. That's not the case. SFINAE is happening regardless of the syntax you use.

template<class T> void f() -> decltype(typename T::nested_type{}) {}
template<class T> void f() -> typename T::nested_type {}

Both versions of f SFINAE away correctly when T=int (because substituting int into T::nested_type produces a failure, and substitution failure is not an error). The only thing that is different is that in the former case, we're also SFINAE-checking that T::nested_type{} is well-formed (i.e. T::nested_type is default-constructible from empty braces) whereas in the latter case we are checking only that it exists. (But this distinction shouldn't matter for tag types, which are always default-constructible.)

[rarutyun]

Add tag_dispatching mechanism for OpenMP backend

[rarutyun]

pstl/include/pstl/internal/execution_impl.h

31–33

Yes, you are right. Anyway, we current implementation it is not required anymore.

[rarutyun]

pstl/include/pstl/internal/algorithm_fwd.h

19

I believe you need to add pstl/include to
https://github.com/google/llvm-premerge-checks/blob/main/scripts/clang-tidy.ignore
(Although why this file is in a Google repo instead of the llvm-project repo, I don't know!)

I believe we will do that (if necessary) when enable CI for Parallel STL (which is one of the next steps after merging this patch). Currently I propose to just merge this changes ignoring clang-tidy (as it was done for previous patches as well)

19

    pstl/include/pstl/internal/algorithm_fwd.h
not                   ^^^^^^^^
    pstl/include/pstl/include/algorithm_fwd.h

I agree with @Quuxplusone here

[MikeDvorskiy]

In spite of my minor comments it LGTM.

pstl/include/pstl/internal/algorithm_fwd.h

402–403

I guess we have wrong clang format changes here. (As far as I remember our profile of clang-format options keeps return type on the separate line).

406–407

See the comment below.

pstl/include/pstl/internal/algorithm_impl.h

315–316

As far as I can see, here and in the other same places we don't in use parameter name tag in code, excepting type deduction (via decltype) of type that we already have. So, I would propose to omit this parameter name and define backend_tag as:

using backend_tag = typename parallel_tag<_IsVector>::__backend_tag;

It is not showstopper because it is not public API. So, it is up to you.

[rarutyun]

pstl/include/pstl/internal/algorithm_fwd.h

402–403

It's already inconsistent within the file. I suggest to make separate commit if we believe it's important. Locally I've applied clang-format for diff and that's the output

406–407

I guess you mean "above" instead of "below". Anyway, the answer is above:)

pstl/include/pstl/internal/algorithm_impl.h

315–316

Actually, in some places we use __tag parameter but not everywhere. Although, we could do using backend_tag with duplicating the whole type from template parameter I would prefer to keep it as it is because it (from my point of view) makes the code simpler and `backend_tag` line is not required to be changed if function parameter type is modified. Everything would be correctly deduced automatically would be correctly deduced automaticallyю

[rarutyun]

CI is green, @MikeDvorskiy and @rodgert approved that previously. I believe we can finally merge it.