Differential D35520

rb_tree: optimize tree rotation
ClosedPublic
Actions

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

Tags

None

Referenced Files

	Unknown Object (File)
	Mon, Sep 8, 12:28 PM

	Unknown Object (File)
	Sun, Aug 24, 2:16 PM

	Unknown Object (File)
	Thu, Aug 21, 9:16 AM

	Unknown Object (File)
	Mon, Aug 18, 3:03 PM

	Unknown Object (File)
	Aug 6 2025, 2:21 PM

	Unknown Object (File)
	Aug 4 2025, 5:14 AM

	Unknown Object (File)
	Jul 29 2025, 10:07 AM

	Unknown Object (File)
	Jul 29 2025, 9:52 AM

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...