From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-dy1-f177.google.com (mail-dy1-f177.google.com [74.125.82.177]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 2DC543ED111 for ; Wed, 4 Feb 2026 12:11:53 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=74.125.82.177 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1770207113; cv=none; b=mOx6WgqlInxFx7fdc7dM4TWidHgciIbDQIaEqCdAswzaxE3rA+B7jwQIiOrEWrp/wX26YJjPcygofbjyp5kTdN+Ru6W7CLYVirM5Nzif2l4eYsA9tdCxRZmhzQQHwt56RdG+mG+vEEck245nsUS2AkOFgapYp/1haiq1tBmyhvc= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1770207113; c=relaxed/simple; bh=aoaN7ME1iMyYf++bnpGvz7GtM2z7TXRS237HYDX+pKc=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=A4aG8CwOSVy5+Q2ht8kqCrpPiHaaG3MLkJ6Ibp5J5Qqkuy5/Bz/Of2fzCwnXRFREf2f8Yz+cN71dp41KdCOW3kXvux/PQyyhEhlt1shK4TUIexyn8xokRAsOAzQX+Gkx2UWdnlExQMpKMzXV2YmoR9arwER/dte6cU1jfiN3q7w= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=efQO8Jri; arc=none smtp.client-ip=74.125.82.177 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="efQO8Jri" Received: by mail-dy1-f177.google.com with SMTP id 5a478bee46e88-2b751c8b6beso482472eec.0 for ; Wed, 04 Feb 2026 04:11:53 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1770207112; x=1770811912; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=YN0YQmQWxiKNIFqzhGl+72lot5+Q/3sN6ija9jeI4OI=; b=efQO8JriXRiWQTVc/Oy/3KKezLgfcEPgzwC6AmXGU9cBcqjF9Sdh3fNFDCVNb6X/oT R150tlJK64YNsjPKO7/0ogae9frGSHIZRsY3lQnV+wVVMPBnlgwgKH5jOJ0VKDJ2OVn8 D565PdtS1Qa3tpzzRGngFjqr1rqKzk666OrHT6VNYB4GWjnHtXT5QNrvLiMiwr6v2858 xYGRqpO7THia+fqD92n7pqxSrhhSbYraOaNRozFPUaNEjlja1T7Lyhi5IcOHV5d1PN9C ufJ7j/Z93Z8b2fyxKqDn1SUrAZaC7WR5g9cAGLABLfpO0yycDP9ODbEzHwuBJIu7vSYu b8ew== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1770207112; x=1770811912; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to; bh=YN0YQmQWxiKNIFqzhGl+72lot5+Q/3sN6ija9jeI4OI=; b=SRnBudvOhr4j5oi5xSAuHj3eWbIVkWaxfaKM0fBqQz8u5egWmHIa/jjvDOudpB5MkI NJ19CtCCL2iS9APn1uDsWSeX0iC+5Mi/OWVmBBV+Tm445uuFM6iSsusJwiKF33N4C9Fn oja+q+aOvcksdb0T/7Cx9TrW6G7QMGXP/RmFD+vNE+GWu8PAEVcFV/ReV/oza1MMk2XK jZaE3B5Q3BS2sDvxJCV3QxRKsHqsYcxIHqt5Xe7TCPb09oF19+k60O7F2DsSoq6pH6Ze 46NZlY6TM63d2J98KDDs5I0pzZRCeYXkL89E3LfecJwTrJIFeg6Ivnr9Jt9Xc9BzpwbZ ZTpQ== X-Forwarded-Encrypted: i=1; AJvYcCVJMyGcsOO4kSRntu3y5ya4unrolUy2PP8lb4oGVp09rWGwSlwkIK2dtH4O8EHIx4RiNCug3k5F18Xi+hg=@vger.kernel.org X-Gm-Message-State: AOJu0Ywlv2b5rJIMB8a+sOONOBayMODWGqp5II3bROJb8cg1JVNEGa7B B5eIlmy+md3cMnp2ZVdBd7hBvdk3O8emIT1HfdpxWo6X39JQuT4eJTnW X-Gm-Gg: AZuq6aI/Qy4oYaiZ+6K9akq9O5UTNsMoZg2aXeApyGUb4WQPc1KwwQEYs1no9gB0cZz elJcnhjtXJscy3/awtXlPzi41orgmMTeeYtdMVh1o494aFWcnKa2YD9Gn5tHVFRE7zAeHJgwEEp buW/tquZhMVq/R9cuwqur0fZZDCxw/Dk11D37ZCztmYHKlXrd5cNQRyIMBbgBxzqoTRYZNOZNtI QzsEf1YzGwrsPqtBtBSSx/wN0i+K0QRPexaVKiFRsjC3mwlKqxnJJFh9csM3Y9SKqJzfxkK2P2Q 61+Vkwb68dju4eOk9bA6kEnkz2kO7R7dQkCV0OWcOxq0qC9s3PRGN1umxC2PWXdENdVQ0Q4CqJa nceBROfS6IUR1u6JmrE3jG7MybDGYtSWWlQ0+usMPvsXUK97p7Mg22yFlWg9p5cKFLIywklUnsb c9zoHHZqbAiKsJoA== X-Received: by 2002:a05:693c:37c8:b0:2b6:bb18:c70a with SMTP id 5a478bee46e88-2b820f26aa6mr2418891eec.15.1770207112205; Wed, 04 Feb 2026 04:11:52 -0800 (PST) Received: from debian ([74.48.213.230]) by smtp.gmail.com with ESMTPSA id a92af1059eb24-126f504e860sm1967203c88.17.2026.02.04.04.11.48 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 04 Feb 2026 04:11:51 -0800 (PST) From: Qiliang Yuan To: vincent.guittot@linaro.org, christian.loehle@arm.com Cc: bsegall@google.com, dietmar.eggemann@arm.com, juri.lelli@redhat.com, linux-kernel@vger.kernel.org, mgorman@suse.de, mingo@redhat.com, peterz@infradead.org, realwujing@gmail.com, rostedt@goodmis.org, vschneid@redhat.com, yuanql9@chinatelecom.cn Subject: Re: [PATCH v2 RSEND] sched/fair: Optimize EAS energy calculation complexity from O(N) to O(1) inside inner loop Date: Wed, 4 Feb 2026 07:11:41 -0500 Message-ID: <20260204121145.3951995-1-realwujing@gmail.com> X-Mailer: git-send-email 2.51.0 In-Reply-To: References: Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Hi Christian, Vincent, Thank you for the detailed feedback. On Mon, Feb 02, 2026 at 10:48:04AM +0000, Christian Loehle wrote: > Which is still O(n), I think the title is misleading. On Tue, Feb 03, 2026 at 06:16:27PM +0100, Vincent Guittot wrote: > Ok, but the whole feec() remains O(n) You are absolutely right. While the per-candidate CPU energy estimation was optimized, the overall complexity of find_energy_efficient_cpu() remains O(N). I've renamed the patch in v3 to "Optimize EAS by reducing redundant performance domain scans" to more accurately reflect the scope of the improvement. On Mon, Feb 02, 2026 at 10:48:04AM +0000, Christian Loehle wrote: > I don't think this is actually true. EAS doesn't really work with a large > number of PDs because of the expensive wakeup path. > I don't think there's an EAS system out there where this would actually make > a measurable impact. On Tue, Feb 03, 2026 at 06:16:27PM +0100, Vincent Guittot wrote: > Could you add some figures to highlight the statement above ? In v3, I've further optimized the path by consolidating the 'pd_max_util' and 'pd_busy_time' calculations into the same loop that finds the 'max_spare_cap_cpu'. This reduces the total number of full PD scans from three down to one per performance domain. I agree that the impact on current mobile systems with 2-3 PDs might be subtle. However, as topologies grow and the wake-up path becomes more sensitive to cache misses, reducing redundant scans of task structures and rq utilization is a worthwhile constant-factor improvement. I'm investigating synthetic benchmarks on systems with higher core counts to provide more concrete figures. I've sent out v3 which includes these further logic consolidations. v3 link: https://lore.kernel.org/all/20260204120509.3950227-1-realwujing@gmail.com/ Thanks, Qiliang