Re: Reduce one comparison in binaryheap's sift down

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