public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug libstdc++/14061] New: poor performance of std::sort on large lexicographic c-string sort
@ 2004-02-07 8:07 ctsa at u dot washington dot edu
2004-02-07 8:37 ` [Bug libstdc++/14061] " pinskia at gcc dot gnu dot org
` (2 more replies)
0 siblings, 3 replies; 4+ messages in thread
From: ctsa at u dot washington dot edu @ 2004-02-07 8:07 UTC (permalink / raw)
To: gcc-bugs
I've encountered a performance bug for string sorting using std::sort which I
can't diagnose; this has been reduced to a minimal testcase which compares
std::sort and qsort:
sort_bug.cc
"""
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
int cmpcount = 0;
int qsort_cmp(const void* ptr1,const void* ptr2){
if( (++cmpcount)%100000 == 0 ) std::cerr << cmpcount << std::endl;
return( strcmp(*((char**) ptr1),*((char**) ptr2)));
}
struct functor_cmp {
bool operator()(const char* a, const char* b){
if( (++cmpcount)%100000 == 0 ) std::cerr << cmpcount << std::endl;
return strcmp(a,b) == -1;
}
};
int main() {
const int len = 1000000;
char* big_str = new char[len];
for(int i=0;i<len-1;++i){
big_str[i] = "ACGT"[(int) (4.*random()/(RAND_MAX+1.))];
}
big_str[len-1] = 0;
char** sub_strs = new char*[len];
for(int i=0;i<len;++i){ sub_strs[i] = big_str+i; }
// qsort runs well, std::sort reaches ~2000000 iterations and bogs down
#if 0
qsort(sub_strs,len,sizeof(char*),qsort_cmp);
#else
std::sort(sub_strs,sub_strs+len,functor_cmp());
#endif
delete [] sub_strs;
delete [] big_str;
}
"""
The performance bug shows up at all optimization levels I've tried; if the
qsort/std::sort versions are compiled without any optimization (gcc 3.4, specs
below) the two versions complete the sort in 3s/390s respectively -- nothing in
memory is being swapped to disk in either case. Compiling the same code with the
Intel 7.1 compiler (no optimizaion) yeilds almost equal sort times between the
two versions, about 3s/3s .
The platform specs:
1 Ghz Pentium III
Redhat 7.1
$ rpm -q glibc binutils
glibc-2.2.4-32
binutils-2.10.91.0.2-3
I've tested and found this bug with gcc 3.3.2 and 3.4, here's the the gcc 3.4
version I'm using:
$ g++34 -v
Reading specs from
/home/ctsa/opt/gcc-3.4-20040206/i686-linux/lib/gcc/i686-pc-linux-gnu/3.4.0/specs
Configured with: ../gcc-3.4-20040206/configure
--prefix=/home/ctsa/opt/gcc-3.4-20040206
--exec-prefix=/home/ctsa/opt/gcc-3.4-20040206/i686-linux --program-suffix=34
--disable-checking --enable-concept-checks --enable-languages=c,c++
Thread model: posix
gcc version 3.4.0 20040206 (prerelease)
--
Summary: poor performance of std::sort on large lexicographic c-
string sort
Product: gcc
Version: 3.4.0
Status: UNCONFIRMED
Severity: normal
Priority: P2
Component: libstdc++
AssignedTo: unassigned at gcc dot gnu dot org
ReportedBy: ctsa at u dot washington dot edu
CC: gcc-bugs at gcc dot gnu dot org
GCC build triplet: i686-pc-linux-gnu
GCC host triplet: i686-pc-linux-gnu
GCC target triplet: i686-pc-linux-gnu
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14061
^ permalink raw reply [flat|nested] 4+ messages in thread
* [Bug libstdc++/14061] poor performance of std::sort on large lexicographic c-string sort
2004-02-07 8:07 [Bug libstdc++/14061] New: poor performance of std::sort on large lexicographic c-string sort ctsa at u dot washington dot edu
@ 2004-02-07 8:37 ` pinskia at gcc dot gnu dot org
2004-02-07 16:03 ` pcarlini at suse dot de
2004-02-07 22:09 ` ctsa at u dot washington dot edu
2 siblings, 0 replies; 4+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2004-02-07 8:37 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From pinskia at gcc dot gnu dot org 2004-02-07 08:37 -------
I know that this is a performance bug but note the C++ standard says this:
Complexity: Approximately N log N (where N ==last-first) comparisons on the "average".
If the worst case behavior is important stable_sort()(25.3.1.2) or partial_sort()(25.3.1.3) should be used.
And note that stable_sort is faster than both quick_sort and std::sort in your case which you give.
Also note that the only complexity is needed to O(N log N) compares on average and so this is not
comforming issue.
Confirmed that std::sort is much slower than quick_sort and std::stable_sort in the case you gave, note
it might be faster in other cases though.
--
What |Removed |Added
----------------------------------------------------------------------------
Severity|normal |enhancement
Status|UNCONFIRMED |NEW
Ever Confirmed| |1
Known to fail| |tree-ssa
Last reconfirmed|0000-00-00 00:00:00 |2004-02-07 08:37:18
date| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14061
^ permalink raw reply [flat|nested] 4+ messages in thread
* [Bug libstdc++/14061] poor performance of std::sort on large lexicographic c-string sort
2004-02-07 8:07 [Bug libstdc++/14061] New: poor performance of std::sort on large lexicographic c-string sort ctsa at u dot washington dot edu
2004-02-07 8:37 ` [Bug libstdc++/14061] " pinskia at gcc dot gnu dot org
@ 2004-02-07 16:03 ` pcarlini at suse dot de
2004-02-07 22:09 ` ctsa at u dot washington dot edu
2 siblings, 0 replies; 4+ messages in thread
From: pcarlini at suse dot de @ 2004-02-07 16:03 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From pcarlini at suse dot de 2004-02-07 16:03 -------
Not a bug, Andrew is right.
--
What |Removed |Added
----------------------------------------------------------------------------
Status|NEW |RESOLVED
Resolution| |INVALID
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14061
^ permalink raw reply [flat|nested] 4+ messages in thread
* [Bug libstdc++/14061] poor performance of std::sort on large lexicographic c-string sort
2004-02-07 8:07 [Bug libstdc++/14061] New: poor performance of std::sort on large lexicographic c-string sort ctsa at u dot washington dot edu
2004-02-07 8:37 ` [Bug libstdc++/14061] " pinskia at gcc dot gnu dot org
2004-02-07 16:03 ` pcarlini at suse dot de
@ 2004-02-07 22:09 ` ctsa at u dot washington dot edu
2 siblings, 0 replies; 4+ messages in thread
From: ctsa at u dot washington dot edu @ 2004-02-07 22:09 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From ctsa at u dot washington dot edu 2004-02-07 22:09 -------
(In reply to comment #1)
Thanks Andrew! This answer was a big help. Apologies for the spurious report...
> I know that this is a performance bug but note the C++ standard says this:
> Complexity: Approximately N log N (where N ==last-first) comparisons on the
"average".
> If the worst case behavior is important stable_sort()(25.3.1.2) or
partial_sort()(25.3.1.3) should be used.
>
> And note that stable_sort is faster than both quick_sort and std::sort in your
case which you give.
> Also note that the only complexity is needed to O(N log N) compares on average
and so this is not
> comforming issue.
>
> Confirmed that std::sort is much slower than quick_sort and std::stable_sort
in the case you gave, note
> it might be faster in other cases though.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14061
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2004-02-07 22:09 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2004-02-07 8:07 [Bug libstdc++/14061] New: poor performance of std::sort on large lexicographic c-string sort ctsa at u dot washington dot edu
2004-02-07 8:37 ` [Bug libstdc++/14061] " pinskia at gcc dot gnu dot org
2004-02-07 16:03 ` pcarlini at suse dot de
2004-02-07 22:09 ` ctsa at u dot washington dot edu
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).