Linux's Early Boot-Time Physical Memory Allocator Sees Big Speed-Up: ~268s To ~50ms

Sent out today for the Linux 7.4 kernel were a set of memblock improvements. Most notable is a performance optimization within mm/memblock.c that implements the kernel's early boot-time physical memory allocator that is used prior to the bring-up of the full page allocator. The performance improvement is using a binary search within the memblock_add_range() and memblock_isolate_range() functions. Google engineer Tarun Sahu spotted that the mm/memblock.c code was using a linear search for finding candidate regions rather than a binary search. When under heavy fragmentation like making use of the Kernel Handover "KHO" functionality (that in turn is used by the Live Update Orchestrator and friends) with tons of disjoint folios, that scanning process with a linear search ends up taking a very significant amount of time. The patch notes that using a binary search for worse-case complexity ends up cutting the KHO memory retriveal time from around 238 seconds to around 50 milliseconds! "Using binary search reduces the worst-case complexity to O(N log N) (and O(N) for sequential appends), cutting KHO memory retrieval time from ~268s to ~50ms." Surprised the linear search lasted this long in the kernel code, then again this just impacts the early boot time memory allocator. That optimization was sent out today as part of the memblock pull request for the Linux 7.4 kernel.