From: Nathan Bossart <nathan@postgresql.org>
To: pgsql-committers@lists.postgresql.org
Subject: pgsql: Optimize sifting down in binaryheap.
Date: Wed, 30 Oct 2024 16:29:12 +0000
Message-ID: <E1t6BZJ-003AmX-1k@gemulon.postgresql.org> (raw)
Optimize sifting down in binaryheap.
Presently, each iteration of the loop in sift_down() will perform
3 comparisons if both children are larger than the parent node (2
for comparing each child to the parent node, and a third to compare
the children to each other). By first comparing the children to
each other and then comparing the larger child to the parent node,
we can accomplish the same thing with just 2 comparisons (while
also not affecting the number of comparisons in any other case).
Author: ChangAo Chen
Reviewed-by: Robert Haas
Discussion: https://postgr.es/m/tencent_0142D8DA90940B9930BCC08348BBD6D0BB07%40qq.com
Branch
------
master
Details
-------
https://git.postgresql.org/pg/commitdiff/849110dd3eec3e21c358e24f11c6d501d05eee72
Modified Files
--------------
src/common/binaryheap.c | 29 +++++++++--------------------
1 file changed, 9 insertions(+), 20 deletions(-)
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: pgsql-committers@postgresql.org
Cc: nathan@postgresql.org, pgsql-committers@lists.postgresql.org
Subject: Re: pgsql: Optimize sifting down in binaryheap.
In-Reply-To: <E1t6BZJ-003AmX-1k@gemulon.postgresql.org>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox