[PATCH v3 0/7] Use introsort for qsort

[Carlos O'Donell]

On 9/3/21 3:18 PM, Paul Eggert wrote:
> On 9/3/21 10:11 AM, Adhemerval Zanella wrote:
> 
>> The performance difference with the provided benchmark clearly show
>> the tradeoff of using a instrosort over a mergesort.
> 
> Zhang, Meng and Liang <https://arxiv.org/pdf/1609.04471> report that
> introsort is particularly bad with reverse-sorted input; that case
> should be added to the benchmarks.

It should, and it would be useful, however, I think that Adhemerval's
changes to make qsort AS-safe are actually relevant and important.

All existing ruby implementations I can see use qsort in an
AS-safe-requiring context (process.c) and this would help those scenarios.

In general I think glibc should provide a qsort that is:

- Safe.

- Does not have quadratic performance behaviour.

If we want better performance we need to:

- Add new APIs mirroring what BSD is doing.

- New APIs explicitly call out the *type* of sort algorithm.

- Encourage developers and application authors to contribute those
  new implementations and use them in their applications.

There is never going to be a qsort that meets all of the workload demands
and so we should aim for a good implementation that is as safe as we
can make it (limit memory usage, avoid malloc, avoid quadratic performance
behaviour).

> The proposed change would appear to hurt performance significantly in
> the common case of sorting pointers. My guess is that typical glibc
> users would prefer speed to hardening against rare signal-handling or
> low-memory cases, since portable code will have to assume that qsort
> isn't hardened anyway.

I disagree. I think users do not expect qsort to be high performance,
they expect it to be OK performance, OK memory usage, and lastly safe.

My experience with core python developers has been that they expect
glibc to provide functions that are safe in as many contexts as possible
in order to have them avoid rolling their own for the implementation
of the language runtime.

Application developers may not care about this AS-safety, but they also
have the flexiblity to bring in additional dependencies. We can satisfy
those requirements by adding more algorithms under new symbols.

> If hardening is a goal, perhaps we should consider an alternate API
> instead of changing qsort's implementation. If we do that, we can
> improve the API as well as changing the function's name. The new API
> could promise to not call malloc, or more generally to be
> async-signal-safe if the comparison function is. The comparison
> function could take a third void* argument so it can in effect be a
> closure (this is qsort's greatest failing), the sorting function
> could take a flag argument for options, and it could return an error
> indication (in case it detects a comparison function gone haywire,
> say). That sort of thing.

I'd argue the opposite. Make the current functions safe. Add new high
performance versions with explicit algorithms and explicit tradeoffs.

>> The improvements over sizes larger than 8 is mostly due the
>> optimization done on swap operations.
> 
> A similar optimization could be done to the existing code
> independently, no? I expect that an apples-to-apples performance
> comparison would be even less favorable to the proposed change.

Size is nice, but safety is nicer IMO.

-- 
Cheers,
Carlos.