The Maple Tree
summary
Maple Tree implements a compact, range-oriented B-tree variant with 256-byte nodes (four cache lines), RCU-safe operations, bulk loading and pre-allocation, and dynamic node types that pick compact representations for sparse or dense data. It replaces a VMA cache while keeping performance, and a real capture of 521 PIDs shows much higher density versus the Radix tree where many nodes are wasteful — e.g. Radix nodes 576 bytes and about 115 single‑PID Radix nodes in that trace. Code is in Linux mm tree / linux-next.
AI-written summary · about
chapters (11)
- 0:00Introduction to Maple Tree
- 1:50Problems with current data structures
- 4:00Maple Tree updates and features
- 7:54PID storage comparison
- 12:18Dynamic node sizes and Judy array
- 16:28Memory efficiency and cache lines
- 17:10Potential use cases
- 19:20Radix vs Maple Tree node example
- 21:12File descriptor and filesystem use
- 22:15Node compression techniques
- 22:38Q&A and future applications
related talks
39mThe Linux Maple Tree
31mEnhancing Scalability of the Vmalloc Mechanism in the Linux Kernel
15mMapperX: Adaptive Metadata Maintenance for Fast Crash Recovery of DM-Cache Based...
19mP2CACHE: Exploring Tiered Memory for In-Kernel File Systems Caching
28mRefining Data Structure Implementations in the Linux Kernel for Improve..
01h 09mNew locks for the old kernel
48mPersistent Memory Usage within Linux Environment
30miommu page table consolidation and iommufd