[v5,1/6] stdlib: Optimization qsort{_r} swap implementation

It optimizes take in consideration both the most common elements are
either 32 or 64 bit in size and inputs are aligned to the word
boundary.  This is similar to the optimization done on lib/sort.c
from Linux.

This patchs adds an optimized swap operation on qsort based in previous
msort one.  Instead of byte operation, three variants are provided:

  1. Using uint32_t loads and stores.
  2. Using uint64_t loads and stores.
  3. Generic one with a temporary buffer and memcpy/mempcpy.

The 1. and 2. options are selected only if base pointer is aligned
to required type.

Checked on x86_64-linux-gnu.
---
 stdlib/qsort.c | 109 +++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 91 insertions(+), 18 deletions(-)

On 2023-07-13 06:25, Adhemerval Zanella via Libc-alpha wrote:

> +is_aligned (const void *base, size_t size, unsigned char align)

ALIGN should be of type size_t, not unsigned char. Although this 
shouldn't change the machine code it's better documentation and more 
robust to future changes.


> +  if (is_aligned (pbase, size, 8))

Change "8" to "alignof (uint64_t)".

> +    swap_type = SWAP_WORDS_64;
> +  else if (is_aligned (pbase, size, 4))

Likewise, change "4" to "alignof (uint32_t)".

Or is the problem that alignof didn't work for you? If so, perhaps 
__alignof__. Still, alignof is used elsewhere in glibc and is in C23 so 
it's better to use here if it works.

On 2023-07-13 15:17, Paul Eggert wrote:

>> +  if (is_aligned (pbase, size, 8))
> 
> Change "8" to "alignof (uint64_t)".


Oops, scratch that. The size must be a multiple of sizeof (uint64_t) and 
the alignment must be a multiple of alignof (uint64_t). Since sizeof 
(uint64_t) must be a multiple of alignof (uint64_t) what you wrote was 
safe (but confusing), whereas what I wrote was not.

To help avoid confusion by future readers, I suggest rewriting the 
comments and parameters for is_aligned to be something like the 
following. This shouldn't change the machine code.

   /* If this function returns true, elements can be safely copied using
      word loads and stores.  Otherwise, it might not be safe.
      BASE (as an integer) must be a multiple of the word alignment.
      TOTAL_SIZE must be a multiple of WORDSIZE.
      Since WORDSIZE must be a multiple of the word alignment,
      and WORDSIZE is a power of two on all supported platforms,
      this function for speed merely checks that BASE and SIZE
      are both multiples of the word size.  */
   __attribute_const__ __always_inline static bool
   is_aligned (const void *base, size_t size, size_t wordsize)
   {
     return (((uintptr_t) base | size) & (wordsize - 1)) == 0;
   }

On 13/07/23 22:01, Paul Eggert wrote:
> On 2023-07-13 15:17, Paul Eggert wrote:
> 
>>> +  if (is_aligned (pbase, size, 8))
>>
>> Change "8" to "alignof (uint64_t)".
> 
> 
> Oops, scratch that. The size must be a multiple of sizeof (uint64_t) and the alignment must be a multiple of alignof (uint64_t). Since sizeof (uint64_t) must be a multiple of alignof (uint64_t) what you wrote was safe (but confusing), whereas what I wrote was not.
> 
> To help avoid confusion by future readers, I suggest rewriting the comments and parameters for is_aligned to be something like the following. This shouldn't change the machine code.
> 
>   /* If this function returns true, elements can be safely copied using
>      word loads and stores.  Otherwise, it might not be safe.
>      BASE (as an integer) must be a multiple of the word alignment.
>      TOTAL_SIZE must be a multiple of WORDSIZE.

I think you meant SIZE here instead of TOTAL_SIZE.

>      Since WORDSIZE must be a multiple of the word alignment,
>      and WORDSIZE is a power of two on all supported platforms,
>      this function for speed merely checks that BASE and SIZE
>      are both multiples of the word size.  */
>   __attribute_const__ __always_inline static bool
>   is_aligned (const void *base, size_t size, size_t wordsize)
>   {
>     return (((uintptr_t) base | size) & (wordsize - 1)) == 0;
>   }
> 

Alright, I changed this version.

On Thu, 13 Jul 2023, Adhemerval Zanella via Libc-alpha wrote:

> +/* Returns true if elements can be copied using word loads and stores.
> +   The SIZE and BASE must be a multiple of the ALIGN.  */
> +__attribute_const__ __always_inline static bool

Kernel folks sure love their double underscores, but plain
'static inline bool' should work just as well here.

I'd recommend to properly credit Linux lib/sort.c since obviously this
commit originated as a direct copy of the code therein, not just being
inspired by what's there.

> +is_aligned (const void *base, size_t size, unsigned char align)
> +{
> +  return (((uintptr_t) base | size) & (align - 1)) == 0;
> +}
> +
> +static void
> +swap_words_64 (void * restrict a, void * restrict b, size_t n)
> +{
> +  do
> +   {
> +     n -= 8;
> +     uint64_t t = *(uint64_t *)(a + n);
> +     *(uint64_t *)(a + n) = *(uint64_t *)(b + n);
> +     *(uint64_t *)(b + n) = t;
> +   } while (n);
> +}

The undefined behavior resulting from attempt to access via an 'uint64_t *'
something of a different type is known to cause miscompilation in practice:
https://www.spec.org/cpu2017/Docs/benchmarks/605.mcf_s.html#portability

