[Top][All Lists]

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

potential rbtree optimizations

From: Eric Blake
Subject: potential rbtree optimizations
Date: Fri, 8 May 2009 21:54:00 +0000 (UTC)
User-agent: Loom/3.14 (http://gmane.org/)

Bruno, I noticed this thread on the gcc lists:


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

Would it be worth adding an additional gl_list RB-tree implementation that uses 
threading, such that it would be easy to for clients to experiment between 
implementations and determine whether they care more about memory and insertion 
speed, vs. better iteration speed?

Eric Blake

reply via email to

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