Re: potential rbtree optimizations

[Ben Pfaff]

Eric Blake <address@hidden> writes:

> Bruno, I noticed this thread on the gcc lists:
>
> http://gcc.gnu.org/ml/gcc-patches/2009-05/msg00419.html
>
> with some interesting ideas for speeding up iteration of an RB tree, either 
> at 
> the expense of two additional pointers (fastest speed, good cache usage, but 
> large memory penalty), or with the addition of two bits (crammed in the 
> padding 
> adjacent to the red-black color indicator) which control whether existing 
> pointers are tree relations vs. threaded links (no change in memory, faster 
> iteration than current implementation, but slower rebalancing).

I don't know whether everyone is aware of my paper on binary
search tree performance, so I'll point to it in case it helps
understanding the performance trade-offs with various link
structures:
        http://benpfaff.org/papers/libavl.pdf
-- 
Ben Pfaff 
http://benpfaff.org