Re: [PATCH 5/6] rbtree: faster augmented erase

[Rik van Riel]

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@xxxxxxxxxx>

Acked-by: Rik van Riel <riel@xxxxxxxxxx>
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/