public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug libstdc++/51965] New: Redundant move constructions in heap algorithms
@ 2012-01-23 13:55 valyala at gmail dot com
2012-01-23 14:04 ` [Bug libstdc++/51965] " valyala at gmail dot com
` (15 more replies)
0 siblings, 16 replies; 17+ messages in thread
From: valyala at gmail dot com @ 2012-01-23 13:55 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51965
Bug #: 51965
Summary: Redundant move constructions in heap algorithms
Classification: Unclassified
Product: gcc
Version: 4.7.0
Status: UNCONFIRMED
Severity: enhancement
Priority: P3
Component: libstdc++
AssignedTo: unassigned@gcc.gnu.org
ReportedBy: valyala@gmail.com
Created attachment 26426
--> http://gcc.gnu.org/bugzilla/attachment.cgi?id=26426
Eliminate unnecessary move constructions in stl_heap.h
Currently Heap implementation (
http://gcc.gnu.org/viewcvs/trunk/libstdc%2B%2B-v3/include/bits/stl_heap.h?revision=181987&view=markup
) contains redundant move constructions. These constructors are invoked when
passing rvalue __value to std::__push_heap() and std::__adjust_heap(). It would
be better passing the __value into these functions by reference instead. This
eliminates redundant move constructions and results in 3x reduction of the
number of move constructor calls inside heap functions such as make_heap() and
sort_heap().
See the attached patch for details.
^ permalink raw reply [flat|nested] 17+ messages in thread
* [Bug libstdc++/51965] Redundant move constructions in heap algorithms
2012-01-23 13:55 [Bug libstdc++/51965] New: Redundant move constructions in heap algorithms valyala at gmail dot com
@ 2012-01-23 14:04 ` valyala at gmail dot com
2012-01-23 14:10 ` chris at bubblescope dot net
` (14 subsequent siblings)
15 siblings, 0 replies; 17+ messages in thread
From: valyala at gmail dot com @ 2012-01-23 14:04 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51965
--- Comment #1 from Aliaksandr Valialkin <valyala at gmail dot com> 2012-01-23 13:51:16 UTC ---
Created attachment 26427
--> http://gcc.gnu.org/bugzilla/attachment.cgi?id=26427
Testcase for determining redundant move constructions in stl_heap
^ permalink raw reply [flat|nested] 17+ messages in thread
* [Bug libstdc++/51965] Redundant move constructions in heap algorithms
2012-01-23 13:55 [Bug libstdc++/51965] New: Redundant move constructions in heap algorithms valyala at gmail dot com
2012-01-23 14:04 ` [Bug libstdc++/51965] " valyala at gmail dot com
@ 2012-01-23 14:10 ` chris at bubblescope dot net
2012-01-23 14:52 ` redi at gcc dot gnu.org
` (13 subsequent siblings)
15 siblings, 0 replies; 17+ messages in thread
From: chris at bubblescope dot net @ 2012-01-23 14:10 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51965
Chris Jefferson <chris at bubblescope dot net> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |chris at bubblescope dot
| |net
--- Comment #2 from Chris Jefferson <chris at bubblescope dot net> 2012-01-23 14:04:43 UTC ---
>From my memory of originally writing this, from the old non-moving version,
these moves were originally copies.
The reason I believe those moves are there is because in some cases the
original location is written over. For example trace the behaviour of push_heap
/ __push_heap.
I'm not saying your patch is wrong, and I can't currently compile a g++ svn
head to check, but have you run the tester with your patch, and have you
checked the logic carefully to make sure you can't scribble over the value in
the algorithm?
There may will still be a way of reducing the work to just one move of course,
at the start of the algorithm.
Sorry if you have already considered this, but I remember bits of this being
subtle.
^ permalink raw reply [flat|nested] 17+ messages in thread
* [Bug libstdc++/51965] Redundant move constructions in heap algorithms
2012-01-23 13:55 [Bug libstdc++/51965] New: Redundant move constructions in heap algorithms valyala at gmail dot com
2012-01-23 14:04 ` [Bug libstdc++/51965] " valyala at gmail dot com
2012-01-23 14:10 ` chris at bubblescope dot net
@ 2012-01-23 14:52 ` redi at gcc dot gnu.org
2012-01-23 15:40 ` paolo.carlini at oracle dot com
` (12 subsequent siblings)
15 siblings, 0 replies; 17+ messages in thread
From: redi at gcc dot gnu.org @ 2012-01-23 14:52 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51965
--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> 2012-01-23 14:11:08 UTC ---
Thanks, Chris.
I haven't looked at the patch or test yet, but I'm a little surprised the
compiler can't elide the move constructors.
^ permalink raw reply [flat|nested] 17+ messages in thread
* [Bug libstdc++/51965] Redundant move constructions in heap algorithms
2012-01-23 13:55 [Bug libstdc++/51965] New: Redundant move constructions in heap algorithms valyala at gmail dot com
` (2 preceding siblings ...)
2012-01-23 14:52 ` redi at gcc dot gnu.org
@ 2012-01-23 15:40 ` paolo.carlini at oracle dot com
2012-01-23 23:46 ` marc.glisse at normalesup dot org
` (11 subsequent siblings)
15 siblings, 0 replies; 17+ messages in thread
From: paolo.carlini at oracle dot com @ 2012-01-23 15:40 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51965
--- Comment #4 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-01-23 15:26:34 UTC ---
Indeed, I double checked that *before* changing the functions to use moves we
had plain copies, that is the original HP/SGI functions had copies, nothing was
passed by reference. Thus just doing what is suggested is unlikely to be
correct.
^ permalink raw reply [flat|nested] 17+ messages in thread
* [Bug libstdc++/51965] Redundant move constructions in heap algorithms
2012-01-23 13:55 [Bug libstdc++/51965] New: Redundant move constructions in heap algorithms valyala at gmail dot com
` (3 preceding siblings ...)
2012-01-23 15:40 ` paolo.carlini at oracle dot com
@ 2012-01-23 23:46 ` marc.glisse at normalesup dot org
2012-01-24 1:16 ` paolo.carlini at oracle dot com
` (10 subsequent siblings)
15 siblings, 0 replies; 17+ messages in thread
From: marc.glisse at normalesup dot org @ 2012-01-23 23:46 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51965
Marc Glisse <marc.glisse at normalesup dot org> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |marc.glisse at normalesup
| |dot org
--- Comment #5 from Marc Glisse <marc.glisse at normalesup dot org> 2012-01-23 23:18:20 UTC ---
(The split into push_heap and __push_heap is just so the first part can be
inlined without the second, right?)
A more direct adaptation of the old code to rvalue references would be:
std::__push_heap(__first, _DistanceType((__last - __first) - 1),
_DistanceType(0), _ValueType(_GLIBCXX_MOVE(*(__last -
1))));
Without the named temporary value, the compiler can perform copy elision.
Aliaksandr's patch looks like a different way to achieve the same goal.
Note that the current code thus seems to have a performance regression in C++03
compared to before the introduction of moves.
^ permalink raw reply [flat|nested] 17+ messages in thread
* [Bug libstdc++/51965] Redundant move constructions in heap algorithms
2012-01-23 13:55 [Bug libstdc++/51965] New: Redundant move constructions in heap algorithms valyala at gmail dot com
` (4 preceding siblings ...)
2012-01-23 23:46 ` marc.glisse at normalesup dot org
@ 2012-01-24 1:16 ` paolo.carlini at oracle dot com
2012-01-24 11:08 ` marc.glisse at normalesup dot org
` (9 subsequent siblings)
15 siblings, 0 replies; 17+ messages in thread
From: paolo.carlini at oracle dot com @ 2012-01-24 1:16 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51965
Paolo Carlini <paolo.carlini at oracle dot com> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |jwakely.gcc at gmail dot
| |com
--- Comment #6 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-01-24 00:24:44 UTC ---
Ah good, if it's so easy to enable the elision, this kind of change looks safe
to me. But __pop_heap doesn't seem so straightforward to tweak, we also changed
a bit the interfaces. Marc can you submit a complete patch? Otherwise, so close
to the branch for 4.7.0 I'm not sure I will be able to work on this, or maybe
you can coordinate with Jon.
^ permalink raw reply [flat|nested] 17+ messages in thread
* [Bug libstdc++/51965] Redundant move constructions in heap algorithms
2012-01-23 13:55 [Bug libstdc++/51965] New: Redundant move constructions in heap algorithms valyala at gmail dot com
` (5 preceding siblings ...)
2012-01-24 1:16 ` paolo.carlini at oracle dot com
@ 2012-01-24 11:08 ` marc.glisse at normalesup dot org
2012-01-24 13:04 ` paolo.carlini at oracle dot com
` (8 subsequent siblings)
15 siblings, 0 replies; 17+ messages in thread
From: marc.glisse at normalesup dot org @ 2012-01-24 11:08 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51965
--- Comment #7 from Marc Glisse <marc.glisse at normalesup dot org> 2012-01-24 10:49:38 UTC ---
(In reply to comment #6)
> But __pop_heap doesn't seem so straightforward to tweak, we also changed
> a bit the interfaces.
At first glance, I am not sure why pop_heap can end up calling push_heap, so I
would need to really look at the code (no time...).
> Marc can you submit a complete patch?
Not now, sorry. Maybe in a few weeks... (no promise)
I haven't reviewed Aliaksandr's patch, but the approach seems sensible.
> Otherwise, so close to the branch for 4.7.0 I'm not sure I will be able to work on this,
It may be safer to patch it in 4.8.0 and backport to 4.7.1.
^ permalink raw reply [flat|nested] 17+ messages in thread
* [Bug libstdc++/51965] Redundant move constructions in heap algorithms
2012-01-23 13:55 [Bug libstdc++/51965] New: Redundant move constructions in heap algorithms valyala at gmail dot com
` (6 preceding siblings ...)
2012-01-24 11:08 ` marc.glisse at normalesup dot org
@ 2012-01-24 13:04 ` paolo.carlini at oracle dot com
2013-07-25 8:34 ` redi at gcc dot gnu.org
` (7 subsequent siblings)
15 siblings, 0 replies; 17+ messages in thread
From: paolo.carlini at oracle dot com @ 2012-01-24 13:04 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51965
Paolo Carlini <paolo.carlini at oracle dot com> changed:
What |Removed |Added
----------------------------------------------------------------------------
Status|UNCONFIRMED |NEW
Last reconfirmed| |2012-01-24
CC| |paolo.carlini at oracle dot
| |com
Ever Confirmed|0 |1
--- Comment #8 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-01-24 11:58:33 UTC ---
I agree. Let's make sure we actually handle this, as soon as 4.7.0 is out.
^ permalink raw reply [flat|nested] 17+ messages in thread
* [Bug libstdc++/51965] Redundant move constructions in heap algorithms
2012-01-23 13:55 [Bug libstdc++/51965] New: Redundant move constructions in heap algorithms valyala at gmail dot com
` (7 preceding siblings ...)
2012-01-24 13:04 ` paolo.carlini at oracle dot com
@ 2013-07-25 8:34 ` redi at gcc dot gnu.org
2013-09-06 9:52 ` glisse at gcc dot gnu.org
` (6 subsequent siblings)
15 siblings, 0 replies; 17+ messages in thread
From: redi at gcc dot gnu.org @ 2013-07-25 8:34 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51965
Jonathan Wakely <redi at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Target Milestone|--- |4.9.0
^ permalink raw reply [flat|nested] 17+ messages in thread
* [Bug libstdc++/51965] Redundant move constructions in heap algorithms
2012-01-23 13:55 [Bug libstdc++/51965] New: Redundant move constructions in heap algorithms valyala at gmail dot com
` (8 preceding siblings ...)
2013-07-25 8:34 ` redi at gcc dot gnu.org
@ 2013-09-06 9:52 ` glisse at gcc dot gnu.org
2014-04-22 11:36 ` jakub at gcc dot gnu.org
` (5 subsequent siblings)
15 siblings, 0 replies; 17+ messages in thread
From: glisse at gcc dot gnu.org @ 2013-09-06 9:52 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51965
--- Comment #9 from Marc Glisse <glisse at gcc dot gnu.org> ---
Most recent discussion about this:
http://gcc.gnu.org/ml/libstdc++/2013-07/msg00105.html
^ permalink raw reply [flat|nested] 17+ messages in thread
* [Bug libstdc++/51965] Redundant move constructions in heap algorithms
2012-01-23 13:55 [Bug libstdc++/51965] New: Redundant move constructions in heap algorithms valyala at gmail dot com
` (9 preceding siblings ...)
2013-09-06 9:52 ` glisse at gcc dot gnu.org
@ 2014-04-22 11:36 ` jakub at gcc dot gnu.org
2014-07-16 13:28 ` jakub at gcc dot gnu.org
` (4 subsequent siblings)
15 siblings, 0 replies; 17+ messages in thread
From: jakub at gcc dot gnu.org @ 2014-04-22 11:36 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51965
Jakub Jelinek <jakub at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Target Milestone|4.9.0 |4.9.1
--- Comment #10 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 4.9.0 has been released
^ permalink raw reply [flat|nested] 17+ messages in thread
* [Bug libstdc++/51965] Redundant move constructions in heap algorithms
2012-01-23 13:55 [Bug libstdc++/51965] New: Redundant move constructions in heap algorithms valyala at gmail dot com
` (10 preceding siblings ...)
2014-04-22 11:36 ` jakub at gcc dot gnu.org
@ 2014-07-16 13:28 ` jakub at gcc dot gnu.org
2014-10-30 10:38 ` jakub at gcc dot gnu.org
` (3 subsequent siblings)
15 siblings, 0 replies; 17+ messages in thread
From: jakub at gcc dot gnu.org @ 2014-07-16 13:28 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=51965
Jakub Jelinek <jakub at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Target Milestone|4.9.1 |4.9.2
--- Comment #11 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 4.9.1 has been released.
^ permalink raw reply [flat|nested] 17+ messages in thread
* [Bug libstdc++/51965] Redundant move constructions in heap algorithms
2012-01-23 13:55 [Bug libstdc++/51965] New: Redundant move constructions in heap algorithms valyala at gmail dot com
` (11 preceding siblings ...)
2014-07-16 13:28 ` jakub at gcc dot gnu.org
@ 2014-10-30 10:38 ` jakub at gcc dot gnu.org
2015-06-26 20:03 ` jakub at gcc dot gnu.org
` (2 subsequent siblings)
15 siblings, 0 replies; 17+ messages in thread
From: jakub at gcc dot gnu.org @ 2014-10-30 10:38 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=51965
Jakub Jelinek <jakub at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Target Milestone|4.9.2 |4.9.3
--- Comment #12 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 4.9.2 has been released.
^ permalink raw reply [flat|nested] 17+ messages in thread
* [Bug libstdc++/51965] Redundant move constructions in heap algorithms
2012-01-23 13:55 [Bug libstdc++/51965] New: Redundant move constructions in heap algorithms valyala at gmail dot com
` (12 preceding siblings ...)
2014-10-30 10:38 ` jakub at gcc dot gnu.org
@ 2015-06-26 20:03 ` jakub at gcc dot gnu.org
2015-06-26 20:30 ` jakub at gcc dot gnu.org
2020-03-29 19:20 ` glisse at gcc dot gnu.org
15 siblings, 0 replies; 17+ messages in thread
From: jakub at gcc dot gnu.org @ 2015-06-26 20:03 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=51965
--- Comment #13 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 4.9.3 has been released.
^ permalink raw reply [flat|nested] 17+ messages in thread
* [Bug libstdc++/51965] Redundant move constructions in heap algorithms
2012-01-23 13:55 [Bug libstdc++/51965] New: Redundant move constructions in heap algorithms valyala at gmail dot com
` (13 preceding siblings ...)
2015-06-26 20:03 ` jakub at gcc dot gnu.org
@ 2015-06-26 20:30 ` jakub at gcc dot gnu.org
2020-03-29 19:20 ` glisse at gcc dot gnu.org
15 siblings, 0 replies; 17+ messages in thread
From: jakub at gcc dot gnu.org @ 2015-06-26 20:30 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=51965
Jakub Jelinek <jakub at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Target Milestone|4.9.3 |4.9.4
^ permalink raw reply [flat|nested] 17+ messages in thread
* [Bug libstdc++/51965] Redundant move constructions in heap algorithms
2012-01-23 13:55 [Bug libstdc++/51965] New: Redundant move constructions in heap algorithms valyala at gmail dot com
` (14 preceding siblings ...)
2015-06-26 20:30 ` jakub at gcc dot gnu.org
@ 2020-03-29 19:20 ` glisse at gcc dot gnu.org
15 siblings, 0 replies; 17+ messages in thread
From: glisse at gcc dot gnu.org @ 2020-03-29 19:20 UTC (permalink / raw)
To: gcc-bugs
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=51965
--- Comment #19 from Marc Glisse <glisse at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #16)
> (In reply to Marc Glisse from comment #5)
> > (The split into push_heap and __push_heap is just so the first part can be
> > inlined without the second, right?)
> >
> > A more direct adaptation of the old code to rvalue references would be:
> >
> > std::__push_heap(__first, _DistanceType((__last - __first) - 1),
> > _DistanceType(0), _ValueType(_GLIBCXX_MOVE(*(__last -
> > 1))));
>
> I tried doing this and it didn't seem to help the testcase attached here.
push_heap(): default_ctors=0, copy_ctors=0, copy_assignments=0, swaps=0,
[-cheap_dtors=1998,-] {+cheap_dtors=999,+} expensive_dtors=0,
[-move_ctors=1998,-] {+move_ctors=999,+} cheap_move_assignments=2201,
expensive_move_assignments=0, comparisons=2196
It doesn't help the other operations, but it has some effect on this one.
^ permalink raw reply [flat|nested] 17+ messages in thread
end of thread, other threads:[~2020-03-29 19:20 UTC | newest]
Thread overview: 17+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2012-01-23 13:55 [Bug libstdc++/51965] New: Redundant move constructions in heap algorithms valyala at gmail dot com
2012-01-23 14:04 ` [Bug libstdc++/51965] " valyala at gmail dot com
2012-01-23 14:10 ` chris at bubblescope dot net
2012-01-23 14:52 ` redi at gcc dot gnu.org
2012-01-23 15:40 ` paolo.carlini at oracle dot com
2012-01-23 23:46 ` marc.glisse at normalesup dot org
2012-01-24 1:16 ` paolo.carlini at oracle dot com
2012-01-24 11:08 ` marc.glisse at normalesup dot org
2012-01-24 13:04 ` paolo.carlini at oracle dot com
2013-07-25 8:34 ` redi at gcc dot gnu.org
2013-09-06 9:52 ` glisse at gcc dot gnu.org
2014-04-22 11:36 ` jakub at gcc dot gnu.org
2014-07-16 13:28 ` jakub at gcc dot gnu.org
2014-10-30 10:38 ` jakub at gcc dot gnu.org
2015-06-26 20:03 ` jakub at gcc dot gnu.org
2015-06-26 20:30 ` jakub at gcc dot gnu.org
2020-03-29 19:20 ` glisse at gcc dot gnu.org
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).