Differential D35520

rb_tree: optimize tree rotation
ClosedPublic
Actions

Authored by dougm on Jun 19 2022, 2:59 AM.

Tags

None

Referenced Files

	F158946505: D35520.diff
	Mon, Jun 8, 3:01 AM

	Unknown Object (File)
	Sun, May 31, 9:25 PM

	Unknown Object (File)
	Sun, May 31, 8:42 AM

	Unknown Object (File)
	Wed, May 27, 12:07 PM

	Unknown Object (File)
	Tue, May 26, 6:27 AM

	Unknown Object (File)
	Mon, May 25, 10:48 PM

	Unknown Object (File)
	Mon, May 18, 6:08 AM

	Unknown Object (File)
	Thu, May 14, 5:56 PM

Subscribers

Details

Reviewers

Commits

rG6f7a96cfe537: rb_tree: optimize tree rotation
rG61c74fb66f1b: rb_tree: optimize tree rotation

Summary

The RB_ROTATE macros begin with fetching a field via a pointer. In almost most cases, that value is one that is already in a register, and the compiler cannot infer it. So, to eliminate those needless fetches, have the caller of the RB_ROTATE macros present the data in the third macro parameter, rather than having the macro fetch it.

And a few minor style cleanups.

Diff Detail

Repository

rG FreeBSD src repository

Lint

Lint Not Applicable

Unit

Tests Not Applicable

Event Timeline

dougm requested review of this revision.Jun 19 2022, 2:59 AM

dougm created this revision.

Rename variables in REMOVE_COLOR (elm->child, sib->elm) to make it look more like the INSERT_COLOR code.

Purify the patch.

Find a better (smaller) way to set 'child' in RB_INSERT_COLOR. Reduce lip3 size from 8830 to 8734.

dougm mentioned this in D35524: rb_tree: optimize bit twiddle.Jun 23 2022, 3:13 AM

alc accepted this revision.Jun 25 2022, 7:30 AM

This revision is now accepted and ready to land.Jun 25 2022, 7:30 AM

Closed by commit rG61c74fb66f1b: rb_tree: optimize tree rotation (authored by dougm). · Explain WhyJun 25 2022, 7:43 AM

This revision was automatically updated to reflect the committed changes.

dougm added a commit: rG61c74fb66f1b: rb_tree: optimize tree rotation.

Herald added a subscriber: imp. · View Herald TranscriptJun 25 2022, 7:43 AM

dougm added a commit: rG6f7a96cfe537: rb_tree: optimize tree rotation.Aug 1 2022, 5:46 AM

Revision Contents
Changeset List

Path

Size

sys/

sys/

6 lines

Diff 107369

sys/sys/tree.h

Loading...