On Fri, Jul 20, 2012 at 05:31:01AM -0700, Michel Lespinasse wrote: > Patch 5 speeds up the augmented rbtree erase. Here again we use a tree > rotation callback during rebalancing; however we also have to propagate > the augmented node information above nodes being erased and/or stitched, > and I haven't found a nice enough way to do that. So for now I am proposing > the simple-stupid way of propagating all the way to the root. More on > this later. So, I looked at it again and finally figured out a decent way to avoid unnecessary propagation here. Going to resend patches 5/6 as replies to their original postings. > - The prio tree of all VMAs mapping a given file (struct address_space) > could be switched to an augmented rbtree based interval tree (thus removing > the prio tree library in favor of augmented rbtrees) I actually have a prototype for that already. The augmented rbtree based implementation is slightly faster than prio tree on insert/erase, and considerably faster on lookups. However, this is with a synthetic test exercising prio and rbtrees directly, not with a realistic workload going through the MM layers. Do we know of situations where prio tree performance is currently a concern ? > As they stand, patches 3-6 don't seem to make a difference for basic rbtree > support, and they improve my augmented rbtree insertion/erase benchmark > by a factor of ~2.1 to ~2.3 depending on test machines. After rewriting patches 5-6 as discussed above, augmented rbtrees are now ~2.5 - ~2.7 times faster than before this patch series. -- Michel "Walken" Lespinasse A program is never fully debugged until the last user dies. -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@xxxxxxxxx. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"dont@xxxxxxxxx";> email@xxxxxxxxx </a>