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

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

[Maxim Levitsky]

Hi,

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.

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.

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?

Besides a comment there states that alignment is only for CRIS

How about a check for misalignment?

Best regards,
	Maxim Levitsky

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

[Chris Snook]

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

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

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

[Andi Kleen]

Chris Snook <csnook@redhat.com> writes:

> 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.

That seems like a unfair generalization.

The problem with hash tables is that if they're big enough
or if the rest of the workload is memory intensive
each hit will be a cache miss. And you can do a lot of branch
mispredicts in the time of a single cache miss.

In general trees can be much better for cache usage, although
it's generally better to use some tree that has nodes near 
the cache line size. Binary trees like RB are too small for that.

The other advantage of trees is that they scale naturally.
For hash tables you either have it being sized for the worst
case (usually wasting a lot of memory[1] and making the cache miss
problem worse) or you need to do dynamic rehashing which 
is complex and difficult to get right especially in multi threaded
situations.

That is why the trend in Linux at least is to move away from
hash tables.

[1] Just take a look at how much memory that various hash 
tables in Linux use: dmesg | grep hash

> 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.

At least upto 4 bytes or so it's generally a safe assumption
that objects will be naturally aligned. Also except for tree 
root the objects are typically allocated with malloc() (or
equivalent kmalloc) anyways and malloc()s guarantee
worst case alignment.


-Andi
-- 
ak@linux.intel.com

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

[Pekka Enberg]

Hi Andi,

On Sat, Oct 18, 2008 at 10:53 AM, Andi Kleen <andi@firstfloor.org> wrote:
> The problem with hash tables is that if they're big enough
> or if the rest of the workload is memory intensive
> each hit will be a cache miss. And you can do a lot of branch
> mispredicts in the time of a single cache miss.
>
> In general trees can be much better for cache usage, although
> it's generally better to use some tree that has nodes near
> the cache line size. Binary trees like RB are too small for that.

Right, but even for binary trees, you can get some of the benefits by
packing all the nodes in a slab cache of their own. That way many of
the neighboring nodes will share the same cache line if you're
allocating memory for the nodes in a top-down order. Of course, you
lose the benefits if the tree is updated a lot because you're back to
worst case allocation again.

                       Pekka

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

[Chris Friesen]

Maxim Levitsky wrote:

> 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)

malloc() can't return a misaligned pointer.  From the spec:  "The 
pointer returned if the allocation succeeds shall be suitably aligned so 
that it may be assigned to a pointer to any type of object..."

Chris

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

[Maxim Levitsky]

Pekka Enberg wrote:
> Hi Andi,
> 
> On Sat, Oct 18, 2008 at 10:53 AM, Andi Kleen <andi@firstfloor.org> wrote:
>> The problem with hash tables is that if they're big enough
>> or if the rest of the workload is memory intensive
>> each hit will be a cache miss. And you can do a lot of branch
>> mispredicts in the time of a single cache miss.
>>
>> In general trees can be much better for cache usage, although
>> it's generally better to use some tree that has nodes near
>> the cache line size. Binary trees like RB are too small for that.
> 
> Right, but even for binary trees, you can get some of the benefits by
> packing all the nodes in a slab cache of their own. That way many of
> the neighboring nodes will share the same cache line if you're
> allocating memory for the nodes in a top-down order. Of course, you
> lose the benefits if the tree is updated a lot because you're back to
> worst case allocation again.
> 
>                        Pekka

Thank you very much.

Best regards,
	Maxim Levitsky