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 
> differences?

I am very well aware of the libkern code. I've been discussing the
future of that with the author, because I don't agree with some of the
design decisions and how they affect the use. I would like to keep that
discussion separate though.

The first concern is that the code doesn't allow "type safe" usage. I
have a set of wrapping code that avoids this by creating inline glue
for a very small cost. IMO this is necessary feature before actual
wide-spread use.

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.

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.

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.

Joerg