public inbox for gcc-bugs@sourceware.org help / color / mirror / Atom feed
From: "glisse at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org> To: gcc-bugs@gcc.gnu.org Subject: [Bug libstdc++/105308] New: Specialize for_each Date: Tue, 19 Apr 2022 14:54:54 +0000 [thread overview] Message-ID: <bug-105308-4@http.gcc.gnu.org/bugzilla/> (raw) 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.
next reply other threads:[~2022-04-19 14:54 UTC|newest] Thread overview: 4+ messages / expand[flat|nested] mbox.gz Atom feed top 2022-04-19 14:54 glisse at gcc dot gnu.org [this message] 2022-04-19 15:22 ` [Bug libstdc++/105308] " redi at gcc dot gnu.org 2022-04-19 16:05 ` glisse at gcc dot gnu.org 2022-04-19 16:41 ` redi at gcc dot gnu.org
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=bug-105308-4@http.gcc.gnu.org/bugzilla/ \ --to=gcc-bugzilla@gcc.gnu.org \ --cc=gcc-bugs@gcc.gnu.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).