This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: Patch: Improve std::sort performance (particularly on reverse-ordered lists)
- From: David Kastrup <dak at gnu dot org>
- To: libstdc++ at gcc dot gnu dot org
- Date: Wed, 25 Sep 2013 16:32:52 +0200
- Subject: Re: Patch: Improve std::sort performance (particularly on reverse-ordered lists)
- Authentication-results: sourceware.org; auth=none
- References: <CA+jCFLswT89EOhkngQzpTFhBYtE-tzZRh_ZzCYho-1j17UXOdQ at mail dot gmail dot com>
Christopher Jefferson <chris@bubblescope.net> writes:
> This is just posting a patch from bugzilla, so it gets a wider
> audience. The patch seems to be performing well.
Apropos the headline "particularly on reverse-ordered lists": while it
is probably not really talking about _lists_, it's worth mentioning that
I posted rather well-performing (stable, close to minimum comparisons,
memory locality pretty good for lists, considerably better performance
than current list sort, no degenerate worst case behavior) list-sorting
code to this list several months ago, answered a few questions and never
got any conclusive followups or suggestions apart from an acknowledgment
that my numbers seemed correct.
So while it would appear from your discussion of quicksort that you are
more concerned with arrays rather than lists (correct me if I'm wrong),
it might be worth a look anyway.
Here's the original mail in the archive
<URL:http://gcc.gnu.org/ml/libstdc++/2013-07/msg00010.html>.
--
David Kastrup