Messages in this thread | | | Date | Thu, 14 Mar 2019 09:43:43 -0700 | From | Davidlohr Bueso <> | Subject | Re: [LSF/MM TOPIC] Using XArray to manage the VMA |
| |
On Wed, 13 Mar 2019, Matthew Wilcox wrote:
>It's probably worth listing the advantages of the Maple Tree over the >rbtree.
I'm not familiar with maple trees, are they referred to by another name? (is this some sort of B-tree?). Google just shows me real trees.
> > - Shallower tree. A 1000-entry rbtree is 10 levels deep. A 1000-entry > Maple Tree is 5 levels deep (I did a more detailed analysis in an > earlier email thread with Laurent and I can present it if needed).
I'd be interested in reading on that.
> - O(1) prev/next > - Lookups under the RCU lock > >There're some second-order effects too; by using externally allocated >nodes, we avoid disturbing other VMAs when inserting/deleting, and we >avoid bouncing cachelines around (eg the VMA which happens to end up >at the head of the tree is accessed by every lookup in the tree because >it's on the way to every other node).
How would maple trees deal with the augmented vma tree (vma gaps) trick we use to optimize get_unmapped_area?
Thanks, Davidlohr
| |