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

[Michel Lespinasse]

On Fri, Jul 27, 2012 at 5:44 PM, Michel Lespinasse <walken@xxxxxxxxxx> wrote:
> On Fri, Jul 27, 2012 at 1:02 PM, Peter Zijlstra <peterz@xxxxxxxxxxxxx> wrote:
>> As it stands rb_erase() isn't inlined and its rather big,
>> why would you want to inline it for augmented callers?
>
> Just as the non-augmented rb_erase() is generated (as a non-inline
> function) by merging together the rb_erase_augmented() inline function
> and its dummy callbacks, I want each library that uses augmented
> rbtrees to generate their own rb_erase() equivalent using their own
> callbacks. The inline function in rbtree_internal.h is only to be used
> as a template for generating one non-inline instance for each data
> structure that uses augmented rbtrees.

One more thing while we're talking about compiled code size. As you
noted, the non-augmented rb_erase() is pretty big. However, that size
includes the inlined rebalancing code. For the augmented erase
functions, my proposal is to the rebalancing part (rb_erase_color with
the rotate callback) will not be inlined, so as to limit the size of
the erase functions for each augmented rbtree data structure.

-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
--
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/