I don't remember the reference but I read a comprehensive comparison
between various indexing methods about a year ago and the splay tree
did considerably better than a RB-tree. The RB-tree actually did
fairly poorly.
Any binary tree-like structure makes fairly poor use of cpu caches.
Splay trees work somewhat better as long as there is some locality
of reference in the lookups, since the node being looked up is moved
to the root. It isn't a bad trade-off.
On the negative side all binary-tree-like structures tend to be
difficult to MP-lock in a fine-grained manner (not that very many
structures are locked at that fine a grain anyway, but it's a data
point). Splay-trees are impossible to lock at a fine-grain due to
the massive modifications made on any search and the movement
of the root, and there are MP access issues too.
--
What turned out to be the best indexing mechanism was a chained
hash table whos hoppers were small linear arrays instead of single
elements. So instead of pointer-chaining each element you have a small
for() loop for 4-8 elements before you chain. The structure being
indexed would NOT be integrated into the index directly, the index
would point at the final structure from the hopper.
For our purposes such linear arrays would contain a pointer and
an indexing value in as small an element as possible (8-16 bytes),
the idea being that you make the absolute best use of your cache line
and L1 cache / memory burst. One random access (initial hash index),
then linear accesses using a small indexing element, then one final
random access to get to the result structure and validate that
it's the one desired (at that point we'd be 99.9% sure that we have
the right structure because we have already compared the index value
stored in the hopper). As a plus the initial hash index also makes
MP locking the base of the chains easier.
I don't use arrayized chained hash tables in DFly either, but only
because it's stayed fairly low on the priority list. cpu isn't really
a major issue on systems these days. I/O is the bigger problem.
RB-Trees are simply extremely convenient from the programming side,
which is why we still use them.
I was surprised that splay trees did so well vs RB-trees, I never liked
the memory writes splay trees do let alone the impossibility of
fine-grained locking. Originally I thought the writes would make
performance worse, but they actually don't. Still, if I were to change
any topologies now I would definitely go with the chained-hash /
small-linear-array / chain / small-linear-array / chain mechanic. It
seems to be the clear winner.
-Matt
Matthew Dillon
<dil...@backplane.com>
_______________________________________________
freebsd-current@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-current
To unsubscribe, send any mail to "freebsd-current-unsubscr...@freebsd.org"
