* [PATCH 2/2] Optimization of function rb_erase() in lib/rbtree.c
@ 2009-01-20 21:58 Wolfram Strepp
2009-01-24 12:46 ` Peter Zijlstra
0 siblings, 1 reply; 3+ messages in thread
From: Wolfram Strepp @ 2009-01-20 21:58 UTC (permalink / raw)
To: linux-kernel; +Cc: dwmw2, akpm
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;
}
--
Psssst! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger
^ permalink raw reply [flat|nested] 3+ messages in thread* Re: [PATCH 2/2] Optimization of function rb_erase() in lib/rbtree.c 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 2009-01-24 16:53 ` Wolfram Strepp 0 siblings, 1 reply; 3+ messages in thread From: Peter Zijlstra @ 2009-01-24 12:46 UTC (permalink / raw) To: Wolfram Strepp; +Cc: linux-kernel, dwmw2, akpm 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; } ^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH 2/2] Optimization of function rb_erase() in lib/rbtree.c 2009-01-24 12:46 ` Peter Zijlstra @ 2009-01-24 16:53 ` Wolfram Strepp 0 siblings, 0 replies; 3+ messages in thread From: Wolfram Strepp @ 2009-01-24 16:53 UTC (permalink / raw) To: Peter Zijlstra; +Cc: linux-kernel, dwmw2, akpm Hello Peter, > 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. > 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; > } > > I'm fine with your reorganization. Im just building a kernel to test it, but quite sure it will work. Regards, Wolfram -- Psssst! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger ^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2009-01-24 16:54 UTC | newest] Thread overview: 3+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 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 2009-01-24 16:53 ` Wolfram Strepp
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox