Messages in this thread | | | Date | Sat, 24 Jan 2009 17:53:57 +0100 | From | "Wolfram Strepp" <> | Subject | Re: [PATCH 2/2] Optimization of function rb_erase() in lib/rbtree.c |
| |
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 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |