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

[Adhemerval Zanella]

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.

> 2) If you're going to just test which swap function to use, why bother initializing
> swap_func? Why not just use an int?

Indeed this is no much gain on glibc usage.  The kernel provides a API to use
used-defined swap_func, which is not our case.