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

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

[chris at bubblescope dot net]

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

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

[paolo dot carlini at oracle dot com]

------- Comment #1 from paolo dot carlini at oracle dot com  2008-05-27 09:10 -------
(In reply to comment #0)

> 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.

Indeed, makes sense. Will do, thanks for the suggestion.


-- 

paolo dot carlini at oracle dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |paolo dot carlini at oracle
                   |dot org                     |dot com
             Status|UNCONFIRMED                 |ASSIGNED
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2008-05-27 09:10:18
               date|                            |


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

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

[paolo at gcc dot gnu dot org]

------- Comment #2 from paolo at gcc dot gnu dot org  2008-05-31 23:01 -------
Subject: Bug 36338

Author: paolo
Date: Sat May 31 23:01:09 2008
New Revision: 136242

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=136242
Log:
2008-05-31  Paolo Carlini  <paolo.carlini@oracle.com>
            Chris Jefferson  <chris@bubblescope.net>

        PR libstdc++/36338
        * include/bits/stl_heap.h (sort_heap): Use __pop_heap directly.
        (pop_heap): Slightly tweak.

Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/stl_heap.h


-- 


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

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

[paolo dot carlini at oracle dot com]

------- Comment #3 from paolo dot carlini at oracle dot com  2008-05-31 23:02 -------
Fixed for 4.4.0.


-- 

paolo dot carlini at oracle dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.4.0


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