Re: [PATCH v3 2/2] memblock: use binary search to locate candidate regions

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] mm: commit message falsely claims O(N log N) worst-case complexity
--

commit ffd047af563941b5aabcd86a52d569f9b40c01ec
Author: Tarun Sahu <tarunsahu@xxxxxxxxxx>

memblock: use binary search to locate candidate regions

This commit introduces a binary search helper, memblock_bsearch_start(),
to optimize finding candidate regions in memblock_add_range() and
memblock_isolate_range(), aiming to reduce boot-time overhead during heavy
memory fragmentation.

> Under heavy memory fragmentation (such as KHO page preservation registering
> hundreds of thousands of disjoint folios), scanning from index 0 on every
> insertion and isolation results in O(N^2) complexity, causing boot-time
> memory retrieval to take several minutes (~268s for 393k pages).
>
> 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.

[Severity: Medium]
Is the claim of O(N log N) worst-case complexity mathematically accurate here?

While the binary search reduces the time to locate the insertion index to
O(log N), the regions are still stored in a contiguous array. If disjoint
memory regions are inserted in an order that requires inserting into the
middle of the array, the subsequent elements still need to be shifted.

Looking at memblock_insert_region() which is called during insertion:

static void __init_memblock memblock_insert_region(...)
{
        ...
        memmove(rgn + 1, rgn, (type->cnt - idx) * sizeof(*rgn));
        ...
}

Because this memory move operation guarantees the worst-case complexity of a
single insertion remains O(N), wouldn't inserting N disjoint regions in
descending or scattered order still result in an O(N^2) worst-case time
complexity overall?

The described KHO workload sequentially appends regions, which avoids the
shifting overhead and achieves O(N) overall. Could the commit message be
updated to clarify that this patch improves sequential insertion to O(N),
but the worst-case for fragmented insertions remains O(N^2) due to the array
shifting?

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20260926092448.4090401-1-tarunsahu@xxxxxxxxxx?part=2