Re: Patch: Improve std::sort performance (particularly on reverse-ordered lists)

[Christopher Jefferson <chris at bubblescope dot net>]

On 25 September 2013 14:03, Marc Glisse <marc.glisse@inria.fr> wrote:
> On Wed, 25 Sep 2013, Christopher Jefferson wrote:
>
>> There are a selection of ways of fixing this. This patch switches the
>> median calculation from considering then first, mid, last locations to
>> on first+1, mid, last-1 (there is no reason in this bug to consider
>> last-1 instead of last, but I thought it wouldn't do any harm, and
>> might avoid other issues of accidentally choosing a bad pivot.
>
>
> It's going to conflict with Francois' patch, don't know which one of you
> will be first ;-)

My hope (and it looks like this will be the case) is that mine will
land first, and be applied to previous versions. Then we can look at
improving sort going forwards.
>
> I think the median function could be slightly shorter (but slower?) with
> something like:
>
> if(*a<*b) std::swap(a,b);
> proceed as if we were in the else branch.

True, not sure how much the benefit would be. Similar changes could
have been made in C++03 or back to the original SGI codebase (which
means, I'm not making them right now, let's get my nasty mistake fixed
first!)

In general, might be nice to "spruce up" some of the code. However,
benchmarking such things is a pain (as shown by the recent search_n,
where there were two patches and which was faster varied between
different computers).

Chris