Refining Data Structure Implementations in the Linux Kernel for Improve..- Jim Huang & Kuan-Wei Chiu

### Overview In this talk, Kuan-Wei Chiu (introduced as Kel, a graduate student at National Yang Ming Chiao Tung University) presents research co-authored with Jim Huang on optimizing fundamental data structures and algorithms in the Linux kernel's core library code (`lib/`). The presentation addresses algorithmic inefficiencies in the kernel's min-heap and heapsort implementations, while highlighting broader systemic issues across kernel library code, including duplicate implementations, sparse test coverage, and benchmark reproducibility challenges.

### Key Topics - **Bottom-Up Min-Heap Optimization**: Replacing the textbook top-down heapify algorithm with a bottom-up variant to cut comparison counts roughly in half. - **Heapsort Optimization**: Enhancing the kernel's in-place heapsort for equal elements and utilizing a double-pop variation for general random data to cut swap operations by approximately 50%. - **Kernel Library Code Observations**: Addressing why `lib/` receives less developer attention compared to vendor-specific drivers, identifying code duplication across subsystems (e.g., perf, bcache, bcachefs), and demonstrating insufficient test suites.

### Technical Details - **Min-Heap Sift-Down Optimization**: In the textbook heapify approach, each level compares the current node with both children (requiring two comparisons per level, totaling roughly 2 * log N). In the Linux kernel heap API, swap and compare operations rely on function pointers and can operate on expensive data types like strings. The bottom-up variant instead compares only the left and right children on the way down to find the sift-down path (one comparison per level), then sifts up from the bottom with constant secondary comparisons against the root node. This eliminates approximately 50% of comparisons for large heaps while maintaining the same swap count. - **Heapsort Equal Elements Optimization**: The kernel uses heapsort rather than quicksort or mergesort because it guarantees O(N log N) worst-case time without requiring extra O(N) memory allocation (crucial for embedded and real-time Linux). In the previous implementation, when encountering identical child values during sift-down path searches, the algorithm defaulted to the left child. Because the right subtree height can be one less than the left subtree, modifying the algorithm to select the right child when children are equal saves comparisons and swaps. This patch was accepted by kernel maintainer Andrew Morton. - **Double-Pop Heapsort Variant**: For general random inputs (evaluated using `get_random_u32()`), the single-pop method extracts one element per iteration. The optimized double-pop approach determines the second-largest element (one of the root's children) using an extra comparison, pops both largest elements at once, and initiates heapify on a subtree whose height is reduced by one. Over 0.5 * N iterations, this saves approximately 0.5 * N swaps while keeping overall comparison counts virtually unchanged. This patch was scheduled for Linux kernel version 6.9. - **Library Testing and Duplication Deficits**: The speaker points out that developers primarily focus on driver subsystems impacting their employers' hardware. As a result, critical library routines lack robust testing. For example, integer square root had no tests despite wide usage, and heapsort relied on a single 1,000-element test array that cannot detect worst-case regressions. Furthermore, duplicate custom min-heap implementations using complex macros exist across `perf`, `dm-vdo`, `bcache`, and `bcachefs` instead of leveraging unified library code.

### Takeaways Optimizing generic kernel library code provides widespread benefits across more than 1,000 drivers and subsystems calling sorting and heap APIs. By refining sift paths and extraction patterns, significant execution overhead from costly comparison and swap callbacks can be eliminated. However, sustaining these performance improvements requires kernel developers to consolidate redundant subsystem-specific implementations and establish comprehensive test suites covering varied input distributions, edge cases, and reproducible benchmarks.