Phoronix reported on Oct. 24 that a memblock optimization had been submitted in a pull request for Linux 7.4. The proposed change uses binary search for early-boot memory-range lookups. In one Kernel Handover (KHO) case involving about 393,000 pages, patch author Tarun Sahu reported retrieval time falling from about 268 seconds to about 50 milliseconds.
What memblock does during early Linux boot
memblock manages physical memory early in the boot process, before the full page allocator starts. The proposed change targets two functions in mm/memblock.c: memblock_add_range() and memblock_isolate_range().
How the proposed search works
The patch replaces repeated scans from the start of a region list with a lower-bound binary search. The search locates the first region whose end extends beyond the candidate range’s starting address. Binary search narrows the set of regions to check instead of stepping through them one by one.
Sahu describes repeated linear scans under heavy fragmentation as O(N²). The proposed search has O(N log N) worst-case complexity and O(N) complexity for sequential appends.
What the KHO timing measures
Sahu’s reported comparison is for one KHO memory-retrieval workload, with about 393,000 pages:
| Measure and scenario | Before the change | After the change |
| KHO memory retrieval, about 393,000 pages | About 268 seconds | About 50 milliseconds |
The figures describe the retrieval operation in that workload. They do not describe a complete system boot measurement.
A separate workload report
Dongli Zhang described tests on a one-node, 32-CPU system with transparent huge pages (THP) set to “never” and 4K pages. He reported that delays in his workload were no longer noticeable across several test rounds after applying the patch.
Zhang’s boot logs give another measure: the interval between the mem-auto-init and SLUB markers was 38.355755 seconds before the patch and 0.264273 seconds afterward. These values are the marker-to-marker interval in Zhang’s workload.
Sahu said linear scans can still be efficient for small lists, while the proposed optimization targets very large, fragmented lists. He described the affected code as part of boot-time initialization, with memory hotplug as an exception.
