Maple Tree "RFC" Patches Sent Out As New Data Structure To Help With Linux Performance

For over the past year there has been work on the new "Maple Tree" data structure led by Oracle for the Linux kernel and this week marked the patches being sent out in "request for comments" (RFC) form with the aim still on helping the kernel performance.

Maple Tree amounts to a data structure that works well on modern CPUs and in an RCU-safe manner for storing index ranges that map to a single pointer. Oracle's Liam Howlett sums up the Maple Tree data structure as "an RCU-safe range based B-tree designed to use modern processor cache efficiently. There are a number of places in the kernel that a non-overlapping range-based tree would be beneficial, especially one with a simple interface. The first user that is covered in this patch set is the vm_area_struct rbtree in the mm_struct with the long term goal of reducing the contention of the mmap_sem. 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 short than the rbtree so it has fewer cache misses."

This code is still a work-in-progress with some known regressions and not yet supporting 32-bit or MMU-less kernel builds. But even as it stands now there are scaling benchmarks where the Maple Tree usage can help by 1~17% or in the malloc1-threads micro-benchmark where it can help the performance by 29~71%.

So performance is looking good so far for Maple Tree and as for the plan overall, Liam explained, "The long term goal of the maple tree is to reduce mmap_sem contention by removing users that cause contention one by one. This may lead to the lock being completely removed at some point. The secondary goals is to provide the kernel with a fast RCU tree with a simple interface and to clean up the mm code by removing the integration of the tree within the code and structures themselves."

Details on the Maple Tree implementation in current form can be seen from the RFC patch series.

From LPC2019 is also this presentation (PDF) by Howlett going over the state of Maple Tree at that initial point. There is also a Maple Tree presentation from last year by Matthew Wilcox that is embedded below from OSS NA 19.

As we hit the end of 2020, Maple Tree is an RFC state while hopefully in 2021 it will advance enough and ideally pan out with all its performance objectives to make it into the mainline Linux kernel.