[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.