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:
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
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/