Date: Fri, 9 Feb 2024 10:32:45 -0600
From: Nathan Bossart <nathandbossart@gmail.com>
To: "Andrey M. Borodin" <x4mmm@yandex-team.ru>
Cc: Andres Freund <andres@anarazel.de>,
	Heikki Linnakangas <hlinnaka@iki.fi>,
	Mats Kindahl <mats@timescale.com>, Tom Lane <tgl@sss.pgh.pa.us>,
	pgsql-hackers@lists.postgresql.org
Subject: Re: glibc qsort() vulnerability
Message-ID: <20240209163245.GB663211@nathanxps13>
References: <508821.1707232276@sss.pgh.pa.us>
 <20240206205305.GB3891538@nathanxps13>
 <642084.1707252958@sss.pgh.pa.us>
 <CA+14425TqyUZ3-O7zYsW6u85yY5diCz-p_TPQ2bZovn-N-fQ9A@mail.gmail.com>
 <cc9b0272-849a-4a88-8200-59786d18b7a1@iki.fi>
 <20240207214857.rjqkutiaapka2xyp@awork3.anarazel.de>
 <20240207222124.GA382832@nathanxps13>
 <20240208004207.aoyrtv577nmhrivy@awork3.anarazel.de>
 <20240208015211.GA445153@nathanxps13>
 <B9DFF152-D31B-4E2D-A3DD-0AB92BFF71E4@yandex-team.ru>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <B9DFF152-D31B-4E2D-A3DD-0AB92BFF71E4@yandex-team.ru>
Archived-At: <https://www.postgresql.org/message-id/20240209163245.GB663211%40nathanxps13>
Precedence: bulk

On Fri, Feb 09, 2024 at 01:19:49PM +0500, Andrey M. Borodin wrote:
> If we care about branch prediction in comparison function, maybe we could
> produce sorting that inlines comparator, thus eliminating function call
> to comparator? We convert comparison logic to int, to extract comparison
> back then.
> 
> I bet “call" is more expensive than “if".

It might make sense to have a couple of built-in qsort implementations for
pointers to integers, pointers to unsigned integers, etc.  However, a lot
of current use-cases require inspecting specific fields of structs, so
(assuming I understand your proposal correctly), we'd end up with many
qsort implementations.  If that can be made simple and elegant and
demonstrates substantial improvements, then it might be worth considering,
but I'm somewhat skeptical that the current uses are performance-sensitive
enough to be worth the effort.

-- 
Nathan Bossart
Amazon Web Services: https://aws.amazon.com