Re: Reduce one comparison in binaryheap's sift down

[cca5507]

Agree, new version patch is attached.


--
Regards,
ChangAo Chen



------------------ Original ------------------
From:                                                                           
                                             "Nathan Bossart"                   
                                                                 
<nathandboss...@gmail.com&gt;;
Date:&nbsp;Tue, Oct 29, 2024 04:32 AM
To:&nbsp;"Robert Haas"<robertmh...@gmail.com&gt;;
Cc:&nbsp;"cca5507"<cca5...@qq.com&gt;;"pgsql-hackers"<pgsql-hackers@lists.postgresql.org&gt;;
Subject:&nbsp;Re: Reduce one comparison in binaryheap's sift down



On Mon, Oct 28, 2024 at 12:40:20PM -0400, Robert Haas wrote:
&gt; Hmm, so at present we compare the parent to the left child and to the
&gt; right child. If it's smaller than neither, everything is OK. If it's
&gt; smaller than one, we swap it with that one. If it's smaller than both,
&gt; we compare the left and right child with each other and swap the
&gt; parent with the larger of the two. Hence, if a node has 2 children, we
&gt; always do 2 comparisons, and we sometimes do 3 comparisons.
&gt; 
&gt; With the patch, we first compare the two children to each other, and
&gt; then compare the larger one to the parent. If the parent is smaller
&gt; than the larger child, we swap them. Hene, if a node has 2 children,
&gt; we always do 2 comparisons.
&gt; 
&gt; Unless I'm missing something, that does seem significantly better.

That sounds right to me.&nbsp; I think there are some ways to simplify the code
a little further, though.&nbsp; For example, you can initialize larger_off to
left_off, and before any comparisons happen, break if the node has no
children, i.e., left_off &gt;= heap-&gt;bh_size.&nbsp; That should help reduce 
the
number of offset assignments and comparisons, which I found difficult to
read at first.

-- 
nathan

v2-0001-Reduce-one-comparison-in-binaryheap-s-sift-down.patch
Description: Binary data