lkml.org 
[lkml]   [2012]   [Jul]   [25]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH 5/6] rbtree: faster augmented erase
On 07/23/2012 09:54 PM, Michel Lespinasse wrote:
> Add an augmented tree rotation callback to __rb_erase_color(), so that
> augmented tree information can be maintained while rebalancing.
>
> Also introduce rb_erase_augmented(), which is a version of rb_erase()
> with augmented tree callbacks. We need three callbacks here: one to
> copy the subtree's augmented value after stitching in a new node as
> the subtree root (rb_erase_augmented cases 2 and 3), one to propagate
> the augmented values up after removing a node, and one to pass up to
> __rb_erase_color() to handle rebalancing.
>
> Things are set up so that rb_erase() uses dummy do-nothing callbacks,
> which get inlined and eliminated by the compiler, and also inlines the
> __rb_erase_color() call so as to generate similar code than before
> (once again, the compiler somehow generates smaller code than before
> with all that inlining, but the speed seems to be on par). For the
> augmented version rb_erase_augmented(), however, we use partial
> inlining: we want rb_erase_augmented() and its augmented copy and
> propagation callbacks to get inlined together, but we still call into
> a generic __rb_erase_color() (passing a non-inlined callback function)
> for the rebalancing work. This is intended to strike a reasonable
> compromise between speed and compiled code size.

I guess moving the inlined function to the include file
takes care of my concerns for patch 4/6...

> Signed-off-by: Michel Lespinasse <walken@google.com>

Acked-by: Rik van Riel <riel@redhat.com>


\
 
 \ /
  Last update: 2012-07-25 20:41    [W:0.058 / U:0.544 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site