This is the mail archive of the
gcc-bugs@gcc.gnu.org
mailing list for the GCC project.
[Bug libstdc++/14061] poor performance of std::sort on large lexicographic c-string sort
- From: "pinskia at gcc dot gnu dot org" <gcc-bugzilla at gcc dot gnu dot org>
- To: gcc-bugs at gcc dot gnu dot org
- Date: 7 Feb 2004 08:37:19 -0000
- Subject: [Bug libstdc++/14061] poor performance of std::sort on large lexicographic c-string sort
- References: <20040207080740.14061.ctsa@u.washington.edu>
- Reply-to: gcc-bugzilla at gcc dot gnu dot org
------- Additional Comments From pinskia at gcc dot gnu dot org 2004-02-07 08:37 -------
I know that this is a performance bug but note the C++ standard says this:
Complexity: Approximately N log N (where N ==last-first) comparisons on the "average".
If the worst case behavior is important stable_sort()(25.3.1.2) or partial_sort()(25.3.1.3) should be used.
And note that stable_sort is faster than both quick_sort and std::sort in your case which you give.
Also note that the only complexity is needed to O(N log N) compares on average and so this is not
comforming issue.
Confirmed that std::sort is much slower than quick_sort and std::stable_sort in the case you gave, note
it might be faster in other cases though.
--
What |Removed |Added
----------------------------------------------------------------------------
Severity|normal |enhancement
Status|UNCONFIRMED |NEW
Ever Confirmed| |1
Known to fail| |tree-ssa
Last reconfirmed|0000-00-00 00:00:00 |2004-02-07 08:37:18
date| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14061