The Linux Maple Tree
summary
A new range map called the Maple Tree stores contiguous index ranges that map to one pointer, is RCU-safe, and uses ~128 bytes / 2 cache lines nodes with 64 pivots per node. It targets non‑overlapping ranges only and keeps tree height modest (for 1,000,000 dense entries: radix ~4, maple ~7, rbtree ~18). API mirrors XArray. Designed for VMA use (Firefox example ~1,415 VMAs), it aims to cut average lookup dereferences and memory overhead versus rbtree and radix; implementation is working but still under benchmarking.
AI-written summary · about
chapters (15)
- 0:00Introduction
- 0:22Linked Lists
- 1:03RB Tree
- 4:55Radix Tree
- 11:27The Problem
- 14:43Results
- 19:14Memory Consumption
- 21:14Radix Tree Problems
- 23:44Node Types
- 25:24API
- 26:04Shortterm plans
- 27:50Longerterm plans
- 29:08File descriptor table
- 31:31Hash tables
- 32:53Open questions
related talks
26mThe Maple Tree
35mWhat Lies Beneath - A Deep Dive Into Clojure's Data Structures
31mEnhancing Scalability of the Vmalloc Mechanism in the Linux Kernel
34mHash Maps: more room at the bottom
18mRapid: Region-Based Pointer Disambiguation
15mMapperX: Adaptive Metadata Maintenance for Fast Crash Recovery of DM-Cache Based...
28mFaster Go Maps With Swiss Tables
12mRethinking File Mapping for Persistent Memory