Date: Thu, 30 Sep 2010 15:50:04 -0700 From: Freddie Cash <fjwcash@gmail.com> To: freebsd-current@freebsd.org Subject: Re: Examining the VM splay tree effectiveness Message-ID: <AANLkTimz6ATKYPKyD3ZsYtfrEWc=km55DOd3iu=pM-6m@mail.gmail.com> In-Reply-To: <4CA509FE.30303@freebsd.org> References: <4CA4BCD2.4070303@freebsd.org> <20100930172439.GA34369@freebsd.org> <4CA4CCF8.1050300@freebsd.org> <20100930174900.GA37733@freebsd.org> <20100930180417.GA39381@freebsd.org> <4CA504AD.8000102@freebsd.org> <4CA509FE.30303@freebsd.org>
next in thread | previous in thread | raw e-mail | index | archive | help
For the curious, DragonflyBSD went through this back in 2005. All the gory details are in the thread with Subject: "splay tree and red-black tree for vm_map entry lookups" [1] While things are most likely different now between the FreeBSD VM and the DragonflyBSD VM, it may be worthwhile checking out what they did, and why. They considered the FreeBSD splay-tree and compared it to red-black tree, and went with red-black. There's mention in that thread that NetBSD uses red-black trees. No idea if this is still correct. [1] http://leaf.dragonflybsd.org/mailarchive/kernel/2005-01/msg00121.html -- Freddie Cash fjwcash@gmail.com
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?AANLkTimz6ATKYPKyD3ZsYtfrEWc=km55DOd3iu=pM-6m>