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

[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;
   }

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

[redi at gcc dot gnu.org]

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

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|---                         |FIXED
   Target Milestone|---                         |4.5.0

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
GCC 4.4.7 is no longer maintained and no later releases show the problem
anyway.

If you need this fixed please report it to the Red Hat bugzilla, but I don't
think the fix is safe to backport.

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

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

[redi at gcc dot gnu.org]

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

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
I only looked briefly but it might have been fixed by r151055