Re: glibc qsort() vulnerability

> On 9 Feb 2024, at 21:32, Nathan Bossart <nathandbossart(at)gmail(dot)com> wrote:
> a lot
> of current use-cases require inspecting specific fields of structs
Yes, I'm proposing to pass to sorting routine not a comparator, but value extractor. And then rely on operators <,>,==.
In a pseudocode: instead of sort(array, (a,b)->a.field-b.field) use sort(array, x->x.field). And rely on "field" being comparable.

> If that can be made simple and elegant and
> demonstrates substantial improvements
I'll try to produce a PoC and measure it with Andres' intarray test.

> On 9 Feb 2024, at 23:40, Andres Freund <andres(at)anarazel(dot)de> wrote:
>
> We have some infrastructure for that actually, see sort_template.h. But
> perhaps we should define a static inline of the generic pg_qsort() even. OTOH,
> plenty places that'll just end up to a pointless amount of code emitted to
> sort ~5 elements on average.
I think there might be another benefit. It's easier to think about values order than function comparator that returns -1,0,+1...

>> I bet “call" is more expensive than “if".
>
> Not really in this case. The call is perfectly predictable - a single qsort()
> will use the same callback for every comparison, whereas the if is perfectly
> *unpredictable*. A branch mispredict is far more expensive than a correctly
> predicted function call.

Oh, make sense... I did not understand that. But does cpu predicts what instruction to fetch even after a call instruction? These cpus are really neat things... so, probably, yes, it does.

Best regards, Andrey Borodin.