public inbox for [email protected]  

help / color / mirror / Atom feed

From: Andrey Borodin <[email protected]>
To: Nathan Bossart <[email protected]>
Cc: Andres Freund <[email protected]>
Cc: Heikki Linnakangas <[email protected]>
Cc: Mats Kindahl <[email protected]>
Cc: Tom Lane <[email protected]>
Cc: pgsql-hackers mailing list <[email protected]>
Subject: Re: glibc qsort() vulnerability
Date: Sat, 10 Feb 2024 00:02:08 +0500
Message-ID: <[email protected]> (raw)
In-Reply-To: <20240209163245.GB663211@nathanxps13>
References: <[email protected]>
	<20240206205305.GB3891538@nathanxps13>
	<[email protected]>
	<CA+14425TqyUZ3-O7zYsW6u85yY5diCz-p_TPQ2bZovn-N-fQ9A@mail.gmail.com>
	<[email protected]>
	<[email protected]>
	<20240207222124.GA382832@nathanxps13>
	<[email protected]>
	<20240208015211.GA445153@nathanxps13>
	<[email protected]>
	<20240209163245.GB663211@nathanxps13>



> On 9 Feb 2024, at 21:32, Nathan Bossart <[email protected]> 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 <[email protected]> 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.

view thread (16+ messages)

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients using the --to and --cc options:
  reply via email

  To: [email protected]
  Cc: [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected]
  Subject: Re: glibc qsort() vulnerability
  In-Reply-To: <[email protected]>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox