Re: [Xen-devel] [PATCH v6 06/16 RESEND] rbtree: low level optimizations in rb_insert_color()

["Jan Beulich" <JBeulich@xxxxxxxx>]

>>> On 21.11.17 at 16:19, <kpraveen.lkml@xxxxxxxxx> wrote:
> From: Michel Lespinasse <walken@xxxxxxxxxx>
> 
> - Use the newly introduced rb_set_parent_color() function to flip the color
>   of nodes whose parent is already known.
> - Optimize rb_parent() when the node is known to be red - there is no need
>   to mask out the color in that case.
> - Flipping gparent's color to red requires us to fetch its rb_parent_color
>   field, so we can reuse it as the parent value for the next loop iteration.
> - Do not use __rb_rotate_left() and __rb_rotate_right() to handle tree
>   rotations: we already have pointers to all relevant nodes, and know their
>   colors (either because we want to adjust it, or because we've tested it,
>   or we can deduce it as black due to the node proximity to a known red 
> node).
>   So we can generate more efficient code by making use of the node pointers
>   we already have, and setting both the parent and color attributes for
>   nodes all at once. Also in Case 2, some node attributes don't have to
>   be set because we know another tree rotation (Case 3) will always follow
>   and override them.
> 
> Signed-off-by: Michel Lespinasse <walken@xxxxxxxxxx>
> Cc: Andrea Arcangeli <aarcange@xxxxxxxxxx>
> Acked-by: David Woodhouse <David.Woodhouse@xxxxxxxxx>
> Cc: Rik van Riel <riel@xxxxxxxxxx>
> Cc: Peter Zijlstra <a.p.zijlstra@xxxxxxxxx>
> Cc: Daniel Santos <daniel.santos@xxxxxxxxx>
> Cc: Jens Axboe <axboe@xxxxxxxxx>
> Cc: "Eric W. Biederman" <ebiederm@xxxxxxxxxxxx>
> Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
> Signed-off-by: Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx>
> [Linux commit 5bc9188aa207dafd47eab57df7c4fe5b3d3f636a]
> 
> Ported to Xen.
> 
> Signed-off-by: Praveen Kumar <kpraveen.lkml@xxxxxxxxx>

Acked-by: Jan Beulich <jbeulich@xxxxxxxx>



_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxxxxxxxxx
https://lists.xenproject.org/mailman/listinfo/xen-devel