This is an archive of the discontinued LLVM Phabricator instance.

[libc++][pstl] Implement tag dispatching
ClosedPublic

Authored by rarutyun on Jun 17 2021, 3:53 PM.

Details

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

Diff Detail

Event Timeline

rarutyun requested review of this revision.Jun 17 2021, 3:53 PM
rarutyun created this revision.
Herald added a reviewer: Restricted Project. · View Herald TranscriptJun 17 2021, 3:53 PM
rarutyun added inline comments.Jun 17 2021, 3:57 PM
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 added inline comments.
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> && ...)
>;
102

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)

111–124

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 added inline comments.Jun 28 2021, 8:44 AM
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.

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 accepted this revision.Jul 2 2021, 10:04 AM
rodgert added inline comments.
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 updated this revision to Diff 370249.Sep 2 2021, 6:09 AM
rarutyun updated this revision to Diff 370327.Sep 2 2021, 10:47 AM
rarutyun marked 3 inline comments as done.Sep 2 2021, 11:08 AM
rarutyun added inline comments.
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

111–124

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

rarutyun edited the summary of this revision. (Show Details)Sep 2 2021, 11:10 AM
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 edited the summary of this revision. (Show Details)Nov 26 2021, 3:09 AM
rarutyun updated this revision to Diff 390120.Nov 26 2021, 2:10 PM
rarutyun marked an inline comment as done.

Add tag_dispatching mechanism for OpenMP backend

zoecarver resigned from this revision.Dec 2 2021, 1:51 PM
rarutyun added inline comments.Jan 17 2022, 6:12 PM
pstl/include/pstl/internal/execution_impl.h
31–33

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

cjdb resigned from this revision.Jan 18 2022, 1:37 PM
rarutyun added inline comments.Jan 21 2022, 6:57 AM
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 accepted this revision.Jan 21 2022, 8:08 AM

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
308–309

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 updated this revision to Diff 402591.Jan 24 2022, 10:50 AM
rarutyun removed reviewers: zoecarver, cjdb.
rarutyun added inline comments.Jan 26 2022, 8:36 AM
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
308–309

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 updated this revision to Diff 403287.Jan 26 2022, 8:44 AM
rarutyun updated this revision to Diff 403685.Jan 27 2022, 8:58 AM

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

This revision was not accepted when it landed; it landed in state Needs Review.Jan 27 2022, 5:15 PM
This revision was automatically updated to reflect the committed changes.