[Bug libstdc++/53263] New: priority_queue is very slow if -D_GLIBCXX_DEBUG is used

[Bug libstdc++/53263] New: priority_queue is very slow if -D_GLIBCXX_DEBUG is used

[dominik.strasser@onespin-solutions.com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53263

             Bug #: 53263
           Summary: priority_queue is very slow if -D_GLIBCXX_DEBUG is
                    used
    Classification: Unclassified
           Product: gcc
           Version: 4.7.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: dominik.strasser@onespin-solutions.com


Created attachment 27332
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=27332
Minimalistic example demonstrating the problem

I've measured the most simplistic usage of priority queue.
With 5,000 elements, the run time is:
real    0m0.005s
user    0m0.002s
sys     0m0.002s
With 10,000 elements, the run time is:
real    0m0.006s
user    0m0.002s
sys     0m0.002s

If I switch on -D_GLIBCXX_DEBUG, the situation changes:
5,000 elements:
real    0m11.216s
user    0m11.210s
sys     0m0.003s

10,000 elements:
real    0m48.354s
user    0m48.344s
sys     0m0.003s

20,000 elements:
real    2m56.971s
user    2m56.941s
sys     0m0.002s

So in addition to some overhead, there seems to be some quadratic behavior
inside the debug version as the run time is 4x for 2x elements.

[Bug libstdc++/53263] priority_queue is very slow if -D_GLIBCXX_DEBUG is used

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53263

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |fdumont at gcc dot gnu.org
           Severity|normal                      |enhancement

--- Comment #1 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-05-07 12:05:40 UTC ---
I don't think we are making any promises in terms of debug-mode performance. Is
it better for other debug-mode implementations doing checks of similar
strength? 

Maybe Francois has ideas, adding him in CC. If I remember correctly, in some
cases we have been able to make progress rather easily by simply going to
unchecked iterators before forwarding to internal implementation details.

[Bug libstdc++/53263] priority_queue is very slow if -D_GLIBCXX_DEBUG is used

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53263

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2012-05-07
     Ever Confirmed|0                           |1

--- Comment #2 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-05-07 12:06:19 UTC ---
CC-ing Francois.

[Bug libstdc++/53263] priority_queue is very slow if -D_GLIBCXX_DEBUG is used

[dominik.strasser@onespin-solutions.com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53263

--- Comment #3 from dominik.strasser@onespin-solutions.com 2012-05-07 12:38:26 UTC ---
(In reply to comment #1)
> I don't think we are making any promises in terms of debug-mode performance. Is
> it better for other debug-mode implementations doing checks of similar
> strength? 
I see that the other containers have a performance which is comparable to the
non-debug counterpart.
priority_queue just kills some of my tests as it doesn't return after hours.

[Bug libstdc++/53263] priority_queue is very slow if -D_GLIBCXX_DEBUG is used

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53263

--- Comment #4 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-05-07 12:54:36 UTC ---
I see, I see.

First, I notice that we don't have a specific debug/ version of it, thus you
are using the normal version + debug-mode std::vector and std::????_heap
algorithms as implementation details. Likely the latter are the problem, I
think we already noticed somewhere that std::push_heap & company check a lot,
check at every step that a proper heap is passed, but I don't remember the
outcome of that discussion.

[Bug libstdc++/53263] priority_queue is very slow if -D_GLIBCXX_DEBUG is used

[pluto at agmk dot net]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53263

--- Comment #5 from Pawel Sikora <pluto at agmk dot net> 2012-05-07 13:34:43 UTC ---
callgrind shows that n*10e3 of pq.push() generates m*10e6 (m>n)
_M_can_advance() calls and growing fast :)

[Bug libstdc++/53263] priority_queue is very slow if -D_GLIBCXX_DEBUG is used

[fdumont at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53263

--- Comment #6 from François Dumont <fdumont at gcc dot gnu.org> 2012-05-07 20:37:57 UTC ---
  I see 2 possible modifications for this problem.

  The first one would be to avoid the numerous calls to _M_can_advance. In
priority_queue each time an element is pushed there is a call to push_heap
which, in debug mode, call __is_heap on the debug vector so on debug iterator
thus the numerous calls to _M_can_advance. To avoid this issue you can try to
change definition of debug macro in include/debug/macros.h from:

#define __glibcxx_check_heap(_First,_Last)                \
_GLIBCXX_DEBUG_VERIFY(std::__is_heap(_First, _Last),                \
              _M_message(__gnu_debug::__msg_not_heap)            \
              ._M_iterator(_First, #_First)            \
              ._M_iterator(_Last, #_Last))

to

#define __glibcxx_check_heap(_First,_Last)                \
_GLIBCXX_DEBUG_VERIFY(std::__is_heap(__gnu_debug::__base(_First),
__gnu_debug::__base(_Last)),                \
              _M_message(__gnu_debug::__msg_not_heap)            \
              ._M_iterator(_First, #_First)            \
              ._M_iterator(_Last, #_Last))

  This is going to remove the debug layer around the vector iterators which is
useless when call __is_heap because we already know that the iterator range is
correct, it has been checked before.

  The second one would be more radical: remove all debug checks from
priority_queue implementation because the priority_queue completely control the
underlying sequence content and from one push to the other there is no chance
that the underlying sequence do not represent a heap anymore. But this means
that debug algos are correctly segregated from normal algos which is something
I have started to work on but not yet completed.

  In fact the heap could be broken if a contained instance is changed in a bad
way but I don't think debug checks in push_heap are there for this kind of bad
coding practice which is very hard to detect when you want to keep good
performance.

[Bug libstdc++/53263] priority_queue is very slow if -D_GLIBCXX_DEBUG is used

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53263

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |paolo.carlini at oracle dot
                   |                            |com

--- Comment #7 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-05-07 21:10:08 UTC ---
Good, good, thanks Francois, anybody willing to benchmark the more limited
change?

[Bug libstdc++/53263] priority_queue is very slow if -D_GLIBCXX_DEBUG is used

[pluto at agmk dot net]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53263

--- Comment #8 from Pawel Sikora <pluto at agmk dot net> 2012-05-08 07:54:18 UTC ---
(In reply to comment #7)
> Good, good, thanks Francois, anybody willing to benchmark the more limited
> change?

changing __glibcxx_check_heap_*pred* reduces timings for me from
~3.25 sec to 0.18sec (for 10000 items in pqueue).

tested on on intel core-i3-540 with:
x86_64-gnu-linux-g++ pq.C -o pq -g2 -static -D_GLIBCXX_DEBUG -O2

[Bug libstdc++/53263] priority_queue is very slow if -D_GLIBCXX_DEBUG is used

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53263

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|paolo.carlini at oracle dot |
                   |com                         |

--- Comment #9 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-05-08 09:40:23 UTC ---
Thanks Pawel. Thus, Francois, I would suggest testing and, if everything goes
well, checking-in the small change to mainline and 4.7.x, thus consider the
issue resolved in terms of localized performance improvement. Further
enhancements will be automatically part of the long term changes Francois is
working on.

[Bug libstdc++/53263] priority_queue is very slow if -D_GLIBCXX_DEBUG is used

[fdumont at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53263

--- Comment #10 from François Dumont <fdumont at gcc dot gnu.org> 2012-05-08 19:31:49 UTC ---
Ok, I will submit a patch tomorrow generalizing usage of __gnu_debug::__base in
debug macros.

[Bug libstdc++/53263] priority_queue is very slow if -D_GLIBCXX_DEBUG is used

[fdumont at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53263

--- Comment #11 from François Dumont <fdumont at gcc dot gnu.org> 2012-05-11 19:21:38 UTC ---
Author: fdumont
Date: Fri May 11 19:21:31 2012
New Revision: 187414

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=187414
Log:
2012-05-11  François Dumont  <fdumont@gcc.gnu.org>

    PR libstdc++/53263
    * include/debug/safe_iterator.h (__gnu_debug::__base): Move...
    * include/debug/functions.h: ... Here. Add debug function
    overloads to perform checks on normal iterators when possible.
    * include/debug/macros.h (__glibcxx_check_heap)
    (__glibcxx_check_heap_pred): Use __gnu_debug::__base on iterator range.

Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/debug/functions.h
    trunk/libstdc++-v3/include/debug/macros.h
    trunk/libstdc++-v3/include/debug/safe_iterator.h

[Bug libstdc++/53263] priority_queue is very slow if -D_GLIBCXX_DEBUG is used

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53263

--- Comment #12 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-05-12 21:41:15 UTC ---
Francois, please double check that now you are ok, thanks.

[Bug libstdc++/53263] priority_queue is very slow if -D_GLIBCXX_DEBUG is used

[fdumont at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53263

François Dumont <fdumont at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED

--- Comment #13 from François Dumont <fdumont at gcc dot gnu.org> 2012-05-14 19:49:52 UTC ---
Avoiding the numerous debug checks when checking that ranges are heap seems to
have resolve this issue. Fully removing useless debug checks in priority_queue
will come later.

[Bug libstdc++/53263] priority_queue is very slow if -D_GLIBCXX_DEBUG is used

[dominik.strasser@onespin-solutions.com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53263

--- Comment #14 from dominik.strasser@onespin-solutions.com 2012-06-11 15:05:43 UTC ---
Is there a chance to get this into 4.7.1 ?

[Bug libstdc++/53263] priority_queue is very slow if -D_GLIBCXX_DEBUG is used

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53263

--- Comment #15 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-06-11 15:27:17 UTC ---
Too late for 4.7.1. Francois, can you please apply the patch to 4_7-branch as
soon as 4.7.1 is out, thus for 4.7.2? Thanks!

[Bug libstdc++/53263] priority_queue is very slow if -D_GLIBCXX_DEBUG is used

[dominik.strasser@onespin-solutions.com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53263

--- Comment #17 from dominik.strasser@onespin-solutions.com ---
Created attachment 30350
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30350&action=edit
New testcase

[Bug libstdc++/53263] priority_queue is very slow if -D_GLIBCXX_DEBUG is used

[dominik.strasser@onespin-solutions.com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53263

dominik.strasser@onespin-solutions.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #27332|0                           |1
        is obsolete|                            |
  Attachment #30350|0                           |1
        is obsolete|                            |

--- Comment #18 from dominik.strasser@onespin-solutions.com ---
Created attachment 30351
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30351&action=edit
Really new testcase

[Bug libstdc++/53263] priority_queue is very slow if -D_GLIBCXX_DEBUG is used

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53263

--- Comment #19 from Paolo Carlini <paolo.carlini at oracle dot com> ---
I'm not going to work on this anyway, but really I'm not at all sure that
debug-mode is by design made for "bigger configurations", thus makes sense to
give high priority to this kind of issue. Unless of course users actively
contribute improvements.

[Bug libstdc++/53263] priority_queue is very slow if -D_GLIBCXX_DEBUG is used

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53263

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|---                         |FIXED

--- Comment #20 from Paolo Carlini <paolo.carlini at oracle dot com> ---
And we already analyzed the issue and figured out that further improvements
aren't part of it (See Comment 6 and 9).

[Bug libstdc++/53263] priority_queue is very slow if -D_GLIBCXX_DEBUG is used

[dominik.strasser@onespin-solutions.com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53263

--- Comment #21 from dominik.strasser@onespin-solutions.com ---
How can I help ?
My goal is to run our entire regression test suite with STL debugging switched
on as this is great for quality assurance. Having fought several problems, this
now seems to be my final obstacle. After one year I now have a fix in a GCC
release but unfortunately still no cigar.

If you point me to sth. where I can look at I will happily try to contribute.

[Bug libstdc++/53263] priority_queue is very slow if -D_GLIBCXX_DEBUG is used

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53263

--- Comment #22 from Paolo Carlini <paolo.carlini at oracle dot com> ---
Get in touch with Francois and work on further improvements with him.

[Bug libstdc++/53263] priority_queue is very slow if -D_GLIBCXX_DEBUG is used

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53263

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Version|4.8.1                       |4.7.0
   Target Milestone|---                         |4.8.0

--- Comment #23 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Domink, why did you change the version of this bug on 2013-06-24 (and reopen
it)?

It was reported against 4.7.0, before 4.8.0 was even released, so cannot be a
bug in 4.8.1, right?

I'm restoring the version to 4.7.0 and setting target to 4.8.0 since that's
where the fix appeared.