From nobody Sun Feb 8 05:58:58 2026 Received: from mail-dy1-f172.google.com (mail-dy1-f172.google.com [74.125.82.172]) (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 BBFCD331A70 for ; Thu, 22 Jan 2026 15:42:40 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=74.125.82.172 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1769096562; cv=none; b=ORggnISs4WGDuOWKLVIeMuGq4VcEFTNRbUXSPci6LmeHlbgKesyS9KvdHho1XK9idIAAPbhkHNOy2Jt6vcSe/SHI6uiOzTdxsW9T1kHtX2DWiKfEHnm4OKOLWqUYnJGGlkeJtn7KmuN4nIZWbrOiBR85QuJTFwkBsrEIWIhV4h0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1769096562; c=relaxed/simple; bh=OgZv4A220XtraQC2unUD+oVmuUGwQH5ecMGR+9DykVQ=; h=From:To:Cc:Subject:Date:Message-ID:MIME-Version; b=TefAxid4loobnxpNTXAYzfnKPP7bpCHD10ef21fQz9d3ZLi+zgocdJmc4DSmXEvD8EyFzICfqCQ5k6vfLz5DQ1ltxWvFPA/Bf4Z9Sawvix/MFnUvowpG0ge+MikwmaULeVyXcy0jxkY2Aoiule9hPro+6ZxBVYNk4g1YhsFxrT0= 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=kWIFn6Xk; arc=none smtp.client-ip=74.125.82.172 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="kWIFn6Xk" Received: by mail-dy1-f172.google.com with SMTP id 5a478bee46e88-2b72e49776eso807196eec.1 for ; Thu, 22 Jan 2026 07:42:40 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1769096559; x=1769701359; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=xyab1YiLU/6rYP9PiW5CCJzizTBh6AnCPR+u5bcjLx8=; b=kWIFn6XkHkbJ/IzcIWiRJdOibzBzwUlsnWz5K3egNZADmRcX9c2Ka+9Z1J2wN1oCxJ wveMqA6GCfL0whhHxofOEo2kBYfClehgT10+TQvynTafJRv3qtEbWLmL0b0UWqbTlX+h 5m1t1ILAreO74lYV3IeEd5p+I4rkWBIX3v7s3lpxKuDctbO/csG+eQjuGSkWS6M1w5vA J7NlOO5PBSYPDT8wDSLYgvb5sAsNTKNG7jX0Cu6wbiFnAnoXQubCflWDk8IEosw+LhNz hcE3RnYacSy6ThCSXAYmIzmKoYHCRZPHkcC/NFUw6yx15HXu69RYSYZteGETmgKI3MRE 6bng== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1769096559; x=1769701359; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-gg:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=xyab1YiLU/6rYP9PiW5CCJzizTBh6AnCPR+u5bcjLx8=; b=EApir9N9ys4hC8m+f3CbJIfytiNc/ZEvqd0VIxjStjGtpNlL+nbM9/te6FwxSllFFu wEg5rbjtES+jMWR/S0kY0NLz2HUqZl9dymdbVk/Psqo08vpG+PUSm/L8+dD2teJwfrQf TOkXFld8BpEVxHWk1jA0rc6gfZJdkfu2KuuL4XULVrmiN8QjR7jnbUiu4b57RHmGsXkj //aypVhmx/zgm6W2KLOQ7uINtdZXYVvitvCPR2c25oe1ITd2yW2R+6ASXlszk4eEfYAa 4vRFrjU7bxtsSIrj6rblTSUpSYnm650ZDkgC6sf2TwSbIplLpl1YIxGhLgD2Bxof+IKa cWPg== X-Forwarded-Encrypted: i=1; AJvYcCXOZLlRaXSkzkOu62lhGmkUCqxh7M1iuoC789ilUpCRwO96MZx0NzIQ6ie2NI6x7CfiMCVNYSJpZQwLR8E=@vger.kernel.org X-Gm-Message-State: AOJu0Yyc7gdbLGAjJw9o+yYR2IKWn4yodiBfpUfDosoLnFmcqC0wFt1I OAnqCezw2RcpZeCSu6KCMItLHsY679XjbjNeMeidaYjizhVSOLoHooLw X-Gm-Gg: AZuq6aLov9wox/UQRFB3qCzfOEKYw1qgInHmHularTMejHknjHW3bUwt8yB114oOFWW SNeKhTVrkagmGsYNr0sINNd9mS4rlYWVXs1saynUIsuZo2F+k4UoWUuvT9AR9+zDXLHjIPoXurT Z0NKGAE4agnJqvlKWjMbJpwK/Eruv3O8uSR6ezpet0vRf591jQAturXRDYi4VSiGJF2J/B0RBkz gkA/Zn7PIQLkEqAaQHb+gYwsXnH2m7ujRzX+Dcy9syxw/u6H2I6jqF4Rxs+KSLkNt45qiJFY9cD 1GOcSm24j/MvqUmSC8iTmwxal/nBvT9jQHiNXSHhLha7d7VpChd1YEuecuC4e9XwdzF0tySi6UA okZDJjKGDU2Wf55N0NCnH9cKWPinW3OzgaxocQNfxImuad+/uF0jZq1CrI3Nw6zDMKVsSXIKVZH SYs/4= X-Received: by 2002:a05:693c:6210:b0:2b7:2d5e:3f49 with SMTP id 5a478bee46e88-2b72d5e4121mr708642eec.10.1769096558454; Thu, 22 Jan 2026 07:42:38 -0800 (PST) Received: from debian ([74.48.213.230]) by smtp.gmail.com with ESMTPSA id 5a478bee46e88-2b7102fd2efsm7928856eec.12.2026.01.22.07.42.34 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 22 Jan 2026 07:42:37 -0800 (PST) From: Qiliang Yuan To: Ingo Molnar , Peter Zijlstra , Juri Lelli , Vincent Guittot Cc: Dietmar Eggemann , Steven Rostedt , Ben Segall , Mel Gorman , Valentin Schneider , linux-kernel@vger.kernel.org, Qiliang Yuan , Qiliang Yuan Subject: [PATCH] sched/fair: Optimize EAS energy calculation complexity from O(N) to O(1) inside inner loop Date: Thu, 22 Jan 2026 10:42:27 -0500 Message-ID: <20260122154227.130767-1-realwujing@gmail.com> X-Mailer: git-send-email 2.51.0 Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" By pre-calculating the base max utilization of each performance domain at the start of find_energy_efficient_cpu(), we can avoid the repetitive O(M) scan in eenv_pd_max_util() for every candidate CPU. This reduces the complexity of energy calculation from O(P*N) to O(N + P^2), where P is the number of performance domains. For systems with many performance domains or high core counts, this results in significant reduction in wakeup latency. Signed-off-by: Qiliang Yuan Signed-off-by: Qiliang Yuan --- kernel/sched/fair.c | 46 ++++++++++++++++++++++++----------------- kernel/sched/sched.h | 4 ++++ kernel/sched/topology.c | 1 + 3 files changed, 32 insertions(+), 19 deletions(-) diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 458324d240e9..de5bfdfe553f 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -8236,41 +8236,32 @@ static inline void eenv_pd_busy_time(struct energy_= env *eenv, * exceed @eenv->cpu_cap. */ static inline unsigned long -eenv_pd_max_util(struct energy_env *eenv, struct cpumask *pd_cpus, +eenv_pd_max_util(struct energy_env *eenv, struct perf_domain *pd, struct task_struct *p, int dst_cpu) { - unsigned long max_util =3D 0; - int cpu; + unsigned long max_util =3D pd->max_util; =20 - for_each_cpu(cpu, pd_cpus) { - struct task_struct *tsk =3D (cpu =3D=3D dst_cpu) ? p : NULL; - unsigned long util =3D cpu_util(cpu, p, dst_cpu, 1); + if (dst_cpu >=3D 0 && cpumask_test_cpu(dst_cpu, perf_domain_span(pd))) { + unsigned long util =3D cpu_util(dst_cpu, p, dst_cpu, 1); unsigned long eff_util, min, max; =20 - /* - * Performance domain frequency: utilization clamping - * must be considered since it affects the selection - * of the performance domain frequency. - * NOTE: in case RT tasks are running, by default the min - * utilization can be max OPP. - */ - eff_util =3D effective_cpu_util(cpu, util, &min, &max); + eff_util =3D effective_cpu_util(dst_cpu, util, &min, &max); =20 /* Task's uclamp can modify min and max value */ - if (tsk && uclamp_is_used()) { + if (uclamp_is_used()) { min =3D max(min, uclamp_eff_value(p, UCLAMP_MIN)); =20 /* * If there is no active max uclamp constraint, * directly use task's one, otherwise keep max. */ - if (uclamp_rq_is_idle(cpu_rq(cpu))) + if (uclamp_rq_is_idle(cpu_rq(dst_cpu))) max =3D uclamp_eff_value(p, UCLAMP_MAX); else max =3D max(max, uclamp_eff_value(p, UCLAMP_MAX)); } =20 - eff_util =3D sugov_effective_cpu_perf(cpu, eff_util, min, max); + eff_util =3D sugov_effective_cpu_perf(dst_cpu, eff_util, min, max); max_util =3D max(max_util, eff_util); } =20 @@ -8286,7 +8277,7 @@ static inline unsigned long compute_energy(struct energy_env *eenv, struct perf_domain *pd, struct cpumask *pd_cpus, struct task_struct *p, int dst_cpu) { - unsigned long max_util =3D eenv_pd_max_util(eenv, pd_cpus, p, dst_cpu); + unsigned long max_util =3D eenv_pd_max_util(eenv, pd, p, dst_cpu); unsigned long busy_time =3D eenv->pd_busy_time; unsigned long energy; =20 @@ -8351,7 +8342,7 @@ static int find_energy_efficient_cpu(struct task_stru= ct *p, int prev_cpu) unsigned long best_actual_cap =3D 0; unsigned long prev_actual_cap =3D 0; struct sched_domain *sd; - struct perf_domain *pd; + struct perf_domain *pd, *tmp_pd; struct energy_env eenv; =20 rcu_read_lock(); @@ -8377,6 +8368,23 @@ static int find_energy_efficient_cpu(struct task_str= uct *p, int prev_cpu) =20 eenv_task_busy_time(&eenv, p, prev_cpu); =20 + /* Algorithmic Optimization: Pre-calculate max_util for O(1) energy estim= ation */ + for (tmp_pd =3D pd; tmp_pd; tmp_pd =3D tmp_pd->next) { + unsigned long max_u =3D 0; + int i; + + for_each_cpu(i, perf_domain_span(tmp_pd)) { + unsigned long util =3D cpu_util(i, p, -1, 1); + unsigned long eff_util, min, max; + + eff_util =3D effective_cpu_util(i, util, &min, &max); + eff_util =3D sugov_effective_cpu_perf(i, eff_util, min, max); + if (eff_util > max_u) + max_u =3D eff_util; + } + tmp_pd->max_util =3D max_u; + } + for (; pd; pd =3D pd->next) { unsigned long util_min =3D p_util_min, util_max =3D p_util_max; unsigned long cpu_cap, cpu_actual_cap, util; diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h index d30cca6870f5..f308d335ca77 100644 --- a/kernel/sched/sched.h +++ b/kernel/sched/sched.h @@ -972,6 +972,10 @@ struct perf_domain { struct em_perf_domain *em_pd; struct perf_domain *next; struct rcu_head rcu; + + /* O(1) optimization hints */ + unsigned long max_util; + int max_spare_cap_cpu; }; =20 /* diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c index 5a3f29a26bdb..b9de022ddb53 100644 --- a/kernel/sched/topology.c +++ b/kernel/sched/topology.c @@ -354,6 +354,7 @@ static struct perf_domain *pd_init(int cpu) if (!pd) return NULL; pd->em_pd =3D obj; + pd->max_spare_cap_cpu =3D -1; =20 return pd; } --=20 2.51.0