Examining the VM splay tree effectiveness

[Ivan Voras]

On 09/30/10 18:37, Andre Oppermann wrote:

> Both the vmmap and page table make use of splay trees to manage the
> entries and to speed up lookups compared to long to traverse linked
> lists or more memory expensive hash tables.  Some structures though
> do have an additional linked list to simplify ordered traversals.

The property of splay tree requiring *writes* for nearly every read
really is a thorn in the eye for SMP. It seems to me that even if the
immediate benefits from converting to something else are not directly
observable, it will still be worth doing it.

It's a shame that RCU is still a patent minefield :/

http://mirror.leaseweb.com/kernel/people/npiggin/patches/lockless/2.6.16-rc5/radix-intro.pdf

Slightly off-topic: a scare-mongering topic on Slashdot:
http://hardware.slashdot.org/story/10/09/30/1528229/Linux-May-Need-a-Rewrite-Beyond-48-Cores