From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 48) id 41FB13858C83; Tue, 19 Apr 2022 14:54:54 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 41FB13858C83 From: "glisse at gcc dot 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 X-Bugzilla-Reason: CC X-Bugzilla-Type: new X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: gcc X-Bugzilla-Component: libstdc++ X-Bugzilla-Version: 12.0 X-Bugzilla-Keywords: missed-optimization X-Bugzilla-Severity: enhancement X-Bugzilla-Who: glisse at gcc dot gnu.org X-Bugzilla-Status: UNCONFIRMED X-Bugzilla-Resolution: X-Bugzilla-Priority: P3 X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org X-Bugzilla-Target-Milestone: --- X-Bugzilla-Flags: X-Bugzilla-Changed-Fields: bug_id short_desc product version bug_status keywords bug_severity priority component assigned_to reporter target_milestone Message-ID: Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/ Auto-Submitted: auto-generated MIME-Version: 1.0 X-BeenThere: gcc-bugs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-bugs mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 19 Apr 2022 14:54:54 -0000 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=3D105308 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 t= op 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 + executi= on policy. This specialization would be easier to implement for a whole tree t= han 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 poss= ibly 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.=