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

[Andi Kleen <andi@firstfloor.org>]

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