Messages in this thread Patch in this message | | | Date | Tue, 20 Jan 2009 22:55:56 +0100 | From | "Wolfram Strepp" <> | Subject | [PATCH 1/2] Optimization of function rb_erase() in lib/rbtree.c |
| |
Hello,
i have reviewed the code of the rb-tree implementation in the kernel, and distilled two small patches for file lib/rbtree.c, which optimize and cleanup the code of functions rb_erase() and __rb_erase_color(). In summary, there are 5 if()-conditions which can be eliminated. The patches reduce the code size (normal kernel build on x86) of this functions by 23 bytes, or 4.5 %.
So although this is not a dramatic change, i think its worth it, given the many places in the kernel where it is used (and given the fact that processors dont like if-conditions).
The patches are tested on x86.
------------------------------------------
The first patch was already posted some years ago, see: http://lkml.org/lkml/2002/11/22/146 and: http://lkml.org/lkml/2002/11/24/122
It was finally merged by the original author of the rb-tree implementation, Andrea Arcangeli, in one of his kernel trees. Citing from http://lkml.org/lkml/2002/12/25/51:
>Only in 2.4.21pre2aa1: 00_rbtree-cleanups-1 > > Merged rbtree cleanups/microoptimizations from Érsek László after > verifying their math correctness also with the help of Paolo Carlini > and of some gentle reminder from Rusty, they are obviously right, > thanks.
But obviousely, it never found is way into the mainline kernel, so here it is again.
Signed-off-by: Wolfram Strepp <wstrepp@gmx.de>
==================================================== --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -163,17 +163,14 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, { if (!other->rb_right || rb_is_black(other->rb_right)) { - struct rb_node *o_left; - if ((o_left = other->rb_left)) - rb_set_black(o_left); + rb_set_black(other->rb_left); rb_set_red(other); __rb_rotate_right(other, root); other = parent->rb_right; } rb_set_color(other, rb_color(parent)); rb_set_black(parent); - if (other->rb_right) - rb_set_black(other->rb_right); + rb_set_black(other->rb_right); __rb_rotate_left(parent, root); node = root->rb_node; break; @@ -200,17 +197,14 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, { if (!other->rb_left || rb_is_black(other->rb_left)) { - register struct rb_node *o_right; - if ((o_right = other->rb_right)) - rb_set_black(o_right); + rb_set_black(other->rb_right); rb_set_red(other); __rb_rotate_left(other, root); other = parent->rb_left; } rb_set_color(other, rb_color(parent)); rb_set_black(parent); - if (other->rb_left) - rb_set_black(other->rb_left); + rb_set_black(other->rb_left); __rb_rotate_right(parent, root); node = root->rb_node; break; -- 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/
| |