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

["fdumont at gcc dot gnu.org" <gcc-bugzilla at gcc dot gnu dot 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.