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

[Maxim Levitsky]

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:
>
> http://lwn.net/Articles/184495/

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  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/