Re: git: af3c78886fd8 - main - Alter the prototype of qsort_r(3) to match POSIX, which adopted the glibc-based interface.

On 10/8/22 12:07, Alexey Dokuchaev wrote:
> On Sat, Oct 08, 2022 at 01:32:57PM +0000, Pedro Giffuni wrote:
>> Complain here:
>> https://www.austingroupbugs.net/view.php?id=900
> 
> Thanks, the first comment there more or less answers my question.

Well, it probably did not.

The FreeBSD implementation approach is mostly a template based 
implementation, so in the library qsort, qsort_r, historical qsort_r and 
qsort_s are different and independent routines, which are instantiated 
from the same template at compile time.  Therefore, there is no such 
thing of performance penalty as they suggested.

The only downside of this approach is that you get multiple copies of 
mostly identical code so the library could potentially be a little bit 
larger, this, however, is not really a big deal on modern hardware, 
because the actual size of these routines is small (~9kB).

And by paying this price, we avoided all costs associated with their 
passing of third parameter at runtime for qsort() users.  Indeed, it 
doesn't make a big difference to pass an extra register, which can well 
be reused for multiple calls, but having different comparator types is a 
clean way to do things.

In fact, if there is no need to use a third (or first) parameter for the 
comparator, there is absolutely no point of using qsort_r() because now 
the caller is passing three parameter per each comparison instead of 
two, and if the code wasn't reentrant-safe, it won't be automatically 
become reentrant-safe by using qsort_r().

Now they say, it's making it easier to implement qsort(3) by using 
qsort_r(3).  It might be if they don't make use of macros, but by doing 
so it would require casting a function pointer to another with different 
parameter type.  Now this work _today_, but it's explicitly defined as 
UB in C standard, let's quote N1548, §6.3.2.3:

     A pointer to a function of one type may be converted to a
     pointer to a function of another type and back again; the
     result shall compare equal to the original pointer. If a
     converted pointer is used to call a function whose type is
     not compatible with the referenced type, the behavior is
     undefined.

So they are basically suggesting that:

a) passing an unused parameter via register has almost no cost.

Yes this is mostly true, the compiler would save and restore the 
register if it's ever touched in the function anyway, and for caller the 
contents of the register can be reused during the iteration.

b) it is Okay to rely on UB in the C library

Well, they want to do this, good luck with that.  Not in my backyard.

By doing it their way, the cost would be:

a) qsort(3) callers are penalized for all cost related to their 
qsort_r(3).  It would be very small, but non-zero.

b) Our historical qsort_r(3) API uses first parameter to accept the 
"context", which is a widely used calling convention in other languages. 
  In fact, this is exactly why our qsort_b(3) is implemented as a 
wrapper around qsort_r(3) (now as a wrapper of the historical interface).

The motivation of adopting their API is not because it's superior, but 
because it has been used by many applications already and is now 
standardized.

Cheers,