NotificationsYou must be signed in to change notification settings
Fork6
Star31

Commit849110d

committed

Optimize sifting down in binaryheap.

Presently, each iteration of the loop in sift_down() will perform3 comparisons if both children are larger than the parent node (2for comparing each child to the parent node, and a third to comparethe children to each other). By first comparing the children toeach other and then comparing the larger child to the parent node,we can accomplish the same thing with just 2 comparisons (whilealso not affecting the number of comparisons in any other case).Author: ChangAo ChenReviewed-by: Robert HaasDiscussion:https://postgr.es/m/tencent_0142D8DA90940B9930BCC08348BBD6D0BB07%40qq.com

1 parentaf21152 commit849110dCopy full SHA for 849110d

File tree

1 file changed

-20

lines changed

src/common
- binaryheap.c

1 file changed

-20

lines changed

`‎src/common/binaryheap.c`

Lines changed: 9 additions & 20 deletions

Original file line number	Diff line number	Diff line change
`@@ -323,34 +323,23 @@ sift_down(binaryheap *heap, int node_off)`
`323`	`323`	`{`
`324`	`324`	`intleft_off=left_offset(node_off);`
`325`	`325`	`intright_off=right_offset(node_off);`
`326`		`-intswap_off=0;`
	`326`	`+intswap_off=left_off;`
`327`	`327`
`328`		`-/* Is the left child larger than the parent? */`
`329`		`-if (left_off<heap->bh_size&&`
`330`		`-heap->bh_compare(node_val,`
`331`		`-heap->bh_nodes[left_off],`
`332`		`-heap->bh_arg)<0)`
`333`		`-swap_off=left_off;`
`334`		`-`
`335`		`-/* Is the right child larger than the parent? */`
	`328`	`+/* Is the right child larger than the left child? */`
`336`	`329`	`if (right_off<heap->bh_size&&`
`337`		`-heap->bh_compare(node_val,`
	`330`	`+heap->bh_compare(heap->bh_nodes[left_off],`
`338`	`331`	`heap->bh_nodes[right_off],`
`339`	`332`	`heap->bh_arg)<0)`
`340`		`-{`
`341`		`-/* swap with the larger child */`
`342`		`-if (!swap_off\|\|`
`343`		`-heap->bh_compare(heap->bh_nodes[left_off],`
`344`		`-heap->bh_nodes[right_off],`
`345`		`-heap->bh_arg)<0)`
`346`		`-swap_off=right_off;`
`347`		`-}`
	`333`	`+swap_off=right_off;`
`348`	`334`
`349`	`335`	`/*`
`350`		`- * Ifwe didn't find anything to swap, the heap condition is`
	`336`	`+ * Ifno children or parent is >= the larger child, heap condition is`
`351`	`337`	`* satisfied, and we're done.`
`352`	`338`	`*/`
`353`		`-if (!swap_off)`
	`339`	`+if (left_off >=heap->bh_size\|\|`
	`340`	`+heap->bh_compare(node_val,`
	`341`	`+heap->bh_nodes[swap_off],`
	`342`	`+heap->bh_arg) >=0)`
`354`	`343`	`break;`
`355`	`344`
`356`	`345`	`/*`

0 commit comments

Comments

(0)

Movatterモバイル変換

Navigation Menu

Search code, repositories, users, issues, pull requests...

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Commit849110d

File tree

1 file changed

1 file changed

`‎src/common/binaryheap.c`

0 commit comments