On Fri, May 20, 2011 at 11:23:47AM +0200, Mike Belopuhov wrote: > On Fri, May 20, 2011 at 4:04 AM, Ariane van der Steldt <ari...@stack.nl> > wrote: > > AVL trees have a difference of max 1 between the longest and shortest > > path to a leaf, whereas RB-trees have at max the longest path be double > > the length of the shortest path. > > I.e. work case lookups require traversal of > > ? ?ln(size)/ln(2) elements for AVL trees, > > 2 * ln(size)/ln(2) elements for RB trees. > > > > However, RB trees are slightly more efficient with insertion/removal. > > > > The better balancing of AVL trees can make a big difference in lookup > > time compared to RB trees, for trees containing millions of items. > > > >> how are you supposed to choose between them? > > > > Basically it's a trade off. Is lookup more important, or insert/remove? > > And ofcourse, if you still don't know, just take what strikes your > > fancy. :D > > > > i know about the difference of lookup and insert/remove speed, but > is there a significant difference in practice (in openbsd use cases)?
I suspect that the PF state table is mostly lookups, therefor AVL would improve performance there. That said without having looked at the code though. For UVMs allocators, the case is harder to pin, since they use a lot of lookup and traversal (where AVL may benefit) while also requiring a lot of modifications (where RB may be better). The choice is a lot harder to pin down. This is without taking cache coherency on multiple CPUs into account, which may change the picture again (a write/rotate would lead to cache invalidation on all other cpus). > > But I'm mostly interested because I tend to use trees left, right and > > center and those macros lead to code bloat. If I can use a tree without > > macros, I'm happy. > > so maybe it makes sense to have a non macro implementation in libkern > and use it in uvm or whenever needed? Or just in sys/kern. -- Ariane
