Optimization of function rb_erase() in lib/rbtree.c
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:
Quoted 6 lines
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.
====================================================
lib/rbtree.c +4 -10
@@ -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)) { - registerstruct 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 ;
Signature · 1 line
Psssst! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger
Quoted 28 lines · Wolfram Strepp
Hello,
i have reviewed the code of the rb-tree implementation
in the kernel, and distilled two small patches for filelib/rbtree.c, which optimize and cleanup the code of functionsrb_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/122It 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:
Quoted 2 lines
Only in 2.4.21pre2aa1: 00_rbtree-cleanups-1
Quoted 7 lines
Quoted 4 lines
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.
The above is not a proper changelog, please ammend it, and write it in the form found in Paolo's STL email.
"
if ((!A || B) && C)
{
//
}
else
{
if (C)
{
if (A) __w->_M_left->_M_color = _M_black;
//
}
//
}Therefore, the check for A (_w->_M_left, that is) in the innermost if is definitely redundant. "
But add the extra redundant case in our code.
Then resend, and you can add
Quoted 46 lines
Signed-off-by Wolfram Strepp <[email protected]>====================================================
lib/rbtree.c +4
-10@@ -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)) { - registerstruct 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 ;
PATCH 1/1 Optimization of function rb_erase() in lib/rbtree.c
In the patch below, 4 redundant if-conditions in function __rb_erase_color() in lib/rbtree.c are removed. Here an explanation for it. In pseudo-source-code, the
structure of the code is as follows:
if ((!A || B) && (!C || D)) {
.
.
.
} else {
if (!C || D) {//if this is true, it implies: (A == true) && (B == false)
if (A) {//hence this always evaluates to 'true'...
.
}
.
//at this point, C always becomes true, because of:
__rb_rotate_right/left();
//and:
other = parent->rb_right/left;
}
.
.
if (C) {//...and this too !
.
}
}================================================
lib/rbtree.c +4 -10
@@ -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)) { - registerstruct 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 ;
Signature · 2 lines
NUR NOCH BIS 31.01.! GMX FreeDSL - Telefonanschluss + DSL für nur 16,37 EURO/mtl.!* http://dsl.gmx.de/?ac=OM.AD.PD003K11308T4569a