[Bug libstdc++/51965] New: Redundant move constructions in heap algorithms

[Bug libstdc++/51965] New: Redundant move constructions in heap algorithms

[valyala at gmail dot com]

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.

[Bug libstdc++/51965] Redundant move constructions in heap algorithms

[valyala at gmail dot com]

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

[Bug libstdc++/51965] Redundant move constructions in heap algorithms

[chris at bubblescope dot net]

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.

[Bug libstdc++/51965] Redundant move constructions in heap algorithms

[redi at gcc dot gnu.org]

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.

[Bug libstdc++/51965] Redundant move constructions in heap algorithms

[paolo.carlini at oracle dot com]

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.

[Bug libstdc++/51965] Redundant move constructions in heap algorithms

[marc.glisse at normalesup dot org]

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.

[Bug libstdc++/51965] Redundant move constructions in heap algorithms

[paolo.carlini at oracle dot com]

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.

[Bug libstdc++/51965] Redundant move constructions in heap algorithms

[marc.glisse at normalesup dot org]

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.

[Bug libstdc++/51965] Redundant move constructions in heap algorithms

[paolo.carlini at oracle dot com]

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.

[Bug libstdc++/51965] Redundant move constructions in heap algorithms

[redi at gcc dot gnu.org]

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

[Bug libstdc++/51965] Redundant move constructions in heap algorithms

[glisse at gcc dot gnu.org]

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

[Bug libstdc++/51965] Redundant move constructions in heap algorithms

[jakub at gcc dot gnu.org]

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

[Bug libstdc++/51965] Redundant move constructions in heap algorithms

[jakub at gcc dot gnu.org]

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.

[Bug libstdc++/51965] Redundant move constructions in heap algorithms

[jakub at gcc dot gnu.org]

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.

[Bug libstdc++/51965] Redundant move constructions in heap algorithms

[jakub at gcc dot gnu.org]

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.

[Bug libstdc++/51965] Redundant move constructions in heap algorithms

[jakub at gcc dot gnu.org]

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

[Bug libstdc++/51965] Redundant move constructions in heap algorithms

[glisse at gcc dot gnu.org]

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.