Re: splay tree and red-black tree for vm_map entry lookups.
On Wed, Jan 19, 2005 at 09:39:38AM -0800, Matthew Dillon wrote:
> :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.
I did add some code that used the hint, but for some reason it made my computer
go crazy at boot, and the login just went dead, could enter a login name but
'login:' just poped back out. I am having some trouble seeing why this could go
so bad. The hint code is in this patch:
http://leaf.dragonflybsd.org/~eirikn/vm_map-rb-tree-netbsd-eirikn-hint.patch
--
Eirik Nygaard
討論串 (同標題文章)
完整討論串 (本文為第 3 之 11 篇)：