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

From: Chris Snook
Date: Fri Oct 17 2008 - 18:15:28 EST


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.

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:

http://lwn.net/Articles/184495/

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.

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.

-- Chris
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/