[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-Id: <1232786621.4859.35.camel@laptop>
Date: Sat, 24 Jan 2009 09:43:41 +0100
From: Peter Zijlstra <peterz@...radead.org>
To: Wolfram Strepp <wstrepp@....de>
Cc: linux-kernel@...r.kernel.org, dwmw2@...radead.org,
akpm@...ux-foundation.org
Subject: Re: [PATCH 1/2] Optimization of function rb_erase() in lib/rbtree.c
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@...llo.nl>
> Signed-off-by: Wolfram Strepp <wstrepp@....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;
>
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists