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

[Maxim Levitsky <maximlevitsky@gmail.com>]

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