LWN: Comments on "Trees II: red-black trees"

Trees II: red-black trees

jlayton — Tue, 26 Oct 2010 18:18:20 +0000

This is an older article, but it seems there are some mistakes. It says:

void rb_link_node(struct rb_node *new_node,
struct rb_node *parent,
struct rb_node **link);

...which is all rb_node pointers (or pointers to pointers). But it declares this function:

void my_rb_insert(struct rb_root *root, struct my_stuff *new)

...which has "new" as a struct my_stuff pointer. That function then calls:

rb_link_node(new, parent, link);
rb_insert_color(new, root);

...shouldn't "new" in latter two calls be a pointer to the embedded rb_node?

Trees II: red-black trees

acolin — Sat, 07 Nov 2009 23:55:32 +0000

Thank you for the article!

Note that in my_rb_insert parent must be initialized, otherwise it doesn't work. This can also be seen in example in rbtree.h. So,
> struct rb_node **link = &root->rb_node, *parent;
should be
> struct rb_node **link = &root->rb_node, *parent = NULL;

Trees II: red-black trees

bigt23 — Fri, 30 May 2008 06:20:10 +0000

nice article! thanks!

Request clue-bat

jengelh — Wed, 11 Apr 2007 19:33:10 +0000

Bad form or not, it is also allowed in C++.

Binary trees considered harmful

i3839 — Thu, 06 Jul 2006 16:49:27 +0000

Well, who knows, maybe it has something to do with this:

$ size  Judy-1.0.3/src/obj/.libs/libJudy.so.1.0.3 
   text    data     bss     dec     hex filename
 114515     760     160  115435   1c2eb Judy-1.0.3/src/obj/.libs/libJudy.so.1.0.3
$ size linux/lib/*tree*.o
   text    data     bss     dec     hex filename
   1823       0     128    1951     79f linux/lib/prio_tree.o
   2934      28      36    2998     bb6 linux/lib/radix-tree.o
   1544       0       0    1544     608 linux/lib/rbtree.o

For something which is avoiding cache misses as much as possible it seems a bit strange to be so bloated that the code to avoid all those cache misses causes so awfully lot cache misses itself. Of course, this isn't something you'll see when benchmarking the code...

Furthermore, whatever memory saving might be achieved by using Judy arrays, it has a long to go way before it made up for that 100K extra usage.

And to rub it in, hashes are almost as good as Judy arrays but are much simpler and smaller to implement. Only icky thing is their (re-)size problem, but that's less icky than a 100K footprint. Good b-tree (not a binary tree) implementations are also not significant worse.

I'm not trying to prove that Judy arrays are bad, they have their usages, but I do think that the kernel isn't the right place for them.

Trees II: red-black trees

wingo — Mon, 03 Jul 2006 08:41:04 +0000

Thanks, nice article.

Binary trees considered harmful

nix — Fri, 30 Jun 2006 15:56:09 +0000

Yeah. It's a shame that the accessor macros and the code are so horribly named/unreadable. It's almost obfuscated-yet-heavily-commented...

Binary trees considered harmful

cventers — Thu, 29 Jun 2006 17:21:47 +0000

True, but so is RCU. I wonder if HP would give an explicit license to GPL
code (since they released the Judy library on Sourceforge as LGPL, along
with some "confidential" internal paper about Judy).

Request clue-bat

ncm — Thu, 29 Jun 2006 17:16:53 +0000

No, it's just defining two variables, and leaving one uninitialized. In C++ code this would be bad form, but in C89 you have to define variables at the top of the block, often before you're ready to initialize them to anything useful. The kernel isn't coded in C89, though; it requires Gcc. With recent releases of Gcc, if run with C99 support turned on, variables can be defined in the middle of a block. It's really only inertia supporting this unfortunate practice.

Binary trees considered harmful

nix — Thu, 29 Jun 2006 16:23:59 +0000

What a baroque and lovely data structure. Alas it seems it's tied up in software patents...

Request clue-bat

smitty_one_each — Thu, 29 Jun 2006 11:58:36 +0000

>struct rb_node **link = &root->rb_node, *parent;

What is the effect of the comma? At first blush, we appear to be trying to assign two values to **link.

Binary trees considered harmful

ncm — Thu, 29 Jun 2006 09:04:44 +0000

The author/designer of Judy Trees remarks that, having measured them in comparison with other methods, "It is truly remarkable to me how much research has been done on binary trees and [that they are] still being taught." Red-black trees are quaint, at best, nowadays. Replacing them in the kernel with a more cache-aware (or, better, cache-oblivious) alternative ought to be an easy way to speed up affected kernel operations, except that it appears it would require rewriting zillions of search and insert functions. It seems unfortunate that the design of the kernel rbtrees is so intrusive, but there may have been no choice, in C.

Trees II: red-black trees

opennw — Thu, 29 Jun 2006 08:41:57 +0000

Wonderful article, thank you. I think the "root-*gt;rb_node;" in my_rb_search() should be "root->rb_node". (I suspect the "*" should be a "&").

Trees II: red-black trees

alonz — Thu, 29 Jun 2006 06:36:00 +0000

I believe there is a small error in the insertion code: the line

    struct my_stuff *stuff = rb_entry(parent, struct my_stuff, parent);

should have been written as

    struct my_stuff *stuff = rb_entry(parent, struct my_stuff, node);