[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: potential rbtree optimizations

From: Ben Pfaff
Subject: Re: potential rbtree optimizations
Date: Fri, 08 May 2009 15:27:51 -0700
User-agent: Gnus/5.11 (Gnus v5.11) Emacs/22.2 (gnu/linux)

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
Ben Pfaff 

reply via email to

[Prev in Thread] Current Thread [Next in Thread]