Limit std::sort comparisons on small list

[David Kastrup]

François Dumont <frs.dumont@gmail.com> writes:

> On 10/07/2013 02:56 PM, Christopher Jefferson wrote:
>> 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:
>>> 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
>>>
>
> I am surprised, code bloat is indeed the only drawback of this patch,
> but isn't sometimes the compiler unrolling loop itself ? You can even
> see in __find_if implementation that we sometimes unroll loops
> manually so I guess that in general it is rather good for
> performance. Especially in this case with the first iteration that is
> better taken care separately.
>
> Of course it is a small optimization but also a rather trivial one. I
> am sorry that I can't check the result on the generated code but I am
> quite sure that the "code bloat" will be even smaller than the
> optimization.

The important cases are the large ones.  Rolling out of cache because of
exceptions can really make a difference.  If your times are O(n lg n),
and you make special exceptions to speed up n operations, then it's easy
to get a hit on n ((lg n) -1) operations.

-- 
David Kastrup