On 09/30/10 20:01, Alan Cox wrote: > On Thu, Sep 30, 2010 at 12:37 PM, Andre Oppermann <[email protected]> wrote: > >> On 30.09.2010 18:37, Andre Oppermann wrote: >> >>> Just for the kick of it I decided to take a closer look at the use of >>> splay trees (inherited from Mach if I read the history correctly) in >>> the FreeBSD VM system suspecting an interesting journey. >>> >> >> Correcting myself regarding the history: The splay tree for vmmap was >> done about 8 years ago by alc@ to replace a simple linked list and was >> a huge improvement. The change in vmpage from a hash to the same splay >> tree as in vmmap was committed by dillon@ about 7.5 years ago with some >> involvement of a...@. >> ss
> Yes, and there is a substantial difference in the degree of locality of > access to these different structures, and thus the effectiveness of a splay > tree. When I did the last round of changes to the locking on the vm map, I > made some measurements of the splay tree's performance on a JVM running a > moderately large bioinformatics application. The upshot was that the > average number of map entries visited on an access to the vm map's splay > tree was less than the expected depth of a node in a perfectly balanced > tree. Sorry, I'm not sure how to parse that - are you saying that the splaying helped, making the number of nodes visited during tree search lesser than the average node depth in a balanced tree? Even if so, wouldn't the excessive bandwidth lost in the splaying ops (and worse - write bandwidth) make it unsuitable today? _______________________________________________ [email protected] mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-hackers To unsubscribe, send any mail to "[email protected]"
