Thread: Re: Reduce one comparison in binaryheap's sift down
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
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
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
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
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