DragonFly BSD
DragonFly kernel List (threaded) for 2005-01
[Date Prev][Date Next]  [Thread Prev][Thread Next]  [Date Index][Thread Index]

Re: splay tree and red-black tree for vm_map entry lookups.

From: Matthew Dillon <dillon@xxxxxxxxxxxxxxxxxxxx>
Date: Wed, 19 Jan 2005 09:39:38 -0800 (PST)

:I have ported the splay tree used in FreeBSD to look up vm_map entries. [1]
:And written a reb-black tree that does the same (part of the vm_map_lookup_entry
:taken from NetBSD) [2].
: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.
:1: http://leaf.dragonflybsd.org/~eirikn/splay-tree-freebsd-1.patch
:2: http://leaf.dragonflybsd.org/~eirikn/vm_map-rb-tree-netbsd-eirikn.patch
:Eirik Nygaard

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

					Matthew Dillon 

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