Eric Blake <[email protected]> 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
