On Mon, 2012-06-25 at 17:52 -0400, Rik van Riel wrote:

The downside? This makes the rbtree code somewhat more
complex, vs. the brute force walk up the tree the current
augmented rbtree code does. 

Something like that should be in the git history of that code. See
b945d6b2554d55 ("rbtree: Undo augmented trees performance damage and
regression").

I removed that because it adds overhead to the scheduler fast paths, but
if we can all agree to move lib/rbtree.c into inlines in
include/linux/rbtree.h (possibly utilizing Daniel Santos' magic) then we
could do this again.

Anyway, doing the updates in the insertion/deletion might speed up
those, but you still have the regular modifications what don't do
insert/delete to think about.

If you look at your patch 1, __vma_unlink has an adjust_free_gap() right
next to the rb_augment_erase(), vma_adjust() has 3 adjust_free_gap()
calls right next to each other.

All these will do an entire path walk back to the root. I would think we
could save quite a bit of updating by not having them all walk back to
the root. No point in re-computing the top levels if you know the next
update will change them again anyway.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>