Re:Crit-bit trees
by eloff on Tuesday December 17, 2013 @10:06AM
(#6921447)
That's the problem I see, it's memory efficient, but lookups will cost thousands of cycles for modestly sized trees. A hash table on the other hand can do lookups in a couple hundred cycles (cold cache for both.)
[ Parent
| on HN ]
Re:Crit-bit trees
by sprachspiel on Tuesday December 17, 2013 @12:32PM
(#6922366)
But cold caches are an unrealistic assumption. The top-most levels of a tree will always be in cache, unless you almost never access them -- in which case there's no problem either. Additionally, a radix tree is ordered, whereas a hash table is not.
Yes, that's correct. However, that's still over a thousand cycles for a tree of depth 5 below the cached part. That's a modestly sized tree (or several smaller trees.) Don't forget lot's of things compete for cache, it's usually safer to assume a cold cache unless you know your data structure is very high traffic.