Horton

Thread

Commits

  1. Optimize sifting down in binaryheap.

  1. Reduce one comparison in binaryheap's sift down

    cca5507 <cca5507@qq.com> — 2024-10-28T15:21:39Z

    Hi,

I think we can reduce&nbsp;one comparison in binaryheap's sift down, right?


Here is a patch to fix it.


--
Regards,
ChangAo Chen

  2. Re: Reduce one comparison in binaryheap's sift down

    Robert Haas <robertmhaas@gmail.com> — 2024-10-28T16:40:20Z

    On Mon, Oct 28, 2024 at 11:22 AM cca5507 <cca5507@qq.com> wrote:
> I think we can reduce one comparison in binaryheap's sift down, right?
>
> Here is a patch to fix it.

Hmm, so at present we compare the parent to the left child and to the
right child. If it's smaller than neither, everything is OK. If it's
smaller than one, we swap it with that one. If it's smaller than both,
we compare the left and right child with each other and swap the
parent with the larger of the two. Hence, if a node has 2 children, we
always do 2 comparisons, and we sometimes do 3 comparisons.

With the patch, we first compare the two children to each other, and
then compare the larger one to the parent. If the parent is smaller
than the larger child, we swap them. Hene, if a node has 2 children,
we always do 2 comparisons.

Unless I'm missing something, that does seem significantly better.

-- 
Robert Haas
EDB: http://www.enterprisedb.com

  3. Re: Reduce one comparison in binaryheap's sift down

    Nathan Bossart <nathandbossart@gmail.com> — 2024-10-28T20:32:36Z

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

That sounds right to me.  I think there are some ways to simplify the code
a little further, though.  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 >= heap->bh_size.  That should help reduce the
number of offset assignments and comparisons, which I found difficult to
read at first.

-- 
nathan

  4. Re: Reduce one comparison in binaryheap's sift down

    cca5507 <cca5507@qq.com> — 2024-10-29T03:21:15Z

    Agree, new version patch is attached.


--
Regards,
ChangAo Chen



------------------&nbsp;Original&nbsp;------------------
From:                                                                                                                        "Nathan Bossart"                                                                                    <nathandbossart@gmail.com&gt;;
Date:&nbsp;Tue, Oct 29, 2024 04:32 AM
To:&nbsp;"Robert Haas"<robertmhaas@gmail.com&gt;;
Cc:&nbsp;"cca5507"<cca5507@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

  5. Re: Reduce one comparison in binaryheap's sift down

    Nathan Bossart <nathandbossart@gmail.com> — 2024-10-29T15:00:28Z

    On Tue, Oct 29, 2024 at 11:21:15AM +0800, cca5507 wrote:
> Agree, new version patch is attached.

I might editorialize a bit, but overall this looks pretty good to me.
Robert, would you like to commit this, or shall I?

-- 
nathan

  6. Re: Reduce one comparison in binaryheap's sift down

    Robert Haas <robertmhaas@gmail.com> — 2024-10-30T12:09:17Z

    On Tue, Oct 29, 2024 at 11:00 AM Nathan Bossart
<nathandbossart@gmail.com> wrote:
> On Tue, Oct 29, 2024 at 11:21:15AM +0800, cca5507 wrote:
> > Agree, new version patch is attached.
>
> I might editorialize a bit, but overall this looks pretty good to me.
> Robert, would you like to commit this, or shall I?

I would be delighted if you could take care of it.

-- 
Robert Haas
EDB: http://www.enterprisedb.com

  7. Re: Reduce one comparison in binaryheap's sift down

    Nathan Bossart <nathandbossart@gmail.com> — 2024-10-30T16:30:04Z

    On Wed, Oct 30, 2024 at 08:09:17AM -0400, Robert Haas wrote:
> I would be delighted if you could take care of it.

Committed.

-- 
nathan