Binary Search Speeds Up Early Linux Boot: From 268 Seconds Down to 50 Milliseconds

A set of memblock improvements landed today for the Linux 7.4 kernel. The most notable of them is an optimization in mm/memblock.c, home to the kernel's early boot-time physical memory allocator — the one that runs before the full page allocator is brought up.

The change itself is simple. Google engineer Tarun Sahu noticed that memblock_add_range() and memblock_isolate_range() were hunting for candidate memory regions using a linear search. He replaced it with a binary search.

Where it matters

During an ordinary boot the difference is barely perceptible. But under heavy memory fragmentation — for instance when using the Kernel Handover (KHO) mechanism that underpins the Live Update Orchestrator and friends — the system ends up with a vast number of disjoint folios. Scanning through them linearly turns into a painfully slow affair.

The numbers make the case. According to the patch, switching to binary search drops the worst-case complexity to O(N log N) — and O(N) for sequential appends — slashing KHO memory retrieval time from roughly 268 seconds to around 50 milliseconds.

One can only marvel that a linear search survived this long in the kernel. Then again, it only touched the early boot-time allocator, where nobody had particularly noticed the cost.

The optimization was sent out today as part of the memblock pull request for Linux 7.4.

Source: Phoronix