[Bug libstdc++/14061] New: poor performance of std::sort on large lexicographic c-string sort

[Bug libstdc++/14061] New: poor performance of std::sort on large lexicographic c-string sort

[ctsa at u dot washington dot edu]

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

[Bug libstdc++/14061] poor performance of std::sort on large lexicographic c-string sort

[pinskia at gcc dot gnu dot org]

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

[Bug libstdc++/14061] poor performance of std::sort on large lexicographic c-string sort

[pcarlini at suse dot de]

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

[Bug libstdc++/14061] poor performance of std::sort on large lexicographic c-string sort

[ctsa at u dot washington dot edu]

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

[Bug libstdc++/14061] poor performance of std::sort on large lexicographic c-string sort

[jdcoxm3 at hotmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=14061

jdcoxm3 at hotmail dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jdcoxm3 at hotmail dot com

--- Comment #4 from jdcoxm3 at hotmail dot com ---
I ran into nearly the same issue and submitted a bug on this.  Add a check to
you compare function as a work around.

struct functor_cmp {
  bool operator()(const char* a, const char* b){
    if (a == b) return false;
    if( (++cmpcount)%100000 == 0 ) std::cerr << cmpcount << std::endl;
    return strcmp(a,b) == -1;
  }
};