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