splay tree and red-black tree for vm_map entry lookups.
dillon at apollo.backplane.com
Wed Jan 19 09:40:46 PST 2005
:I have ported the splay tree used in FreeBSD to look up vm_map entries. 
:And written a reb-black tree that does the same (part of the vm_map_lookup_entry
:taken from NetBSD) .
:I havn't done any benchmarks on the two patches yet, but this should be done to
:see which one is the best to use, and I hope you have some feedback for me.
Lets go with the red-black approach. I will patch it in and start
testing it myself. It looks like NetBSD has done their homework though
and I expect we will be able to commit it by the end of the week.
Splay trees are a great idea in theory, but I really, really dislike
the fact that splay tree lookups write to memory (a lot!) as a side
effect. Memory writes are the achilles heal of modern processors.
splay trees also have a severe disadvantage in that their 'cache' effect
is strictly limited by the algorithm itself to one cache entry
(the head of the tree).
<dillon at xxxxxxxxxxxxx>
More information about the Kernel