Maple Tree "RFC" Patches Sent Out as New Data Structure to Help with Linux Performance
MrPlow writes:
Submitted via IRC for TheMightyBuzzard
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[er] 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%.
Source: https://www.phoronix.com/scan.php?page=news_item&px=Maple-Tree-Linux-RFC
[*] RCU: Read-Copy-Update.
Read more of this story at SoylentNews.