Date: Sat, 25 Jun 2022 07:43:30 GMT From: Doug Moore <dougm@FreeBSD.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org Subject: git: 61c74fb66f1b - main - rb_tree: optimize tree rotation Message-ID: <202206250743.25P7hUnQ077996@gitrepo.freebsd.org>
next in thread | raw e-mail | index | archive | help
The branch main has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=61c74fb66f1bef776923cbd5b2a62fb06b003f0c commit 61c74fb66f1bef776923cbd5b2a62fb06b003f0c Author: Doug Moore <dougm@FreeBSD.org> AuthorDate: 2022-06-25 07:40:16 +0000 Commit: Doug Moore <dougm@FreeBSD.org> CommitDate: 2022-06-25 07:40:16 +0000 rb_tree: optimize tree rotation The RB_ROTATE macros begin with fetching a field via a pointer. In most cases, that value is one that has already been pulled into a register, and the compiler cannot infer that. 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. Differential Revision: https://reviews.freebsd.org/D35520 --- sys/sys/tree.h | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) diff --git a/sys/sys/tree.h b/sys/sys/tree.h index 0403288d1d68..fb0136a0c69a 100644 --- a/sys/sys/tree.h +++ b/sys/sys/tree.h @@ -380,7 +380,6 @@ struct { \ } while (/*CONSTCOND*/ 0) #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ - (tmp) = RB_RIGHT(elm, field); \ if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ RB_SET_PARENT(RB_RIGHT(elm, field), elm, field); \ } \ @@ -392,7 +391,6 @@ struct { \ } while (/*CONSTCOND*/ 0) #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ - (tmp) = RB_LEFT(elm, field); \ if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ RB_SET_PARENT(RB_LEFT(elm, field), elm, field); \ } \ @@ -473,6 +471,7 @@ name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ } \ RB_FLIP_RIGHT(parent, field); \ if (RB_RED_RIGHT(parent, field)) { \ + child = elm; \ elm = parent; \ continue; \ } \ @@ -493,6 +492,7 @@ name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ } \ RB_FLIP_LEFT(parent, field); \ if (RB_RED_LEFT(parent, field)) { \ + child = elm; \ elm = parent; \ continue; \ } \ @@ -548,6 +548,7 @@ name##_RB_REMOVE_COLOR(struct name *head, \ RB_FLIP_LEFT(parent, field); \ else if (!RB_RED_RIGHT(sib, field)) { \ RB_FLIP_LEFT(parent, field); \ + elm = RB_LEFT(sib, field); \ RB_ROTATE_RIGHT(head, sib, elm, field); \ if (RB_RED_RIGHT(elm, field)) \ RB_FLIP_LEFT(sib, field); \ @@ -578,6 +579,7 @@ name##_RB_REMOVE_COLOR(struct name *head, \ RB_FLIP_RIGHT(parent, field); \ else if (!RB_RED_LEFT(sib, field)) { \ RB_FLIP_RIGHT(parent, field); \ + elm = RB_RIGHT(sib, field); \ RB_ROTATE_LEFT(head, sib, elm, field); \ if (RB_RED_LEFT(elm, field)) \ RB_FLIP_RIGHT(sib, field); \
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?202206250743.25P7hUnQ077996>