Limit std::sort comparisons on small list

[Christopher Jefferson]

I'm unconvinced by this optimisation. I have already heard the
occasional complaint that libstdc++ is quite large, so even in this
tiny case I would be unsure about producing a very small code size
increase for a very small performance improvement.

On 4 October 2013 21:44, François Dumont <frs.dumont@gmail.com> wrote:
> On 10/03/2013 10:59 PM, Paolo Carlini wrote:
>>
>> .. or, if I remember correctly, should we maybe see what happens for a
>> smaller or much smaller number of elements to see if there is a measurable
>> (in number of comparisons terms), on sort?
>>
>> Thanks,
>> Paolo.
>>
> I run the sort performance test using only 11 elements and in this case I
> see:
>
> Without patch:
> sort.cc                      reverse 10 comparisons          0r 0u    0s
> 0mem    0pf
> sort.cc                      forwards 20 comparisons         0r 0u    0s
> 0mem    0pf
> sort.cc                      random 30 comparisons           0r 0u    0s
> 0mem    0pf
>
> With patch:
> sort.cc                      reverse 10 comparisons          0r 0u    0s
> 0mem    0pf
> sort.cc                      forwards 19 comparisons         0r 0u    0s
> 0mem    0pf
> sort.cc                      random 29 comparisons           0r 0u    0s
> 0mem    0pf
>
> so with a limited number of elements we can see the gain even if it looks
> like for the sort algo it is limited to 1 comparison. For stable_sort it is
> better.
>
> François
>