[Bug libstdc++/36338] New: heap_sort effectively hangs with -D_GLIBCXX_DEBUG

["chris at bubblescope dot net" <gcc-bugzilla at gcc dot gnu dot org>]

heap_sort is unusably slow in debug mode, and 'effectively hangs' for large
instances. This also in rare cases (and this is how I came across it) effects
std::sort, which calls make_heap / heap_sort when it's quicksort partitioning
is doing badly.

Consider sorting a vectors of zeroes in 4 ways:

1) std::sort
2) std::sort, -D_GLIBCXX_DEBUG
3) std::heap_sort
4) std::heap_sort, -D_GLIBCXX_DEBUG

1,000 elements: 0.004s, 0.014s, 0.004s, 1.3s
2,000 elements: 0.003s, 0.033s, 0.006s, 4.7s
5,000 elements: 0.005s, 0.096s, 0.008s, 32.7s
10,000 elements: 0.006s, 0.166s, 0.013s, 104s

We can see we've effectively changed an 'O(n log n)' algorithm into an 'O(n^2
log n)' algorithm.

Note, this problem is not fixed by filling the array with different numbers. 

Looking at pop_heap, it is just a thin wrapper over __pop_heap, along with this
check. Therefore I believe the easiest fix will be to make sort_heap call
__pop_heap directly, which avoids the check.

I tested this with the following program:

#include <algorithm>
#include <vector>

using namespace std;

int main(void)
{
  vector<int> a(5000, 0);
#ifdef HEAP
  make_heap(a.begin(), a.end());
  sort_heap(a.begin(), a.end());
#else
  sort(a.begin(), a.end());
#endif
}


-- 
           Summary: heap_sort effectively hangs with -D_GLIBCXX_DEBUG
           Product: gcc
           Version: 4.2.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: chris at bubblescope dot net


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