Examining the VM splay tree effectiveness

[Ivan Voras]

On 10/01/10 20:28, Ed Schouten wrote:
> Andre,
> 
> * Andre Oppermann <andre at freebsd.org> wrote:
>> A splay tree is an interesting binary search tree with insertion,
>> lookup and removal performed in O(log n) *amortized* time.  With
>> the *amortized* time being the crucial difference to other binary trees.
>> On every access *including* lookup it rotates the tree to make the
>> just found element the new root node.  For all gory details see:
>>  http://en.wikipedia.org/wiki/Splay_tree
> 
> Even though a red-black tree is quite good since it guarantees a $2 \log
> n$ upperbound, the problem is that it's quite computationally intensive.
> 
> Maybe it would be worth looking at other types of balanced trees? For
> example, another type of tree which has only $O(\log n)$ amortized
> insertion/removal/lookup time, but could already be a lot better in
> practice, is a Treap.

How many elements are held in vm_map trees? From the source it looks
like one tree with all pages in the system and then one per-process?

Trees have very varied real-time characteristics, e.g.:

http://attractivechaos.awardspace.com/udb.html
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83.6795&rep=rep1&type=pdf