[PATCH 1/2] Optimization of function rb_erase() in lib/rbtree.c

[PATCH 1/2] Optimization of function rb_erase() in lib/rbtree.c

[Wolfram Strepp]

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

Re: [PATCH 1/2] Optimization of function rb_erase() in lib/rbtree.c

[Peter Zijlstra]

On Tue, 2009-01-20 at 22:55 +0100, Wolfram Strepp wrote:
> 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.


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

Acked-by: Peter Zijlstra <a.p.zijlstra@chello.nl>

> 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;
> 

[PATCH] Optimization of function rb_erase() in lib/rbtree.c

[Wolfram Strepp]

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 !
		.
	}
}

Signed-off-by: Wolfram Strepp <wstrepp@gmx.de>
Acked-by: Peter Zijlstra <a.p.zijlstra@chello.nl>

================================================
--- 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;


-- 
NUR NOCH BIS 31.01.! GMX FreeDSL - Telefonanschluss + DSL 
für nur 16,37 EURO/mtl.!* http://dsl.gmx.de/?ac=OM.AD.PD003K11308T4569a