I see that the new string routines do it properly via 

  typedef unsigned long int __attribute__ ((__may_alias__)) op_t;

Would be nice to avoid new instances of such UB here.

Alexander

On 2023-07-17 09:57, Alexander Monakov wrote:
> I'd recommend to properly credit Linux lib/sort.c since obviously this
> commit originated as a direct copy of the code therein, not just being
> inspired by what's there.

What are the licensing issues here? The Linux kernel is GPLv2 only, 
whereas glibc/stdlib/qsort.c is LGPLv2.1+, so we can't simply take 
nontrivial source code from the Linux kernel.

On 17/07/23 14:29, Paul Eggert wrote:
> On 2023-07-17 09:57, Alexander Monakov wrote:
>> I'd recommend to properly credit Linux lib/sort.c since obviously this
>> commit originated as a direct copy of the code therein, not just being
>> inspired by what's there.
> 
> What are the licensing issues here? The Linux kernel is GPLv2 only, whereas glibc/stdlib/qsort.c is LGPLv2.1+, so we can't simply take nontrivial source code from the Linux kernel.

I am not sure in fact, my take was the code as simple enough to have this
concern.  But if it were case, I can reimplement it different to avoid this
issue.

On 2023-07-17 11:07, Adhemerval Zanella Netto wrote:
> I am not sure in fact, my take was the code as simple enough to have this
> concern.

The usual rule of thumb is that ten lines are trivial, and that more 
than that might be a concern. When it's a concern, you can't simply read 
the original code and rewrite it in a different way; you need to 
actually rewrite it from scratch, preferably without looking at the 
original code. It's a pain, admittedly.

On 17/07/23 15:58, Paul Eggert wrote:
> On 2023-07-17 11:07, Adhemerval Zanella Netto wrote:
>> I am not sure in fact, my take was the code as simple enough to have this
>> concern.
> 
> The usual rule of thumb is that ten lines are trivial, and that more than that might be a concern. When it's a concern, you can't simply read the original code and rewrite it in a different way; you need to actually rewrite it from scratch, preferably without looking at the original code. It's a pain, admittedly.

Alright, I don't think it should much of trouble to reimplement a simple heapsort.

On 17/07/23 13:57, Alexander Monakov wrote:
> 
> On Thu, 13 Jul 2023, Adhemerval Zanella via Libc-alpha wrote:
> 
>> +/* Returns true if elements can be copied using word loads and stores.
>> +   The SIZE and BASE must be a multiple of the ALIGN.  */
>> +__attribute_const__ __always_inline static bool
> 
> Kernel folks sure love their double underscores, but plain
> 'static inline bool' should work just as well here.
> 
> I'd recommend to properly credit Linux lib/sort.c since obviously this
> commit originated as a direct copy of the code therein, not just being
> inspired by what's there.

In fact our msort_with_tmp uses the exact same idea, but it is somewhat
convoluted because it adds an specific optimization to 'unsigned long'
and for large values it uses a inplace mempcpy.

> 
>> +is_aligned (const void *base, size_t size, unsigned char align)
>> +{
>> +  return (((uintptr_t) base | size) & (align - 1)) == 0;
>> +}
>> +
>> +static void
>> +swap_words_64 (void * restrict a, void * restrict b, size_t n)
>> +{
>> +  do
>> +   {
>> +     n -= 8;
>> +     uint64_t t = *(uint64_t *)(a + n);
>> +     *(uint64_t *)(a + n) = *(uint64_t *)(b + n);
>> +     *(uint64_t *)(b + n) = t;
>> +   } while (n);
>> +}
> 
> The undefined behavior resulting from attempt to access via an 'uint64_t *'
> something of a different type is known to cause miscompilation in practice:
> https://www.spec.org/cpu2017/Docs/benchmarks/605.mcf_s.html#portability
> 
> I see that the new string routines do it properly via 
> 
>   typedef unsigned long int __attribute__ ((__may_alias__)) op_t;
> 
> Would be nice to avoid new instances of such UB here.

Ack.

On 18/07/23 11:01, Adhemerval Zanella Netto wrote:
> 
> 
> On 17/07/23 13:57, Alexander Monakov wrote:
>>
>> On Thu, 13 Jul 2023, Adhemerval Zanella via Libc-alpha wrote:
>>
>>> +/* Returns true if elements can be copied using word loads and stores.
>>> +   The SIZE and BASE must be a multiple of the ALIGN.  */
>>> +__attribute_const__ __always_inline static bool
>>
>> Kernel folks sure love their double underscores, but plain
>> 'static inline bool' should work just as well here.
>>
>> I'd recommend to properly credit Linux lib/sort.c since obviously this
>> commit originated as a direct copy of the code therein, not just being
>> inspired by what's there.
> 
> In fact our msort_with_tmp uses the exact same idea, but it is somewhat
> convoluted because it adds an specific optimization to 'unsigned long'
> and for large values it uses a inplace mempcpy.

And just to be clear about the the license, the optimization is really
a common technique already used in our mergesort implementation, and
Linux implementation is slight different because it takes in consideration
if the architectures support fast unaligned accesses (which glibc does not
consider anymore since a9b3b770f596c), for 64 bit it also handles 64 and 32
bits with differently (which I don't think we should not bother,
compiler will know better how to optimize it); and it does not have
the large buffer optimization.  So I don't think this falls to the idea
this code is copy/pasted.

For the heapsort, I really used Linux implementation which I replaced with
textbook one.