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

["Jan Beulich" <JBeulich@xxxxxxxx>]

>>> On 21.11.17 at 16:20, <kpraveen.lkml@xxxxxxxxx> wrote:
> From: Michel Lespinasse <walken@xxxxxxxxxx>
> 
> Various minor optimizations in rb_erase():
> - Avoid multiple loading of node->__rb_parent_color when computing parent
>   and color information (possibly not in close sequence, as there might
>   be further branches in the algorithm)
> - In the 1-child subcase of case 1, copy the __rb_parent_color field from
>   the erased node to the child instead of recomputing it from the desired
>   parent and color
> - When searching for the erased node's successor, differentiate between
>   cases 2 and 3 based on whether any left links were followed. This avoids
>   a condition later down.
> - In case 3, keep a pointer to the erased node's right child so we don't
>   have to refetch it later to adjust its parent.
> - In the no-childs subcase of cases 2 and 3, place the rebalance assigment
>   last so that the compiler can remove the following if(rebalance) test.
> 
> Also, added some comments to illustrate cases 2 and 3.
> 
> Signed-off-by: Michel Lespinasse <walken@xxxxxxxxxx>
> Acked-by: Rik van Riel <riel@xxxxxxxxxx>
> Cc: Peter Zijlstra <a.p.zijlstra@xxxxxxxxx>
> Cc: Andrea Arcangeli <aarcange@xxxxxxxxxx>
> Cc: David Woodhouse <dwmw2@xxxxxxxxxxxxx>
> Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
> Signed-off-by: Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx>
> [Linux commit 4f035ad67f4633c233cb3642711d49b4efc9c82d]
> 
> 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