Source: Neowin
The upcoming Linux 7.4 kernel could deliver a major performance improvement to one of the operating system's earliest memory-management processes. A proposed optimization to Linux's physical memory allocator reduces the time required for a specific memory retrieval workload from approximately 268 seconds to just 50 milliseconds.
The improvement targets memblock, an early boot-time memory management component that operates before Linux initializes its full page allocator. Google engineer Tarun Sahu identified an inefficient search algorithm that could cause significant delays when handling highly fragmented memory regions.
The proposed changes replace repeated linear searches with binary searches, dramatically reducing the amount of work required to locate memory regions. The patches have been submitted for the Linux 7.4 development cycle, although they should not be confused with a feature already available in a released kernel.
Linux 7.4 Introduces an Optimization for Early Memory Management
Linux relies on several memory management mechanisms to initialize and operate a computer. During the earliest stages of booting, the kernel uses memblock to track available physical memory and manage reserved memory regions.
This process happens before the full page allocator becomes available. Memblock helps the kernel identify which physical memory ranges can be used and which must remain reserved for the kernel, firmware and other system components.
Although this mechanism generally operates efficiently, certain workloads can create significant performance problems. Systems that manage large numbers of fragmented memory regions may force memblock to perform repeated searches, increasing processing time considerably.
The Linux 7.4 proposal addresses this limitation by improving how the allocator locates candidate memory regions in its internal data structures.
How Binary Search Reduces Memory Processing Time
The proposed optimization targets two functions in the Linux kernel's mm/memblock.c file: memblock_add_range() and memblock_isolate_range().
Previously, these functions could search memory regions sequentially from the beginning of a list to find the appropriate location. When a workload contains hundreds of thousands of separate regions, repeatedly scanning those entries becomes increasingly expensive.
The new implementation uses binary search to locate candidate regions more efficiently. Instead of examining entries one by one, binary search repeatedly narrows the search range until it identifies the appropriate position.
According to the patch description, the change improves worst-case algorithmic complexity from a repeated linear-search pattern that can produce (O(N^2)) total work to (O(N \log N)). Sequential appends can achieve (O(N)) complexity.
This change is particularly valuable when Linux must handle a large number of disjoint memory regions during early initialization.
Linux Kernel Memory Retrieval Drops From 268 Seconds to 50ms
The most striking result comes from a Kernel Handover (KHO) memory retrieval workload involving approximately 393,000 pages.
According to Tarun Sahu's patch description, the existing implementation required around 268 seconds to complete the operation. With the binary-search optimization, the reported processing time fell to approximately 50 milliseconds.
Performance metrics
Table showing Performance metrics before opmitization Vs after optimization
| Performance metric | Before optimization | After optimization |
|---|---|---|
| KHO memory retrieval time | 268 seconds | 50 milliseconds |
| Approximate duration | 4 minutes 28 seconds | 0.05 seconds |
| Reported speed improvement | — | About 5,360× faster |
The result represents a reduction of more than 99.98% in processing time for this particular workload.
These measurements concern the reported memory retrieval operation, not the complete Linux boot process. Actual improvements will depend on memory fragmentation, hardware configuration and workload characteristics.
Why the Optimization Matters for Servers and Virtual Machines
The change could be especially useful for systems that handle highly fragmented physical memory during kernel initialization.
Kernel Handover preserves selected memory pages across kernel transitions and can support live-update workflows. When a system must register or retrieve hundreds of thousands of separate memory regions, inefficient searching can introduce substantial delays.
Reducing this overhead could improve initialization performance in affected environments, including infrastructure that relies on Kernel Handover and related live-update orchestration tools.
However, ordinary Linux desktop users should not expect every computer to boot thousands of times faster. The reported improvement applies to a specific memory-intensive scenario, and systems that do not encounter this bottleneck may see little or no noticeable difference.
The broader benefit is that the kernel can handle certain complex memory configurations more efficiently without changing the overall purpose of its early memory allocator.
Linux 7.4 Patch Is Still Under Development
The optimization has been submitted as part of the Linux 7.4 memory-management development cycle. It is therefore important to distinguish the proposed improvement from code that has already shipped in a stable kernel release.
Kernel developers must review changes affecting memory management carefully because errors in early initialization can affect system stability and hardware compatibility.
The patch's performance results provide a strong reason to consider the optimization, but its final implementation and availability depend on the kernel development and review process.
Developers and administrators interested in the technical details can follow the original patch discussion to track revisions and review feedback.
Final Thoughts
Linux 7.4's proposed memblock optimization demonstrates how improving a fundamental algorithm can produce dramatic performance gains. By replacing repeated linear searches with binary search, the patch reportedly cuts Kernel Handover memory retrieval time from approximately 268 seconds to just 50 milliseconds in a workload involving around 393,000 pages.
The improvement could benefit specialized systems that encounter heavy memory fragmentation during early initialization, particularly environments using Kernel Handover. It does not, however, mean that every Linux computer will experience a comparable reduction in total boot time.
If accepted into Linux 7.4, the optimization will provide a more efficient way to handle demanding early memory-management workloads and remove a significant bottleneck in the affected scenarios.