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.