lkml.org 
[lkml]   [2012]   [Jul]   [27]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
SubjectRe: [PATCH 4/6] rbtree: faster augmented insert
From
On Fri, Jul 27, 2012 at 12:26 PM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Fri, 2012-07-20 at 05:31 -0700, Michel Lespinasse wrote:
>> --- a/lib/rbtree.c
>> +++ b/lib/rbtree.c
>> @@ -88,7 +88,8 @@ __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
>> root->rb_node = new;
>> }
>>
>> -void rb_insert_color(struct rb_node *node, struct rb_root *root)
>> +inline void rb_insert_augmented(struct rb_node *node, struct rb_root *root,
>> + rb_augment_rotate *augment)
>
> Daniel probably knows best, but I would have expected something like:
>
> __always_inline void
> __rb_insert(struct rb_node *node, struct rb_root *root,
> const rb_augment_rotate *augment)
>
> Where you force inline and use a const function pointer since GCC is
> better with inlining them -- iirc, Daniel?

This hasn't been necessary with my compiler, but I can see how this
might help with older gcc versions. I really haven't investigated that
much and would be open to daniel's suggestions there.

To answer your question in the next email, we're using a gcc 4.6
variant with some local patches. TBH I don't know precisely what's in
there, however I think our compiler team makes a good job of working
with upstream so whatever changes they have are probably coming to a
future gcc version :)

>> {
>> struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;
>>
>> @@ -152,6 +153,7 @@ void rb_insert_color(struct rb_node *node, struct rb_root *root)
>> rb_set_parent_color(tmp, parent,
>> RB_BLACK);
>> rb_set_parent_color(parent, node, RB_RED);
>> + augment(parent, node);
>
> And possibly:
> if (augment)
> augment(parent, node);
>
> That would obviate the need for the dummy..

__rb_insert() gets instanciated two times, one as rb_insert_color()
with dummy callbacks, and one as rb_insert_augmented() itself with
user-passed callbacks. Using NULL instead of dummy callbacks would
generate the same code in the rb_insert_color() instance, but not in
the version that takes user-passed callbacks (i.e. there would be an
extra check for NULL there, which we don't want).

>> +void rb_insert_color(struct rb_node *node, struct rb_root *root) {
>
> placed your { wrong..

Oops (caught myself a few times doing that, missed this one
apparently... thanks for noticing)

>> + rb_insert_augmented(node, root, dummy);
>> +}
>> EXPORT_SYMBOL(rb_insert_color);
>
> And use Daniel's __flatten here, like:
>
> void rb_insert_color(struct rb_node *node, struct rb_root *root)
> __flatten
> {
> __rb_insert(node, root, NULL);
> }
> EXPORT_SYMBOL(rb_insert_color);
>
> void rb_insert_augmented(struct rb_node *node, struct rb_root *root,
> const rb_augment_rotate *augment) __flatten
> {
> __rb_insert(node, root, augment);
> }
> EXPORT_SYMBOL(rb_insert_augmented);

Looks good, I'll try that and resubmit.

--
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.


\
 
 \ /
  Last update: 2012-07-28 00:21    [W:0.389 / U:0.200 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site