Re: [PATCH v2] stdlib: Reinstate stable mergesort implementation on qsort

[Adhemerval Zanella Netto <adhemerval.zanella@linaro.org>]

On 12/01/24 08:21, Florian Weimer wrote:
> * Adhemerval Zanella:
> 
>> diff --git a/manual/search.texi b/manual/search.texi
>> index a550858478..5691bf2f2b 100644
>> --- a/manual/search.texi
> 
>> @@ -199,8 +199,9 @@ Functions}):
>>  The @code{qsort} function derives its name from the fact that it was
>>  originally implemented using the ``quick sort'' algorithm.
>>  
>> +The implementation of @code{qsort} in this library might not be an
>> +in-place sort and might thereby use an extra amount of memory to store
>> +the array.
>>  @end deftypefun
> 
> I'd appreciate if a native speaker could have look at this.

I will update with Alexander's suggestion.

> 
>> +typedef uint32_t __attribute__ ((__may_alias__)) u32_alias_t;
>> +typedef uint64_t __attribute__ ((__may_alias__)) u64_alias_t;
> 
> What's the code generation impact of may_alias here?

I did not see any code difference on x86_64 and aarch64 [1], the alias
s used mainly to avoid possible undefined behaviour (similar to what 
we do on string-optype.h for the generic string routines).

> 
>> +    case SWAP_VOID_ARG:
>> +      while (n1 > 0 && n2 > 0)
>> +	{
>> +	  if ((*cmp) (*(const void **) b1, *(const void **) b2, arg) <= 0)
>> +	    {
>> +	      *(void **) tmp = *(void **) b1;
>> +	      b1 += sizeof (void *);
>> +	      --n1;
>> +	    }
>> +	  else
>> +	    {
>> +	      *(void **) tmp = *(void **) b2;
>> +	      b2 += sizeof (void *);
>> +	      --n2;
>> +	    }
>> +	  tmp += sizeof (void *);
>> +	}
>> +    default:
>> +      while (n1 > 0 && n2 > 0)
> 
> Missing break before “default:”.

Ack.

> 
>>  void
>>  __qsort_r (void *const pbase, size_t total_elems, size_t size,
>>  	   __compar_d_fn_t cmp, void *arg)
>>  {
>>    if (total_elems <= 1)
>>      return;
>>  
>> +  char tmp[QSORT_STACK_SIZE];
>> +  size_t total_size = total_elems * size;
>> +  char *buf;
> 
> You need to ensure alignment now that you aren't using alloca anymore, I
> think.

Indeed, I will update to follow alloca alignment.

> 
> Rest looks okay.
> 
> Thanks,
> Florian
> 

[1] https://godbolt.org/z/nEf34WhrM