[PATCH v3 3/7] stdlib: Optimization qsort{_r} swap implementation (BZ #19305)

[Adhemerval Zanella]

On 15/10/2021 13:45, Noah Goldstein wrote:
> On Fri, Oct 15, 2021 at 8:12 AM Adhemerval Zanella
> <adhemerval.zanella@linaro.org> wrote:
>>
>>
>>
>> On 13/10/2021 00:29, Noah Goldstein wrote:
>>>     +static void
>>>     +swap_bytes (void * restrict a, void * restrict b, size_t n)
>>>     +{
>>>     +  /* Use multiple small memcpys with constant size to enable inlining
>>>     +     on most targets.  */
>>>     +  enum { SWAP_GENERIC_SIZE = 32 };
>>>     +  unsigned char tmp[SWAP_GENERIC_SIZE];
>>>     +  while (n > SWAP_GENERIC_SIZE)
>>>     +    {
>>>     +      memcpy (tmp, a, SWAP_GENERIC_SIZE);
>>>     +      a = memcpy (a, b, SWAP_GENERIC_SIZE) + SWAP_GENERIC_SIZE;
>>>     +      b = memcpy (b, tmp, SWAP_GENERIC_SIZE) + SWAP_GENERIC_SIZE;
>>>     +      n -= SWAP_GENERIC_SIZE;
>>>     +    }
>>>     +  memcpy (tmp, a, n);
>>>     +  memcpy (a, b, n);
>>>     +  memcpy (b, tmp, n);
>>>     +}
>>>     +
>>>     +/* Replace the indirect call with a serie of if statements.  It should help
>>>     +   the branch predictor.  */
>>>
>>>
>>> 1) Really? On Intel at least an indirect call that is always going to the same place
>>> is certainly going to be predicted as well if not better than 2/3 branches + direct call.
>>>
>>
>> I shamelessly copy the same strategy Linux kernel used on its lib/sort.c
>> (8fb583c4258d08f0).  Maybe Linux internal usage of its qsort() leads to
>> better predictable branch, and for this change I would prefer to work
>> better on different architectures than assume an specific one.
> 
> If it's running in the Kernel spectre mitigations can make indirect jumps
> particularly expensive. I don't think we have the same issue targeting
> userland.

Indeed I didn't take this in consideration, and it does not seems to
help much in glibc case.  I will used indirect calls.