Subject: Re: libkern's rb tree
To: Jason Thorpe <email@example.com>
From: SODA Noriyuki <firstname.lastname@example.org>
Date: 10/19/2007 09:55:25
> On Thu, Oct 18, 2007 at 01:58:24PM -0700, Jason Thorpe wrote:
>> Can you please adapt this to use the rb tree code in libkern (proplib also
>> uses a copy of this) and test for any performance differences / code size
Jason, why do you think libkern version is better?
I think using <sys/tree.h> version is better, instead.
>>>>> On Thu, 18 Oct 2007 23:31:51 +0200,
Joerg Sonnenberger <email@example.com> said:
> The first concern is that the code doesn't allow "type safe" usage. I
<sys/tree.h> version is type safe, because it's using macros.
> The second concern is the use of the sentinel nodes. Having done the rb
> tree myself I'm sure that they save very little actual code and might
> have even increased the size.
I agree. <sys/tree.h> version is better in this point too.
> The third concern is generality. The only use of sys/tree.h in the
> kernel is uvm right now and that does some nasty things with
> RB_AUGMENT. We can't replace that with the current rb_moved. If we
> want to have a single copy in the tree, we need a callback whenever
> a child of a node changes. That adds a conditional to a lot of
> branches though.
If we use <sys/tree.h> version, this is not a problem at all.
> The last concern is about memory usage. If doing all the above, only two
> bits of storage are needed for each node (color and position). I think
> that should be merged into the parent pointer. Based on my own tests,
> this is approximately free on i386 as the bitfield access is as bad as
> modifying the parent pointer and the parent pointer needs to be changed
> in most cases already.
The RB tree implementation in <sys/tree.h> is same with libkern
version in this point.
But if the memory usage is most important, we can use splay tree
instead of redblack tree with <sys/tree.h>, because the splay tree
version uses same interface with only half size of node memory.
The libkern version doesn't have splay tree implementation.