Refining Data Structure Implementations in the Linux Kernel for Improve..
summary
Introduces concrete kernel patches: a bottom-up sift-down heap cuts comparisons by about 50% on large heaps by finding a leaf path then sifting up, keeping swap count similar; a double-pop heap variant pops two elements per iteration, roughly halving swaps while keeping comparisons near the same and is slated to be included in Linux 6.9; heap sort tweaks reduce work on many-equal keys and random data, and experiments with u32-generated arrays show the claimed savings; library code lacks comprehensive tests, causing some benchmarks to be hard to reproduce.
AI-written summary · about
chapters (8)
- 0:00Introduction
- 0:54Data Structure
- 4:05Mean Heap Optimization
- 7:18Sort Optimization
- 11:59Double Pop Optimization
- 18:02Linux Kernel Library Code
- 20:45Data Structure Implementations
- 22:38Conclusion
related talks
40mTowards a Tool for Access-Affinity Based Structure Reordering in the Linux Kernel
31mEnhancing Scalability of the Vmalloc Mechanism in the Linux Kernel
21mPreview: Operating Systems
51mReducing the Kernel's Slab Allocators: Progress Report
34mLCG Lightning Talks
43mLinux Kernel Panel
42mThe Kernel Report
01h 02mProfiling with Heaptrack and Hotspot on Embedded Linux