[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 <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <stdint.h>

bool comp(char const *s1, char const *s2)
   {
   if (s1 == s2)
      std::cout << "This is a bug, s1 should not equal s2" <<std::endl;
   return strcmp(s1,s2) < 0;
   }

int main(int argc, char **argv)
   {
   std::string s = "AABAABAABAABAABABAAABAABBBAAA";
   std::vector<char const *> 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;
   }