public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug libstdc++/36338] New: heap_sort effectively hangs with -D_GLIBCXX_DEBUG
@ 2008-05-27 7:36 chris at bubblescope dot net
2008-05-27 9:11 ` [Bug libstdc++/36338] " paolo dot carlini at oracle dot com
` (2 more replies)
0 siblings, 3 replies; 4+ messages in thread
From: chris at bubblescope dot net @ 2008-05-27 7:36 UTC (permalink / raw)
To: gcc-bugs
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
^ permalink raw reply [flat|nested] 4+ messages in thread
* [Bug libstdc++/36338] heap_sort effectively hangs with -D_GLIBCXX_DEBUG
2008-05-27 7:36 [Bug libstdc++/36338] New: heap_sort effectively hangs with -D_GLIBCXX_DEBUG chris at bubblescope dot net
@ 2008-05-27 9:11 ` paolo dot carlini at oracle dot com
2008-05-31 23:02 ` paolo at gcc dot gnu dot org
2008-05-31 23:03 ` paolo dot carlini at oracle dot com
2 siblings, 0 replies; 4+ messages in thread
From: paolo dot carlini at oracle dot com @ 2008-05-27 9:11 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 4+ messages in thread
* [Bug libstdc++/36338] heap_sort effectively hangs with -D_GLIBCXX_DEBUG
2008-05-27 7:36 [Bug libstdc++/36338] New: heap_sort effectively hangs with -D_GLIBCXX_DEBUG chris at bubblescope dot net
2008-05-27 9:11 ` [Bug libstdc++/36338] " paolo dot carlini at oracle dot com
@ 2008-05-31 23:02 ` paolo at gcc dot gnu dot org
2008-05-31 23:03 ` paolo dot carlini at oracle dot com
2 siblings, 0 replies; 4+ messages in thread
From: paolo at gcc dot gnu dot org @ 2008-05-31 23:02 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 4+ messages in thread
* [Bug libstdc++/36338] heap_sort effectively hangs with -D_GLIBCXX_DEBUG
2008-05-27 7:36 [Bug libstdc++/36338] New: heap_sort effectively hangs with -D_GLIBCXX_DEBUG chris at bubblescope dot net
2008-05-27 9:11 ` [Bug libstdc++/36338] " paolo dot carlini at oracle dot com
2008-05-31 23:02 ` paolo at gcc dot gnu dot org
@ 2008-05-31 23:03 ` paolo dot carlini at oracle dot com
2 siblings, 0 replies; 4+ messages in thread
From: paolo dot carlini at oracle dot com @ 2008-05-31 23:03 UTC (permalink / raw)
To: gcc-bugs
------- 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
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2008-05-31 23:03 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2008-05-27 7:36 [Bug libstdc++/36338] New: heap_sort effectively hangs with -D_GLIBCXX_DEBUG chris at bubblescope dot net
2008-05-27 9:11 ` [Bug libstdc++/36338] " paolo dot carlini at oracle dot com
2008-05-31 23:02 ` paolo at gcc dot gnu dot org
2008-05-31 23:03 ` paolo dot carlini at oracle dot com
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).