Optimize sifting down in binaryheap.
authorNathan Bossart <nathan@postgresql.org>
Wed, 30 Oct 2024 16:28:34 +0000 (11:28 -0500)
committerNathan Bossart <nathan@postgresql.org>
Wed, 30 Oct 2024 16:28:34 +0000 (11:28 -0500)
commit849110dd3eec3e21c358e24f11c6d501d05eee72
tree5b39238872860c9b19802531a81bc9ceac59e097
parentaf21152268317323480caa790c4a6347110f8085
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
src/common/binaryheap.c