[Bug libstdc++/105308] New: Specialize for_each

[Bug libstdc++/105308] New: Specialize for_each

[glisse at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105308

            Bug ID: 105308
           Summary: Specialize for_each
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: enhancement
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: glisse at gcc dot gnu.org
  Target Milestone: ---

Hello,

with a balanced binary tree, as used for instance in std::set or std::map, it
is relatively easy to perform an operation in parallel on all elements (like
for_each): recurse on the 2 subtrees in parallel (and probably assign the top
node to one of the subtrees arbitrarily). Of course there are technical
details, we don't store the size of subtrees so we may want to decide in
advance how deep to switch to sequential, etc. Doing this requires accessing
details of the tree implementation and cannot be done by a user (plus, for_each
doesn't seem to be a customization point...).

I am still confused that we have the traditional for_each, the new for_each
with execution policy, the new range for_each, but no mixed range + execution
policy. This specialization would be easier to implement for a whole tree than
for an arbitrary subrange. It is still possible there, but likely less
balanced, and we may need a first pass to find the common ancestor and possibly
other relevant information (or check if the range is the whole container if
that's possible and only optimize that case).

Possibly some other containers could specialize for_each, although it isn't as
obvious.

Actually, even the sequential for_each could benefit from a specialization for
various containers. Recursing on subtrees is a bit cheaper than having the
iterator move up and down, forward_list could avoid pointing to the previous
element, dequeue could try to split at block boundaries, etc.

Other algorithms that iterate through a range like reduce, all_of, etc could
also benefit, hopefully most are simple wrappers around others so few would
need a specialization.

[Bug libstdc++/105308] Specialize for_each

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105308

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
I'm unclear what the request is. Are you proposing this for the parallel
std::for_each with an execution policy? That code comes from the PSTL project
which is part of LLVM, and maintained by Intel, so enhancements to it should
ideally be done upstream.

[Bug libstdc++/105308] Specialize for_each

[glisse at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105308

--- Comment #2 from Marc Glisse <glisse at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #1)
> I'm unclear what the request is.

The list isn't super clear to me either, any sensible specialization of a
standard algorithm for a standard container. Even simply
ranges::for_each(std::set,*) looks like it could be a bit faster with a
specialization instead of using iterators.

> Are you proposing this for the parallel
> std::for_each with an execution policy?

Yes, that's the first motivation.

> That code comes from the PSTL project which is part of LLVM,
> and maintained by Intel, so enhancements to it should ideally be done upstream.

But the code would need to use private interfaces of libstdc++'s _Rb_tree. Does
PSTL contain a lot of special code, with one variant for libstdc++ / libc++ /
other, that uses internals of the datastructures?

[Bug libstdc++/105308] Specialize for_each

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105308

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Marc Glisse from comment #2)
> (In reply to Jonathan Wakely from comment #1)
> > That code comes from the PSTL project which is part of LLVM,
> > and maintained by Intel, so enhancements to it should ideally be done upstream.
> 
> But the code would need to use private interfaces of libstdc++'s _Rb_tree.
> Does PSTL contain a lot of special code, with one variant for libstdc++ /
> libc++ / other, that uses internals of the datastructures?

No, the core of it is portable, with some impl-specific headers to incorporate
it into either libstdc++ or libc++ (although I don't think libc++ actually uses
it yet).

So if we want to use the internals of our _Rb_tree then yes, we'll need some
downstream changes in our copy.