On Fri, Oct 19, 2007 at 09:55:25AM +0900, SODA Noriyuki wrote:
> Jason, why do you think libkern version is better?
> I think using <sys/tree.h> version is better, instead.
> See below.

Because it is half the size and using less conditionals in the critical
path.

> > 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.

I brought this argument up because I don't think that sys/tree.h is a
valid argument here. We could easily do the same thing with the libkern
version, but the whole point here was to not repeat the implementation
over and over again. This is at least 2KB for every RB tree.

> > 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.

I think the use of RB_AUGMENT in uvm is a very bad hack. Given that the
sys/tree.h code duplicates code, it doesn't hurt other users 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.
> 
> The RB tree implementation in <sys/tree.h> is same with libkern
> version in this point.

Well, it at least provides an interface to make some use of the wasted
space.

> 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.

Splay trees are also a lot worse for the CPU caches due to the constant
modifications. They also don't over bounded operations. The operations
on splay trees are only cheap on average, individual operations can be
O(n). That makes it not very attractive for a number of important use
cass. Splay trees are only attractive if a high locality of access is
expected and IMO many cases just don't satisfy that property.

Joerg