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

["ctsa at u dot washington dot edu" <gcc-bugzilla@gcc.gnu.org>]

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