[Bug libstdc++/65609] New: std::sort is suboptimal

[jdcoxm3 at hotmail dot com]

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

Bug ID: 65609
   Summary: std::sort is suboptimal
   Product: gcc
   Version: 4.4.7
Status: UNCONFIRMED
  Severity: normal
  Priority: P3
 Component: libstdc++
  Assignee: unassigned at gcc dot gnu.org
  Reporter: jdcoxm3 at hotmail dot com

std::sort will call the compare function with the same object which can cause
severe performance problems.  This shows up in parallel_sort (both Intel's TBB
and __gnu_parallel's version) and on multiple OS's (Mac OS, CentOS) and
multiple versions of the compiler. qsort doesn't exhibit this behavior.

g++ (GCC) 4.4.7 20120313 (Red Hat 4.4.7-11)

In the following example, as the length of string s gets larger and larger the
number of times s1 == s2 in the compare function increases rapidly.  Since the
two pointers are equal, it leads to having compare nearly the entire string
(even though they are equal).


#include 
#include 
#include 
#include 
#include 

bool comp(char const *s1, char const *s2)
   {
   if (s1 == s2)
  std::cout << "This is a bug, s1 should not equal s2" < v;
   for (uint32_t x = 0; x < s.size(); ++x)
  v.push_back(s.data() + x);
   std::sort(v.begin(), v.end(), comp);

   return 0;
   }

[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)%10 == 0 ) std::cerr << cmpcount << std::endl;
return strcmp(a,b) == -1;
  }
};

[Bug libstdc++/65609] std::sort is suboptimal

[jdcoxm3 at hotmail dot com]

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

--- Comment #2 from jdcoxm3 at hotmail dot com ---
Thanks for looking into this so quickly.  My mac, running latest os (10.10.2)
and xcode (6.2) also has the problem but looking deeper, it's based on version
4.2.1. I thought it would have been a much later version.