From nobody Wed Apr 1 23:53:39 2026 Delivered-To: importer@patchew.org Authentication-Results: mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=pass(p=none dis=none) header.from=linux.alibaba.com ARC-Seal: i=1; a=rsa-sha256; t=1774937624; cv=none; d=zohomail.com; s=zohoarc; b=TWafVuhkTbasgDgyXZsF81hFIiIjI/tkjqtFEui5SRLJD3UJBFuG+8DuookLfleByzwiW+yosGR8vJ1hH/XFYsxsxRQV2S5dacn5Z2O+5SaMOmQPd4z5HuRV8BELWJx//achQ1BjyObYU/StzFDSq8rmNuY3GAadWC56lEKbkZ0= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1774937624; h=Content-Type:Content-Transfer-Encoding:Cc:Cc:Date:Date:From:From:List-Subscribe:List-Post:List-Id:List-Archive:List-Help:List-Unsubscribe:MIME-Version:Message-ID:Sender:Subject:Subject:To:To:Message-Id:Reply-To; bh=k/Pw/7AwyXnbAwlCyIMzZnhcQ+HaOc0N3Dc1HQuWsgo=; b=a1wr6sdZ7+tcGfewG4I3jm/DNw2Bihbt/lLdlrgConBPBF4A9I10aVdxx//MeXlf1EnWZCMDAZC8H/cb3LJ+bO1brB3JVxMjFfy5rvpbDFZr3LUBbUmE+mev/qXG+oGHfhxEyC9JrgHv9Eq9rOqYsrSpOn+yGpXgdmGh1e8/XLI= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=qemu-devel-bounces+importer=patchew.org@nongnu.org; dmarc=pass header.from= (p=none dis=none) Return-Path: Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) by mx.zohomail.com with SMTPS id 1774937623998769.4056255590841; Mon, 30 Mar 2026 23:13:43 -0700 (PDT) Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1w7SLh-0003iR-6y; Tue, 31 Mar 2026 02:13:13 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1w7SLb-0003gP-AA for qemu-devel@nongnu.org; Tue, 31 Mar 2026 02:13:07 -0400 Received: from out30-118.freemail.mail.aliyun.com ([115.124.30.118]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1w7SLX-00032T-2r for qemu-devel@nongnu.org; Tue, 31 Mar 2026 02:13:05 -0400 Received: from localhost(mailfrom:guobin@linux.alibaba.com fp:SMTPD_---0X03E62i_1774937251 cluster:ay36) by smtp.aliyun-inc.com; Tue, 31 Mar 2026 14:07:40 +0800 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linux.alibaba.com; s=default; t=1774937569; h=From:To:Subject:Date:Message-ID:MIME-Version:Content-Type; bh=k/Pw/7AwyXnbAwlCyIMzZnhcQ+HaOc0N3Dc1HQuWsgo=; b=i2yoM02uJSQKXvXuxDQUSGbaV4U1/j2rjjLTlSkILYXWK2qkxEyjJ7gqkCKRf9Z6FcZIH/l7R8MOBpEJN7tplaFQMsy9R2GTurpNZkugosdkrimzzADBBWCQWKEdkwaVwqxTNmANKA39d0RfFB4uYGNRa7Nuu5HbEPn1KLmUBk8= X-Alimail-AntiSpam: AC=PASS; BC=-1|-1; BR=01201311R671e4; CH=green; DM=||false|; DS=||; FP=0|-1|-1|-1|0|-1|-1|-1; HT=maildocker-contentspam011083073210; MF=guobin@linux.alibaba.com; NM=1; PH=DS; RN=4; SR=0; TI=SMTPD_---0X03E62i_1774937251; From: Bin Guo To: qemu-devel@nongnu.org Cc: peterx@redhat.com, richard.henderson@linaro.org, philmd@linaro.org Subject: [PATCH] memory: Optimize flatview_simplify() to eliminate redundant memmove calls Date: Tue, 31 Mar 2026 14:07:31 +0800 Message-ID: <20260331060731.82641-1-guobin@linux.alibaba.com> X-Mailer: git-send-email 2.50.1 MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Received-SPF: pass (zohomail.com: domain of gnu.org designates 209.51.188.17 as permitted sender) client-ip=209.51.188.17; envelope-from=qemu-devel-bounces+importer=patchew.org@nongnu.org; helo=lists.gnu.org; Received-SPF: pass client-ip=115.124.30.118; envelope-from=guobin@linux.alibaba.com; helo=out30-118.freemail.mail.aliyun.com X-Spam_score_int: -154 X-Spam_score: -15.5 X-Spam_bar: --------------- X-Spam_report: (-15.5 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, ENV_AND_HDR_SPF_MATCH=-0.5, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_VALIDITY_CERTIFIED_BLOCKED=1, RCVD_IN_VALIDITY_RPBL_BLOCKED=1, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, UNPARSEABLE_RELAY=0.001, USER_IN_DEF_DKIM_WL=-7.5, USER_IN_DEF_SPF_WL=-7.5 autolearn=no autolearn_force=no X-Spam_action: no action X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: qemu development List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+importer=patchew.org@nongnu.org Sender: qemu-devel-bounces+importer=patchew.org@nongnu.org X-ZohoMail-DKIM: pass (identity @linux.alibaba.com) X-ZM-MESSAGEID: 1774937626457154100 The original flatview_simplify() implementation uses memmove() to shift array elements after each merge operation, resulting in O(n=C2=B2) 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 =E2=89=A4 j is always maintai= ned. This invariant ensures we never overwrite unprocessed data, making memmove unnecessary. Signed-off-by: Bin Guo Reviewed-by: Philippe Mathieu-Daud=C3=A9 --- 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 <=3D 1) { + return; + } =20 i =3D 0; - while (i < view->nr) { - j =3D i + 1; - while (j < view->nr - && can_merge(&view->ranges[j-1], &view->ranges[j])) { + for (j =3D 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 =3D i; k < j; k++) { - memory_region_unref(view->ranges[k].mr); + memory_region_unref(view->ranges[j].mr); + } else { + i++; + if (i !=3D j) { + view->ranges[i] =3D view->ranges[j]; + } } - memmove(&view->ranges[i], &view->ranges[j], - (view->nr - j) * sizeof(view->ranges[j])); - view->nr -=3D j - i; } + view->nr =3D i + 1; } =20 static void adjust_endianness(MemoryRegion *mr, uint64_t *data, MemOp op) --=20 2.50.1 (Apple Git-155)