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
