Re: [PATCH 6/7] stdlib: Optimization qsort{_r} swap implementation

[Adhemerval Zanella <adhemerval dot zanella at linaro dot org>]

On 23/01/2018 21:37, Paul Eggert wrote:
> On 01/23/2018 10:28 AM, Adhemerval Zanella wrote:
> 
>> Again do we really to over-engineering it? GCC profile usage shows 95% to total
>> issues done with up to 9 elements and 92% of key size 8.  Firefox is somewhat
>> more diverse with 72% up to 17 elements and 95% of key size 8.
> 
> You have a point. I assume these were on machines with 64-bit pointers. In that case why bother with a size-4 special case? Special-casing pointer-size items should suffice.

Yes, I just tested on x86_64 and I added the size-4 mainly because is quite simple
in terms of code complexity and resulting code size.

> 
>> I would rather add specialized sort implementation such as BSD family, heapsort
>> and mergesort, to provide different algorithm for different constraints (mergesort
>> for stable-sort, heapsort/mergesort to avoid worse-case from quicksort). We might
>> even extend it to add something like introsort.
> 
> Each of us over-engineers in his own way (:-).
> 

I do think your points are fair, most usage of qsort is already hitting the quicksort
implementation (due the total size of array) and for these cases they will do see
a small speed up due swap optimization and the undefined behaviour fix for qsort_r.

I think if speed is the focus, there is some other idea to optimize for it like
BZ#17941.