[PATCH v8 00/70] Introducing the Maple Tree

[Andrew Morton]

On Wed, 27 Apr 2022 14:08:39 +0000 Liam Howlett <liam.howlett at oracle.com> wrote:

> > > 
> > > The tree has a branching factor of 10 for non-leaf nodes and 16 for leaf
> > > nodes.  With the increased branching factor, it is significantly shorter than
> > > the rbtree so it has fewer cache misses.  The removal of the linked list
> > > between subsequent entries also reduces the cache misses and the need to pull
> > > in the previous and next VMA during many tree alterations.
> > 
> > Do we have any quantitative testing results?
> 
> I was waiting for the mmtests sweep to complete before sending them but
> I didn't want to hold up Yu Zhao's testing of the combined tree as it
> has proved useful already. Please don't include the results in the first
> commit as it wouldn't make much sense.  If you intend to put them in a
> commit message, please put them in the patch introducing the maple tree.

I did that.

> The benchmarks are around the same as they have always been.

So it's presently a wash.

That makes "the plan" (below) really critical, otherwise there seems
little point in merging this code at this time?

Please send me many very soothing words about how confident we should
be that the plan will be implemented and that it shall be good?

> > 
> > What's the plan on utilizing this to further reduce mmap_lock contention?
> 
> The plan is to get to the point where we use the maple tree in RCU mode.
> Readers will not block for writers.  A single write operation will be
> allowed at a time.  A reader re-walks if stale data is encountered. VMAs
> would be RCU enabled and this mode would be entered once multiple tasks
> are using the mm_struct.  I can go into more details if you want.

Uh, that's very important information.  It's really the whole point
of the patchset!   I added this to the [0/n] changelog.