Re: Reduce one comparison in binaryheap's sift down

From: cca5507 <cca5507(at)qq(dot)com>
To: Nathan Bossart <nathandbossart(at)gmail(dot)com>, Robert Haas <robertmhaas(at)gmail(dot)com>
Cc: pgsql-hackers <pgsql-hackers(at)lists(dot)postgresql(dot)org>
Subject: Re: Reduce one comparison in binaryheap's sift down
Date: 2024-10-29 03:21:15
Message-ID: tencent_0E3134AD10A6F622A554060ECFED00C16E05@qq.com
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

Agree, new version patch is attached.

--
Regards,
ChangAo Chen

------------------&nbsp;Original&nbsp;------------------
From: "Nathan Bossart" <nathandbossart(at)gmail(dot)com&gt;;
Date:&nbsp;Tue, Oct 29, 2024 04:32 AM
To:&nbsp;"Robert Haas"<robertmhaas(at)gmail(dot)com&gt;;
Cc:&nbsp;"cca5507"<cca5507(at)qq(dot)com&gt;;"pgsql-hackers"<pgsql-hackers(at)lists(dot)postgresql(dot)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

Attachment Content-Type Size
v2-0001-Reduce-one-comparison-in-binaryheap-s-sift-down.patch application/octet-stream 2.4 KB

In response to

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Michael Paquier 2024-10-29 04:12:25 Re: Add isolation test template in injection_points for wait/wakeup/detach
Previous Message Jingtang Zhang 2024-10-29 03:18:42 Re: Introduce new multi insert Table AM and improve performance of various SQL commands with it for Heap AM