Maple Tree v2 Patches For The Linux Kernel - 13~840% Faster For Malloc Threads Test Case

Written by Michael Larabel in Oracle on 17 August 2021 at 06:52 PM EDT. 8 Comments
Sent out last year was a "request for comments" on "Maple Tree" as a new data structure for the Linux kernel. The latest version of the Maple Tree patches were sent out today with mixed results but for where gains are being made they can be quite significant.

The Maple Tree is a data structure for storing index ranges that map to a single pointer and work well on modern CPUs (modern CPU caches) in an RCU-safe manner. Post-RFC, earlier this year Oracle sent out their Maple Tree patches with promising results and have now been succeeded by the "v2" patches.

With the Maple Tree v2 patches there is a lot of code refactoring, locking changes, RCU fixes, and a variety of other low-level improvements.

As for the performance impact of the Maple Tree patches in their current form, there are sizable wins in some synthetic/micro-benchmark test cases while the real-world performance seems to be flat:
While still using the mmap_sem, the performance seems fairly similar on real-world workloads, while there are variations in micro-benchmarks.

Increase in performance in the following micro-benchmarks in Hmean:
- wis malloc1-threads: Increase of 13% to 840%
- wis page_fault1-threads: Increase of 1% to 14%
- wis brk1-threads: Disregard, this test is invalid.

Decrease in performance in the following micro-benchmarks in Hmean:
- wis brk1-processes: Decrease of 45% due to RCU required

- wis pthread_mutex1-threads: +11% to -3%
- wis signal1-threads: +6% to -12%
- wis malloc1-processes: +9% to -18% (-18 at 2 processes, increases after)
- wis page_fault3-threads: +8% to -22%

These Maple Tree patches out of Oracle in their current form amount to 61 patches that end up adding more than 46.9k lines of new code (and 1.6k deletions) but the vast majority of that new code is library code and in particular Maple Tree test code.
Related News
About The Author
Michael Larabel

Michael Larabel is the principal author of 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 automated benchmarking software. He can be followed via Twitter, LinkedIn, or contacted via

Popular News This Week