From: Peter Zijlstra <peterz@infradead.org>
To: Wolfram Strepp <wstrepp@gmx.de>
Cc: linux-kernel@vger.kernel.org, dwmw2@infradead.org,
akpm@linux-foundation.org
Subject: Re: [PATCH 2/2] Optimization of function rb_erase() in lib/rbtree.c
Date: Sat, 24 Jan 2009 13:46:15 +0100 [thread overview]
Message-ID: <1232801175.4859.61.camel@laptop> (raw)
In-Reply-To: <20090120215839.74570@gmx.net>
On Tue, 2009-01-20 at 22:58 +0100, Wolfram Strepp wrote:
> This patch reorganizes some lines, and therefore one if-condition
> can be omitted. Here an explanation.
>
> There are two cases when a node is erased:
> 'normal case': the successor is not the right-hand-child of the node to be erased
> 'special case': the successor is the right-hand child of the node to be erased
>
> In the normal case, the pointers from the nodes to its parents and vice-versa
> have all to be reconnected to its new parents/childs.
> The current code basically ignores this special case, doing the reconnections
> always in the way as if it were the normal case. This is ok, but not optimal.
> The patch re-arranges the lines, such that it makes use of one particular
> feature of the special case: when the node to be deleted is replaced by its successor,
> it pulls it child behind - so no reconnection is necessary. As a result, the
> if-condition, which checks if this child is a NIL-leave, can be omitted.
>
> Here some ascii-art, with following symbols (referring to the code):
> O: node to be deleted
> N: the successor of O
> P: parent of N
> C: child of N
> L: some other node
>
> normal case:
>
> O N
> / \ / \
> / \ / \
> L \ L \
> / \ P ----> / \ P
> / \ / \
> / /
> N C
> \ / \
> \
> C
> / \
>
>
> special case:
> O|P N
> / \ / \
> / \ / \
> L \ L \
> / \ N ----> / C
> \ / \
> \
> C
> / \
>
>
> Signed-off-by: Wolfram Strepp <wstrepp@gmx.de>
>
> ======================================
>
> --- a/lib/rbtree.c
> +++ b/lib/rbtree.c
> @@ -231,22 +231,13 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
> node = node->rb_right;
> while ((left = node->rb_left) != NULL)
> node = left;
> +
> child = node->rb_right;
> parent = rb_parent(node);
> color = rb_color(node);
>
> - if (child)
> - rb_set_parent(child, parent);
> - if (parent == old) {
> - parent->rb_right = child;
> - parent = node;
> - } else
> - parent->rb_left = child;
> -
> + /* connect 'node' with its new parent */
> node->rb_parent_color = old->rb_parent_color;
> - node->rb_right = old->rb_right;
> - node->rb_left = old->rb_left;
> -
> if (rb_parent(old))
> {
> if (rb_parent(old)->rb_left == old)
> @@ -256,9 +247,26 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
> } else
> root->rb_node = node;
>
> - rb_set_parent(old->rb_left, node);
> - if (old->rb_right)
> +
> + if (parent == old) {
> + /* special case: 'node' becomes parent, pulling its
> + child up behind --> no re-connecting necessary ! */
> + parent = node;
> + } else {
> + /* replace 'node' with its former child */
> + parent->rb_left = child;
> + if (child)
> + rb_set_parent(child, parent);
> +
> + /* connect 'node' to its new right-hand child */
> + node->rb_right = old->rb_right;
> rb_set_parent(old->rb_right, node);
> + }
> +
> + /* connect 'node' to its new left-hand child */
> + node->rb_left = old->rb_left;
> + rb_set_parent(old->rb_left, node);
> +
> goto color;
> }
OK, this patch is better done in smaller steps.
I'll have to admit to not having tested any of the below patches, but
they represent how I went about understanding your patch.
---
Subject: rbtree: code movement
From: Peter Zijlstra <a.p.zijlstra@chello.nl>
Date: Sat Jan 24 13:14:11 CET 2009
Move some code around in order to make the next change more obvious.
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
---
lib/rbtree.c | 19 ++++++++++---------
1 file changed, 10 insertions(+), 9 deletions(-)
Index: linux-2.6/lib/rbtree.c
===================================================================
--- linux-2.6.orig/lib/rbtree.c
+++ linux-2.6/lib/rbtree.c
@@ -237,6 +237,16 @@ void rb_erase(struct rb_node *node, stru
node = node->rb_right;
while ((left = node->rb_left) != NULL)
node = left;
+
+ if (rb_parent(old))
+ {
+ if (rb_parent(old)->rb_left == old)
+ rb_parent(old)->rb_left = node;
+ else
+ rb_parent(old)->rb_right = node;
+ } else
+ root->rb_node = node;
+
child = node->rb_right;
parent = rb_parent(node);
color = rb_color(node);
@@ -253,15 +263,6 @@ void rb_erase(struct rb_node *node, stru
node->rb_right = old->rb_right;
node->rb_left = old->rb_left;
- if (rb_parent(old))
- {
- if (rb_parent(old)->rb_left == old)
- rb_parent(old)->rb_left = node;
- else
- rb_parent(old)->rb_right = node;
- } else
- root->rb_node = node;
-
rb_set_parent(old->rb_left, node);
if (old->rb_right)
rb_set_parent(old->rb_right, node);
-------------------
Subject: rbtree: optimize a special case in rb_erase()
From: Wolfram Strepp <wstrepp@gmx.de>
Date: Sat Jan 24 13:17:04 CET 2009
There are two cases when a node is erased:
'normal case': the successor is not the right-hand-child of the node to be erased
'special case': the successor is the right-hand child of the node to be erased
Here some ascii-art, with following symbols (referring to the code):
O: node to be deleted
N: the successor of O
P: parent of N
C: child of N
L: some other node
normal case:
O N
/ \ / \
/ \ / \
L \ L \
/ \ P ----> / \ P
/ \ / \
/ /
N C
\ / \
\
C
/ \
special case:
O|P N
/ \ / \
/ \ / \
L \ L \
/ \ N ----> / C
\ / \
\
C
/ \
Notice that for the special case we don't have to reconnect C to N.
Signed-off-by: Wolfram Strepp <wstrepp@gmx.de>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
---
lib/rbtree.c | 8 ++++----
1 file changed, 4 insertions(+), 4 deletions(-)
Index: linux-2.6/lib/rbtree.c
===================================================================
--- linux-2.6.orig/lib/rbtree.c
+++ linux-2.6/lib/rbtree.c
@@ -251,13 +251,13 @@ void rb_erase(struct rb_node *node, stru
parent = rb_parent(node);
color = rb_color(node);
- if (child)
- rb_set_parent(child, parent);
if (parent == old) {
- parent->rb_right = child;
parent = node;
- } else
+ } else {
+ if (child)
+ rb_set_parent(child, parent);
parent->rb_left = child;
+ }
node->rb_parent_color = old->rb_parent_color;
node->rb_right = old->rb_right;
--------------
Subject: rbtree: further optimize the special case
From: Wolfram Strepp <wstrepp@gmx.de>
Date: Sat Jan 24 13:30:39 CET 2009
normal case:
O N
/ \ / \
/ \ / \
L \ L \
/ \ P ----> / \ P
/ \ / \
/ /
N C
\ / \
\
C
/ \
special case:
O|P N
/ \ / \
/ \ / \
L \ L \
/ \ N ----> / C
\ / \
\
C
/ \
Notice that for the special case we don't have to reconnect N to C.
Furthermore, notice that the initial checks:
if (!node->rb_left)
child = node->rb_right;
else if (!node->rb_right)
child = node->rb_left;
else
{
...
}
guarantee that old->rb_right is set in the final else branch, therefore
we can omit checking that again.
Signed-off-by: Wolfram Strepp <wstrepp@gmx.de>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
---
lib/rbtree.c | 8 ++++----
1 file changed, 4 insertions(+), 4 deletions(-)
Index: linux-2.6/lib/rbtree.c
===================================================================
--- linux-2.6.orig/lib/rbtree.c
+++ linux-2.6/lib/rbtree.c
@@ -257,15 +257,15 @@ void rb_erase(struct rb_node *node, stru
if (child)
rb_set_parent(child, parent);
parent->rb_left = child;
+
+ node->rb_right = old->rb_right;
+ rb_set_parent(old->rb_right, node);
}
node->rb_parent_color = old->rb_parent_color;
- node->rb_right = old->rb_right;
node->rb_left = old->rb_left;
-
rb_set_parent(old->rb_left, node);
- if (old->rb_right)
- rb_set_parent(old->rb_right, node);
+
goto color;
}
next prev parent reply other threads:[~2009-01-24 12:46 UTC|newest]
Thread overview: 3+ messages / expand[flat|nested] mbox.gz Atom feed top
2009-01-20 21:58 [PATCH 2/2] Optimization of function rb_erase() in lib/rbtree.c Wolfram Strepp
2009-01-24 12:46 ` Peter Zijlstra [this message]
2009-01-24 16:53 ` Wolfram Strepp
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1232801175.4859.61.camel@laptop \
--to=peterz@infradead.org \
--cc=akpm@linux-foundation.org \
--cc=dwmw2@infradead.org \
--cc=linux-kernel@vger.kernel.org \
--cc=wstrepp@gmx.de \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox