Oracle Continues Working On The Maple Tree For The Linux Kernel
Written by Michael Larabel in Oracle on 9 May 2021 at 09:25 AM EDT. 1 Comment
ORACLE --
Oracle engineers have continued working on the "Maple Tree" data structure for the Linux kernel as an RCU-safe, range-based B-tree designed to make efficient use of modern processor caches.

Sent out last year was the RFC patch series of Maple Tree for the Linux kernel to introduce this new data structure and make initial use of it. Sent out last week was the latest 94 patches in a post-RFC state for introducing this data structure.
The maple tree is 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, where three data structures are replaced by the maple tree: the augmented rbtree, the vma cache, and the linked list of VMAs in the mm_struct. The long term goal is to reduce or remove the mmap_sem contention.

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.


At this point the performance of using Maple Tree is showing similar real-world performance to the existing code but some micro-benchmarks are seeing better performance out of it. Below is a video back from the Open-Source Summit North America 2019 about the Maple Tree:


The latest 94 patches working on Maple Tree are out for review and even with a week passing since sending them out there hasn't been much comment yet on this Oracle undertaking for the Linux kernel.
Related News
About The Author
Author picture

Michael Larabel is the principal author of Phoronix.com and founded the site in 2004 with a focus on enriching the Linux hardware experience. Michael has written more than 20,000 articles covering the state of Linux hardware support, Linux performance, graphics drivers, and other topics. Michael is also the lead developer of the Phoronix Test Suite, Phoromatic, and OpenBenchmarking.org automated benchmarking software. He can be followed via Twitter or contacted via MichaelLarabel.com.

Popular News This Week