Re: [Slightly off topic] A question about R/B trees.

From: Maxim Levitsky
Date: Fri Oct 17 2008 - 18:48:01 EST

Chris Snook wrote:
Maxim Levitsky wrote:
I am working on my small project, and I need a fast container to hold a large sparse array.
Balanced trees seem to fit perfectly.

Balanced trees take O(log n) to perform a great many operations, and traversing a binary tree is a particularly bad case for branch prediction. Hash tables will perform much better, unless you get them horribly wrong.
Let me explain.

I am writing a userspace packet writing application.

One of things I need is to have a cache of the disk.

I need an 'array' that will hold cache of written blocks in ascending order,
I need to be able to insert a block anywhere in the array, and be able to read it
from lowest block to highest.

Hash tables can't be read this way, right?

I could use a linked list, but insertion will be slower.

I decided to implement a red/black tree, and took a look at kernel rb tree for reference,
and I noticed that tree item has no parent pointer, while it seems that it should have it.

I know now that it has parent pointer, but it is mixed with current and parent node colour.
Thus it is assumed that last two bits of this pointer are zero.

Not quite. Read this:

What do you mean?

I have read this article, I haven't yet spotted anything suspicious about parent pointer there yet.

I can see anywhere that this restriction is applied.
I see that structure is "aligned" but that I think only ensures that compiler places it
aligned in static data, does the alignment ensures that it will always place it on aligned address in a structure?
But then, the whole container structure can be misaligned, can't it?

GCC will only misalign the contents of a struct if you explicitly tell it to pack the struct. That's one of those things you only do if you're 100% certain it's the right thing, and you're prepared to accept the consequences if you screw it up.

Why gcc?

Say you allocate a piece of memory using kmalloc, and write there, a structure that contains a r/b tree item.
I agree that gcc will ensure that offset from start of that structure to first byte of the tree item will be aligned.

But what if malloc returned a misaligned pointer?
This will ensure that virtual address of the tree item won't be aligned.
(I know it doesn't, but this isn't a assumption about gcc anymore)

Besides a comment there states that alignment is only for CRIS

I'm not sure this check is still necessary, but CRIS is a rather niche architecture. On most architectures, word-aligning structures boosts performance at negligible memory cost, so compilers do it automatically.

How about a check for misalignment?

The kernel is written in a dialect of C that makes several assumptions about the compiler, among them that the compiler won't screw this up unless you tell it to. Any compiler that has alignment problems with the rbtree code is going to have similar problems in lots of other places too. We don't support those compilers.

Best regards,
Maxim Levitsky
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at
Please read the FAQ at