The original flatview_simplify() implementation uses memmove() to shift
array elements after each merge operation, resulting in O(n²) time
complexity in the worst case. This is inefficient for VMs with large
memory topologies containing hundreds of MemoryRegions.

Replace the memmove-based approach with a two-pointer in-place compression
algorithm that achieves O(n) time complexity. The new algorithm uses a
write pointer i and a read pointer j, where i ≤ j is always maintained.
This invariant ensures we never overwrite unprocessed data, making memmove
unnecessary.

Signed-off-by: Bin Guo <guobin@linux.alibaba.com>
---
 system/memory.c | 27 ++++++++++++++-------------
 1 file changed, 14 insertions(+), 13 deletions(-)

diff --git a/system/memory.c b/system/memory.c
index 56f3225b21..0ff066c348 100644
--- a/system/memory.c
+++ b/system/memory.c
@@ -336,24 +336,25 @@ static bool can_merge(FlatRange *r1, FlatRange *r2)
 /* Attempt to simplify a view by merging adjacent ranges */
 static void flatview_simplify(FlatView *view)
 {
-    unsigned i, j, k;
+    unsigned i, j;
+
+    if (view->nr <= 1) {
+        return;
+    }
 
     i = 0;
-    while (i < view->nr) {
-        j = i + 1;
-        while (j < view->nr
-               && can_merge(&view->ranges[j-1], &view->ranges[j])) {
+    for (j = 1; j < view->nr; j++) {
+        if (can_merge(&view->ranges[i], &view->ranges[j])) {
             int128_addto(&view->ranges[i].addr.size, view->ranges[j].addr.size);
-            ++j;
-        }
-        ++i;
-        for (k = i; k < j; k++) {
-            memory_region_unref(view->ranges[k].mr);
+            memory_region_unref(view->ranges[j].mr);
+        } else {
+            i++;
+            if (i != j) {
+                view->ranges[i] = view->ranges[j];
+            }
         }
-        memmove(&view->ranges[i], &view->ranges[j],
-                (view->nr - j) * sizeof(view->ranges[j]));
-        view->nr -= j - i;
     }
+    view->nr = i + 1;
 }
 
 static void adjust_endianness(MemoryRegion *mr, uint64_t *data, MemOp op)
-- 
2.50.1 (Apple Git-155)

On 31/3/26 08:07, Bin Guo wrote:
> The original flatview_simplify() implementation uses memmove() to shift
> array elements after each merge operation, resulting in O(n²) time
> complexity in the worst case. This is inefficient for VMs with large
> memory topologies containing hundreds of MemoryRegions.
> 
> Replace the memmove-based approach with a two-pointer in-place compression
> algorithm that achieves O(n) time complexity. The new algorithm uses a
> write pointer i and a read pointer j, where i ≤ j is always maintained.
> This invariant ensures we never overwrite unprocessed data, making memmove
> unnecessary.

Super nice!

Reviewed-by: Philippe Mathieu-Daudé <philmd@linaro.org>

> Signed-off-by: Bin Guo <guobin@linux.alibaba.com>
> ---
>   system/memory.c | 27 ++++++++++++++-------------
>   1 file changed, 14 insertions(+), 13 deletions(-)

Queued, thanks.

Paolo