From patchwork Thu Feb 6 14:22:59 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Rafael J. Wysocki" X-Patchwork-Id: 862862 Received: from cloudserver094114.home.pl (cloudserver094114.home.pl [79.96.170.134]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id CEAB21EDA33; Thu, 6 Feb 2025 14:29:32 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=79.96.170.134 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738852175; cv=none; b=JUq5RYpdPwuWd7rcjmOQwAKnenzr6u6HP8Gl+k98P1LmGYL3z6kbMIKPHpE7aDu79hllWetFINJ1yxaM10pIkucWl+tFbCZXd8aHBBLWECWTcHkMxWNsRofxoALnlQjG7yfO70aD0CGvJTnXA8e6jlfcI5lO6xUq8DZmuRf9PIs= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738852175; c=relaxed/simple; bh=w88YqCV4joJ59wLsJjRrUn/tCBNWwaQK/X+ysio0IFA=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=UNlEOhxZvIwBC4VY18DrDC2avEKLQYgXR6snA08PPt4KM0XahwGMXsDeAXPlCYhWhSSFn8zFVHiSBZavU/brE8xir7t1Ydq+mt/REVxTsnSG3xH1SfnF+0OE/v7EJds+9R7p6k4rzLGzhvuUFMRZILORKa1bn697oVrAgR2Mh6M= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=rjwysocki.net; spf=pass smtp.mailfrom=rjwysocki.net; dkim=pass (2048-bit key) header.d=rjwysocki.net header.i=@rjwysocki.net header.b=M7DRQVSi; arc=none smtp.client-ip=79.96.170.134 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=rjwysocki.net Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=rjwysocki.net Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=rjwysocki.net header.i=@rjwysocki.net header.b="M7DRQVSi" Received: from localhost (127.0.0.1) (HELO v370.home.net.pl) by /usr/run/smtp (/usr/run/postfix/private/idea_relay_lmtp) via UNIX with SMTP (IdeaSmtpServer 6.2.1) id e5625c4cae068dd4; Thu, 6 Feb 2025 15:29:25 +0100 Received: from kreacher.localnet (unknown [195.136.19.94]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by cloudserver094114.home.pl (Postfix) with ESMTPSA id 1EEA26BA970; Thu, 6 Feb 2025 15:29:25 +0100 (CET) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=rjwysocki.net; s=dkim; t=1738852165; bh=w88YqCV4joJ59wLsJjRrUn/tCBNWwaQK/X+ysio0IFA=; h=From:Subject:Date; b=M7DRQVSigP8PXrHLIp1ijxfv9rKoEe6f6XUdS6rAfsBKNFwP+b0r08Dg1xXdXnh8g DfiGglwesh5WPYZNjH++USZU6dbPg9HYqj/4Wq7TNlrujiXXO6blQN3zGUMMfRsLHb OWIltwzl1OM+R6yg01fc7sD/NlsIbOM5iNKVwWfMzom+a1BtZfL5SUNbYtolvVcLaz mXPpSwdaKAujq2nRQX/mOzNezORHqnM8sE8UNCvXSMS71Qm4kPdk5ZK7WlnA+hut1G dsCCBC5Dbh5gJGRyrApf4xJ+9QxDMOZeUesxGMkMqE0O1SIz3gvJro46IGWIDhFDmX +bkVsNxCJINkg== From: "Rafael J. Wysocki" To: Linux PM Cc: LKML , Daniel Lezcano , Christian Loehle , Artem Bityutskiy , Aboorva Devarajan Subject: [RFT][PATCH v1 1/5] cpuidle: menu: Drop a redundant local variable Date: Thu, 06 Feb 2025 15:22:59 +0100 Message-ID: <13699686.uLZWGnKmhe@rjwysocki.net> In-Reply-To: <1916668.tdWV9SEqCh@rjwysocki.net> References: <1916668.tdWV9SEqCh@rjwysocki.net> Precedence: bulk X-Mailing-List: linux-pm@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-CLIENT-IP: 195.136.19.94 X-CLIENT-HOSTNAME: 195.136.19.94 X-VADE-SPAMSTATE: clean X-VADE-SPAMCAUSE: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgddvieeifecutefuodetggdotefrodftvfcurfhrohhfihhlvgemucfjqffogffrnfdpggftiffpkfenuceurghilhhouhhtmecuudehtdenucesvcftvggtihhpihgvnhhtshculddquddttddmnecujfgurhephffvvefufffkjghfggfgtgesthfuredttddtjeenucfhrhhomhepfdftrghfrggvlhculfdrucghhihsohgtkhhifdcuoehrjhifsehrjhifhihsohgtkhhirdhnvghtqeenucggtffrrghtthgvrhhnpedvffeuiedtgfdvtddugeeujedtffetteegfeekffdvfedttddtuefhgeefvdejhfenucfkphepudelhedrudefiedrudelrdelgeenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepihhnvghtpeduleehrddufeeirdduledrleegpdhhvghlohepkhhrvggrtghhvghrrdhlohgtrghlnhgvthdpmhgrihhlfhhrohhmpehrjhifsehrjhifhihsohgtkhhirdhnvghtpdhnsggprhgtphhtthhopeeipdhrtghpthhtoheplhhinhhugidqphhmsehvghgvrhdrkhgvrhhnvghlrdhorhhgpdhrtghpthhtoheplhhinhhugidqkhgvrhhnvghlsehvghgvrhdrkhgvrhhnvghlrdhorhhgpdhrtghpthhtohepuggrnhhivghlrdhlvgiitggrnhhosehlihhnrghrohdrohhrghdprhgtphhtthhopegthhhrihhsthhirghnrdhlohgvhhhlvgesrghrmhdrtghomhdprhgtphhtthhopegrrhhtvghmrdgsihhthihuthhskhhihieslhh X-DCC--Metrics: v370.home.net.pl 1024; Body=6 Fuz1=6 Fuz2=6 From: Rafael J. Wysocki Local variable min in get_typical_interval() is updated, but never accessed later, so drop it. No functional impact. Signed-off-by: Rafael J. Wysocki --- drivers/cpuidle/governors/menu.c | 6 +----- 1 file changed, 1 insertion(+), 5 deletions(-) --- a/drivers/cpuidle/governors/menu.c +++ b/drivers/cpuidle/governors/menu.c @@ -117,7 +117,7 @@ static unsigned int get_typical_interval(struct menu_device *data) { int i, divisor; - unsigned int min, max, thresh, avg; + unsigned int max, thresh, avg; uint64_t sum, variance; thresh = INT_MAX; /* Discard outliers above this value */ @@ -125,7 +125,6 @@ again: /* First calculate the average of past intervals */ - min = UINT_MAX; max = 0; sum = 0; divisor = 0; @@ -136,9 +135,6 @@ divisor++; if (value > max) max = value; - - if (value < min) - min = value; } } From patchwork Thu Feb 6 14:24:18 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Rafael J. Wysocki" X-Patchwork-Id: 863206 Received: from cloudserver094114.home.pl (cloudserver094114.home.pl [79.96.170.134]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id D06C71EDA34; Thu, 6 Feb 2025 14:29:32 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=79.96.170.134 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738852175; cv=none; b=YxK+vIos/tAGIHP7XZEIxKRDKelGbi5TQ7tuLj+HzinR6TMfjUDx+cTm7J6nbyOM12J5/59RUoss2/seEJvEZteiOphLsDt9FtkZNHk67BODZXqWOjoOYymxraZwN5WfxovVSmi/+bgeb0J3/12wjL+roYe3W/ywm2Z/cN6i6kg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738852175; c=relaxed/simple; bh=ALEieubBgccz3ujIHX0fEgcGmndFC4PRDsNOYLwOPKI=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=rTXi1I/Wm1ZIip/CgYUtEjoCL6uPTl+6Kb1xZZJVdgGNkS+PwkcXjVBT0ZYX/9CXkscNJzqVSZEM20+k0ZpkOo2RsIoeB0+pqXzHEPUa76U/I2y1GVwigsAk+fB3NvWQbgIgr6wrgwV1DoiJisB4jjxOIEftSx+XSppLDDKdx1Q= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=rjwysocki.net; spf=pass smtp.mailfrom=rjwysocki.net; dkim=pass (2048-bit key) header.d=rjwysocki.net header.i=@rjwysocki.net header.b=bF3E5A9/; arc=none smtp.client-ip=79.96.170.134 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=rjwysocki.net Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=rjwysocki.net Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=rjwysocki.net header.i=@rjwysocki.net header.b="bF3E5A9/" Received: from localhost (127.0.0.1) (HELO v370.home.net.pl) by /usr/run/smtp (/usr/run/postfix/private/idea_relay_lmtp) via UNIX with SMTP (IdeaSmtpServer 6.2.1) id 1b2af6f2bbd46cd0; Thu, 6 Feb 2025 15:29:24 +0100 Received: from kreacher.localnet (unknown [195.136.19.94]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by cloudserver094114.home.pl (Postfix) with ESMTPSA id 452FE6BA970; Thu, 6 Feb 2025 15:29:24 +0100 (CET) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=rjwysocki.net; s=dkim; t=1738852164; bh=ALEieubBgccz3ujIHX0fEgcGmndFC4PRDsNOYLwOPKI=; h=From:Subject:Date; b=bF3E5A9/bTCp6+LXbwm183ynq/nffQxfvQIwJjnw6EALGeC6v/fXsBMa8Fhuq6rvk uraaSb7IzDCYiyusUKopobwiVfV0wu0pZoPCOT4rT8GqQ5mMygIRwQeq3X7TM6eRKa cGMQA7iTTSspW81IZAMBqo2ch8GXTH6zbOfZECnCj8j4Cb88/g6Ern/yv8PoAj1nJq BlnOyKUjTHwFBMIeVJSo8g1MtartIL+08NlOrLF4lW2CDzyQVkTHE5ddlw38dZHFrD lDMCCRfp0Mn/zfGeyZ1RBYGugP1pG614wlSWnIOw9rVR2ZHj8DX6wtu+oiwfZrdkOn hIzwUtJbJLGEg== From: "Rafael J. Wysocki" To: Linux PM Cc: LKML , Daniel Lezcano , Christian Loehle , Artem Bityutskiy , Aboorva Devarajan Subject: [RFT][PATCH v1 2/5] cpuidle: menu: Use one loop for average and variance computations Date: Thu, 06 Feb 2025 15:24:18 +0100 Message-ID: <3339073.aeNJFYEL58@rjwysocki.net> In-Reply-To: <1916668.tdWV9SEqCh@rjwysocki.net> References: <1916668.tdWV9SEqCh@rjwysocki.net> Precedence: bulk X-Mailing-List: linux-pm@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-CLIENT-IP: 195.136.19.94 X-CLIENT-HOSTNAME: 195.136.19.94 X-VADE-SPAMSTATE: clean X-VADE-SPAMCAUSE: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgddvieeifecutefuodetggdotefrodftvfcurfhrohhfihhlvgemucfjqffogffrnfdpggftiffpkfenuceurghilhhouhhtmecuudehtdenucesvcftvggtihhpihgvnhhtshculddquddttddmnecujfgurhephffvvefufffkjghfggfgtgesthfuredttddtjeenucfhrhhomhepfdftrghfrggvlhculfdrucghhihsohgtkhhifdcuoehrjhifsehrjhifhihsohgtkhhirdhnvghtqeenucggtffrrghtthgvrhhnpedvffeuiedtgfdvtddugeeujedtffetteegfeekffdvfedttddtuefhgeefvdejhfenucfkphepudelhedrudefiedrudelrdelgeenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepihhnvghtpeduleehrddufeeirdduledrleegpdhhvghlohepkhhrvggrtghhvghrrdhlohgtrghlnhgvthdpmhgrihhlfhhrohhmpehrjhifsehrjhifhihsohgtkhhirdhnvghtpdhnsggprhgtphhtthhopeeipdhrtghpthhtoheplhhinhhugidqphhmsehvghgvrhdrkhgvrhhnvghlrdhorhhgpdhrtghpthhtoheplhhinhhugidqkhgvrhhnvghlsehvghgvrhdrkhgvrhhnvghlrdhorhhgpdhrtghpthhtohepuggrnhhivghlrdhlvgiitggrnhhosehlihhnrghrohdrohhrghdprhgtphhtthhopegthhhrihhsthhirghnrdhlohgvhhhlvgesrghrmhdrtghomhdprhgtphhtthhopegrrhhtvghmrdgsihhthihuthhskhhihieslhh X-DCC--Metrics: v370.home.net.pl 1024; Body=6 Fuz1=6 Fuz2=6 From: Rafael J. Wysocki Use the observation that one loop is sufficient to compute the average of an array of values and their variance to eliminate one of the loops from get_typical_interval(). While at it, make get_typical_interval() consistently use u64 as the 64-bit unsigned integer data type and rearrange some white space and the declarations of local variables in it (to make them follow the reverse X-mas tree pattern). No intentional functional impact. Signed-off-by: Rafael J. Wysocki --- drivers/cpuidle/governors/menu.c | 61 +++++++++++++++++---------------------- 1 file changed, 28 insertions(+), 33 deletions(-) --- a/drivers/cpuidle/governors/menu.c +++ b/drivers/cpuidle/governors/menu.c @@ -116,49 +116,45 @@ */ static unsigned int get_typical_interval(struct menu_device *data) { - int i, divisor; - unsigned int max, thresh, avg; - uint64_t sum, variance; - - thresh = INT_MAX; /* Discard outliers above this value */ + unsigned int max, divisor, thresh = INT_MAX; + u64 avg, variance, avg_sq; + int i; again: - - /* First calculate the average of past intervals */ + /* Compute the average and variance of past intervals. */ max = 0; - sum = 0; + avg = 0; + variance = 0; divisor = 0; for (i = 0; i < INTERVALS; i++) { unsigned int value = data->intervals[i]; - if (value <= thresh) { - sum += value; - divisor++; - if (value > max) - max = value; - } + + /* Discard data points above the threshold. */ + if (value > thresh) + continue; + + divisor++; + + avg += value; + variance += (u64)value * value; + + if (value > max) + max = value; } if (!max) return UINT_MAX; - if (divisor == INTERVALS) - avg = sum >> INTERVAL_SHIFT; - else - avg = div_u64(sum, divisor); - - /* Then try to determine variance */ - variance = 0; - for (i = 0; i < INTERVALS; i++) { - unsigned int value = data->intervals[i]; - if (value <= thresh) { - int64_t diff = (int64_t)value - avg; - variance += diff * diff; - } - } - if (divisor == INTERVALS) + if (divisor == INTERVALS) { + avg >>= INTERVAL_SHIFT; variance >>= INTERVAL_SHIFT; - else + } else { + do_div(avg, divisor); do_div(variance, divisor); + } + + avg_sq = avg * avg; + variance -= avg_sq; /* * The typical interval is obtained when standard deviation is @@ -173,10 +169,9 @@ * Use this result only if there is no timer to wake us up sooner. */ if (likely(variance <= U64_MAX/36)) { - if ((((u64)avg*avg > variance*36) && (divisor * 4 >= INTERVALS * 3)) - || variance <= 400) { + if ((avg_sq > variance * 36 && divisor * 4 >= INTERVALS * 3) || + variance <= 400) return avg; - } } /* From patchwork Thu Feb 6 14:25:18 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Rafael J. Wysocki" X-Patchwork-Id: 863207 Received: from cloudserver094114.home.pl (cloudserver094114.home.pl [79.96.170.134]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 06E8A1EDA20; Thu, 6 Feb 2025 14:29:31 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=79.96.170.134 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738852174; cv=none; b=RETjKLmIsH37KTmz1y6QwNct7ZrOCdSjmvbJzM184IMV0p8sodA+intmFmdEeGjH68N4B6JRQhVnCd7wxhmZ4fHceRYIDN0CKQzygxyuoiHHwl+g0cZq7nCqcrrGYSMRWF2Eq4g2N/CzMve1yJmTYVfZ4/QNv0q6tbCLfNem5wE= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738852174; c=relaxed/simple; bh=ixHGPp5ZLF5maWj/njvU5xlymHep1GI46tlAYLZj4Vc=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=aj0BrotlbxiKB9E4QSG63WIIrFenF9d3N8JFVageaEzTd1dGiWgJgwgWUuMcBIsN8T2vgvfKoRBOT00w3D2HFyh38HxelLoTS51/CopHySyb2DybaS5OlqyBJ+UXo/FsiQZTSTlEf7keUpdnsnmRGk7S+BHKkJku0et4P+U2+kU= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=rjwysocki.net; spf=pass smtp.mailfrom=rjwysocki.net; dkim=pass (2048-bit key) header.d=rjwysocki.net header.i=@rjwysocki.net header.b=RTLFuRJk; arc=none smtp.client-ip=79.96.170.134 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=rjwysocki.net Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=rjwysocki.net Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=rjwysocki.net header.i=@rjwysocki.net header.b="RTLFuRJk" Received: from localhost (127.0.0.1) (HELO v370.home.net.pl) by /usr/run/smtp (/usr/run/postfix/private/idea_relay_lmtp) via UNIX with SMTP (IdeaSmtpServer 6.2.1) id ec84bb99580961bd; Thu, 6 Feb 2025 15:29:24 +0100 Received: from kreacher.localnet (unknown [195.136.19.94]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by cloudserver094114.home.pl (Postfix) with ESMTPSA id 71ED26BA970; Thu, 6 Feb 2025 15:29:23 +0100 (CET) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=rjwysocki.net; s=dkim; t=1738852163; bh=ixHGPp5ZLF5maWj/njvU5xlymHep1GI46tlAYLZj4Vc=; h=From:Subject:Date; b=RTLFuRJkG98k8S1KWQNxTR51aOBdRiU9P17oihnhD24Ik2oXoHR28lSgJdkyyP16l tWW7B4ruTugSgRbOWwkbZ2biz3onCS4NbgjPrtvx2SGhhtUuSvojzhpG4Rt+bf5QgW Hlk6Np27FT0nCVUU8uv5vb4oExMGTrfLA+3pSutxZe35JfSC9M1mANPgX6IC99k3kq rQVkNDYw5sOGr/QIbsKyabyG1gpsZr3jZuj0MGb1ukjGM+th8Qs47Z2ZicQcmdmDtm T7IunpvsVTWjrH1Ibq/ZAEEk4FkFJgjZOcGhvr4OU6TLQTEWm4Ijq96ELTvfcCPxnP ZBrcq+0i54JTg== From: "Rafael J. Wysocki" To: Linux PM Cc: LKML , Daniel Lezcano , Christian Loehle , Artem Bityutskiy , Aboorva Devarajan Subject: [RFT][PATCH v1 3/5] cpuidle: menu: Tweak threshold use in get_typical_interval() Date: Thu, 06 Feb 2025 15:25:18 +0100 Message-ID: <8490144.T7Z3S40VBb@rjwysocki.net> In-Reply-To: <1916668.tdWV9SEqCh@rjwysocki.net> References: <1916668.tdWV9SEqCh@rjwysocki.net> Precedence: bulk X-Mailing-List: linux-pm@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-CLIENT-IP: 195.136.19.94 X-CLIENT-HOSTNAME: 195.136.19.94 X-VADE-SPAMSTATE: clean X-VADE-SPAMCAUSE: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgddvieeifecutefuodetggdotefrodftvfcurfhrohhfihhlvgemucfjqffogffrnfdpggftiffpkfenuceurghilhhouhhtmecuudehtdenucesvcftvggtihhpihgvnhhtshculddquddttddmnecujfgurhephffvvefufffkjghfggfgtgesthfuredttddtjeenucfhrhhomhepfdftrghfrggvlhculfdrucghhihsohgtkhhifdcuoehrjhifsehrjhifhihsohgtkhhirdhnvghtqeenucggtffrrghtthgvrhhnpedvffeuiedtgfdvtddugeeujedtffetteegfeekffdvfedttddtuefhgeefvdejhfenucfkphepudelhedrudefiedrudelrdelgeenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepihhnvghtpeduleehrddufeeirdduledrleegpdhhvghlohepkhhrvggrtghhvghrrdhlohgtrghlnhgvthdpmhgrihhlfhhrohhmpehrjhifsehrjhifhihsohgtkhhirdhnvghtpdhnsggprhgtphhtthhopeeipdhrtghpthhtoheplhhinhhugidqphhmsehvghgvrhdrkhgvrhhnvghlrdhorhhgpdhrtghpthhtoheplhhinhhugidqkhgvrhhnvghlsehvghgvrhdrkhgvrhhnvghlrdhorhhgpdhrtghpthhtohepuggrnhhivghlrdhlvgiitggrnhhosehlihhnrghrohdrohhrghdprhgtphhtthhopegthhhrihhsthhirghnrdhlohgvhhhlvgesrghrmhdrtghomhdprhgtphhtthhopegrrhhtvghmrdgsihhthihuthhskhhihieslhh X-DCC--Metrics: v370.home.net.pl 1024; Body=6 Fuz1=6 Fuz2=6 From: Rafael J. Wysocki To prepare get_typical_interval() for subsequent changes, rearrange the use of the data point threshold in it a bit and initialize that threshold to UINT_MAX which is more consistent with its data type. No intentional functional impact. Signed-off-by: Rafael J. Wysocki --- drivers/cpuidle/governors/menu.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) --- a/drivers/cpuidle/governors/menu.c +++ b/drivers/cpuidle/governors/menu.c @@ -116,7 +116,7 @@ */ static unsigned int get_typical_interval(struct menu_device *data) { - unsigned int max, divisor, thresh = INT_MAX; + unsigned int max, divisor, thresh = UINT_MAX; u64 avg, variance, avg_sq; int i; @@ -129,8 +129,8 @@ for (i = 0; i < INTERVALS; i++) { unsigned int value = data->intervals[i]; - /* Discard data points above the threshold. */ - if (value > thresh) + /* Discard data points above or at the threshold. */ + if (value >= thresh) continue; divisor++; @@ -186,7 +186,7 @@ if ((divisor * 4) <= INTERVALS * 3) return UINT_MAX; - thresh = max - 1; + thresh = max; goto again; } From patchwork Thu Feb 6 14:26:41 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Rafael J. Wysocki" X-Patchwork-Id: 862863 Received: from cloudserver094114.home.pl (cloudserver094114.home.pl [79.96.170.134]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 407791EDA2D; Thu, 6 Feb 2025 14:29:30 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=79.96.170.134 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738852173; cv=none; b=JLiiu9jpkxOHePes0wok0Kj27mrauakmXpvNU5M11B+vIoFvkYEIA3sXzD62K0+xqpDNKCJU3tvXMEC98n5bRO7Ua6bA8MegIQZLfFqz1RI0SyhUd5ZTtnvHe8jLu3R3ff+GDUuFXidB1MONjOS+/6f0OETYajJ3Y+wRTyPOQJM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738852173; c=relaxed/simple; bh=c6+9YDdlax32s2h1vFLHMmcCQPkXHYB7zhzdG4X1org=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=CCNw+FTUs/15s4oAvHRYe+mnQ4ULqDBIebYTZ/gCpELz2dkclU7z8VxJ7PtUefv5JVtatrURSGIf8ta8FzKEEXtr8WyfzAu/OVgZmIw+j3/a77r/Ymj3OYFX7Vl26DZl0Axu2DDn0m/+4B+NsqgMDnA24NgXV85kSNt2pSS8FZc= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=rjwysocki.net; spf=pass smtp.mailfrom=rjwysocki.net; dkim=pass (2048-bit key) header.d=rjwysocki.net header.i=@rjwysocki.net header.b=U27uTiQ5; arc=none smtp.client-ip=79.96.170.134 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=rjwysocki.net Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=rjwysocki.net Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=rjwysocki.net header.i=@rjwysocki.net header.b="U27uTiQ5" Received: from localhost (127.0.0.1) (HELO v370.home.net.pl) by /usr/run/smtp (/usr/run/postfix/private/idea_relay_lmtp) via UNIX with SMTP (IdeaSmtpServer 6.2.1) id e8b876c6155304fe; Thu, 6 Feb 2025 15:29:23 +0100 Received: from kreacher.localnet (unknown [195.136.19.94]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by cloudserver094114.home.pl (Postfix) with ESMTPSA id 972086BA972; Thu, 6 Feb 2025 15:29:22 +0100 (CET) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=rjwysocki.net; s=dkim; t=1738852163; bh=c6+9YDdlax32s2h1vFLHMmcCQPkXHYB7zhzdG4X1org=; h=From:Subject:Date; b=U27uTiQ5XTk9X9OnNac31KZQ9wAkdXowr2LRZ5I7IEMqQKZ5aKyeU8IcgrQr4hJF2 lpd0F8Jy1SwwlSsgzrHhU15v+4hzw45xQiyhk3sm3P53R8+AfmCacNKrpukPGuNFCO IiJq7YCQlFuOCpshCLuYYZJ93evorVI+Rth5dVar3Zg27XazwJswTPySaiOmSs9JcY Z1CRC3Pzu7hqoPPnzgXBAD/r3b549X42k1wHZ2rhFNg1mRYPZe3EWWa50CTaNWYRJf DwKjwoJLXf1tkHyrRbJTqPFWnsILvvrIy8vnMJWN4VaXVAO/RopR3dizkXZHLBPX51 WUq1CssY0ZXxA== From: "Rafael J. Wysocki" To: Linux PM Cc: LKML , Daniel Lezcano , Christian Loehle , Artem Bityutskiy , Aboorva Devarajan Subject: [RFT][PATCH v1 4/5] cpuidle: menu: Eliminate outliers on both ends of the sample set Date: Thu, 06 Feb 2025 15:26:41 +0100 Message-ID: <2301940.iZASKD2KPV@rjwysocki.net> In-Reply-To: <1916668.tdWV9SEqCh@rjwysocki.net> References: <1916668.tdWV9SEqCh@rjwysocki.net> Precedence: bulk X-Mailing-List: linux-pm@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-CLIENT-IP: 195.136.19.94 X-CLIENT-HOSTNAME: 195.136.19.94 X-VADE-SPAMSTATE: clean X-VADE-SPAMCAUSE: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgddvieeifecutefuodetggdotefrodftvfcurfhrohhfihhlvgemucfjqffogffrnfdpggftiffpkfenuceurghilhhouhhtmecuudehtdenucesvcftvggtihhpihgvnhhtshculddquddttddmnecujfgurhephffvvefufffkjghfggfgtgesthfuredttddtjeenucfhrhhomhepfdftrghfrggvlhculfdrucghhihsohgtkhhifdcuoehrjhifsehrjhifhihsohgtkhhirdhnvghtqeenucggtffrrghtthgvrhhnpedvffeuiedtgfdvtddugeeujedtffetteegfeekffdvfedttddtuefhgeefvdejhfenucfkphepudelhedrudefiedrudelrdelgeenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepihhnvghtpeduleehrddufeeirdduledrleegpdhhvghlohepkhhrvggrtghhvghrrdhlohgtrghlnhgvthdpmhgrihhlfhhrohhmpehrjhifsehrjhifhihsohgtkhhirdhnvghtpdhnsggprhgtphhtthhopeeipdhrtghpthhtoheplhhinhhugidqphhmsehvghgvrhdrkhgvrhhnvghlrdhorhhgpdhrtghpthhtoheplhhinhhugidqkhgvrhhnvghlsehvghgvrhdrkhgvrhhnvghlrdhorhhgpdhrtghpthhtohepuggrnhhivghlrdhlvgiitggrnhhosehlihhnrghrohdrohhrghdprhgtphhtthhopegthhhrihhsthhirghnrdhlohgvhhhlvgesrghrmhdrtghomhdprhgtphhtthhopegrrhhtvghmrdgsihhthihuthhskhhihieslhh X-DCC--Metrics: v370.home.net.pl 1024; Body=6 Fuz1=6 Fuz2=6 From: Rafael J. Wysocki Currently, get_typical_interval() attempts to eliminate outliers at the high end of the sample set only (probably in order to bias the prediction toward lower values), but this it problematic because if the outliers are present at the low end of the sample set, discarding the highest values will not help to reduce the variance. Since the presence of outliers at the low end of the sample set is generally as likely as their presence at the high end of the sample set, modify get_typical_interval() to treat samples at the largest distances from the average (on both ends of the sample set) as outliers. This should increase the likelihood of making a meaningful prediction in some cases. Signed-off-by: Rafael J. Wysocki --- drivers/cpuidle/governors/menu.c | 32 ++++++++++++++++++++++---------- 1 file changed, 22 insertions(+), 10 deletions(-) --- a/drivers/cpuidle/governors/menu.c +++ b/drivers/cpuidle/governors/menu.c @@ -116,30 +116,37 @@ */ static unsigned int get_typical_interval(struct menu_device *data) { - unsigned int max, divisor, thresh = UINT_MAX; + s64 value, min_thresh = -1, max_thresh = UINT_MAX; + unsigned int max, min, divisor; u64 avg, variance, avg_sq; int i; again: /* Compute the average and variance of past intervals. */ max = 0; + min = UINT_MAX; avg = 0; variance = 0; divisor = 0; for (i = 0; i < INTERVALS; i++) { - unsigned int value = data->intervals[i]; - - /* Discard data points above or at the threshold. */ - if (value >= thresh) + value = data->intervals[i]; + /* + * Discard the samples outside the interval between the min and + * max thresholds. + */ + if (value <= min_thresh || value >= max_thresh) continue; divisor++; avg += value; - variance += (u64)value * value; + variance += value * value; if (value > max) max = value; + + if (value < min) + min = value; } if (!max) @@ -175,10 +182,10 @@ } /* - * If we have outliers to the upside in our distribution, discard - * those by setting the threshold to exclude these outliers, then + * If there are outliers, discard them by setting thresholds to exclude + * data points at a large enough distance from the average, then * calculate the average and standard deviation again. Once we get - * down to the bottom 3/4 of our samples, stop excluding samples. + * down to the last 3/4 of our samples, stop excluding samples. * * This can deal with workloads that have long pauses interspersed * with sporadic activity with a bunch of short pauses. @@ -186,7 +193,12 @@ if ((divisor * 4) <= INTERVALS * 3) return UINT_MAX; - thresh = max; + /* Update the thresholds for the next round. */ + if (avg - min > max - avg) + min_thresh = min; + else + max_thresh = max; + goto again; } From patchwork Thu Feb 6 14:29:05 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Rafael J. Wysocki" X-Patchwork-Id: 863208 Received: from cloudserver094114.home.pl (cloudserver094114.home.pl [79.96.170.134]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id DA5641EDA1E; Thu, 6 Feb 2025 14:29:29 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=79.96.170.134 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738852172; cv=none; b=DAMFQlqk0zUEX795M/LVSn4j97KreRA7fLnbAwWTZGsHMgkgNG51wHmob/YvvpfaMstzqtvzUWNuBFHw0L/VhHgbEQ+8SCQBRQnai4Kk1T6lqDjhVZWR2c2Zpl8Q5zuXecL7jtMvVAH5z9hgDvJSwvEAtyr/ywaG8FGqwVBTwbY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738852172; c=relaxed/simple; bh=s4fYyLyjkEC7Fy+w4j20uWWWPaHGIYLuHi2FBghOMcE=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=Q+9dHBIK8Pm9hIZXlerGJ2CimtKfmuPsGAhH48sbsHOwbx2DlJECPMRTQuajIuDXekVP/1nY9zE65NinpXVSO4aCp7JVDg95lZqEUfZ0GMOfH0iLcsiBjo0+uzUKTR8xRwtz6qxadJWmQhMVPE0SsknJTXePAcDsbYjzgy3/kHw= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=rjwysocki.net; spf=pass smtp.mailfrom=rjwysocki.net; dkim=pass (2048-bit key) header.d=rjwysocki.net header.i=@rjwysocki.net header.b=dn6b/MsZ; arc=none smtp.client-ip=79.96.170.134 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=rjwysocki.net Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=rjwysocki.net Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=rjwysocki.net header.i=@rjwysocki.net header.b="dn6b/MsZ" Received: from localhost (127.0.0.1) (HELO v370.home.net.pl) by /usr/run/smtp (/usr/run/postfix/private/idea_relay_lmtp) via UNIX with SMTP (IdeaSmtpServer 6.2.1) id 8ca5d26d5c476b4d; Thu, 6 Feb 2025 15:29:22 +0100 Received: from kreacher.localnet (unknown [195.136.19.94]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by cloudserver094114.home.pl (Postfix) with ESMTPSA id B37A36BA970; Thu, 6 Feb 2025 15:29:21 +0100 (CET) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=rjwysocki.net; s=dkim; t=1738852162; bh=s4fYyLyjkEC7Fy+w4j20uWWWPaHGIYLuHi2FBghOMcE=; h=From:Subject:Date; b=dn6b/MsZY4+k5w2oFAfupE3RW0OtWKkE4SdHxFXNua+i2A5w2VN/65xZ3u4EtOEhe 5yY2vpZiEWXMb/EtgGe8swrkOzyxaxjdxqhj66Tp2hQ7S2E8QdRHorl7fNK16DpyWW Dbp/x+n4VJw5N511ydfFjR4wFyJxohBdjASQrERs7Om1db7fUxyrpl1GudBJjbVI2W dhFRXcNUvHSMJBjTDAFkuuar/RuYT1By5JYqdQwblwZ8w5UNC2BZgoo5acWC42u6WD hIFacbn70pquX3iJKg74FBM+WiDVWCGjRb4qntgwrGlIB8YEckUdR3wHzuhm9wgjxp G87BXqUi4eZUA== From: "Rafael J. Wysocki" To: Linux PM Cc: LKML , Daniel Lezcano , Christian Loehle , Artem Bityutskiy , Aboorva Devarajan Subject: [RFT][PATCH v1 5/5] cpuidle: menu: Avoid discarding useful information Date: Thu, 06 Feb 2025 15:29:05 +0100 Message-ID: <7770672.EvYhyI6sBW@rjwysocki.net> In-Reply-To: <1916668.tdWV9SEqCh@rjwysocki.net> References: <1916668.tdWV9SEqCh@rjwysocki.net> Precedence: bulk X-Mailing-List: linux-pm@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-CLIENT-IP: 195.136.19.94 X-CLIENT-HOSTNAME: 195.136.19.94 X-VADE-SPAMSTATE: clean X-VADE-SPAMCAUSE: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgddvieeifecutefuodetggdotefrodftvfcurfhrohhfihhlvgemucfjqffogffrnfdpggftiffpkfenuceurghilhhouhhtmecuudehtdenucesvcftvggtihhpihgvnhhtshculddquddttddmnecujfgurhephffvvefufffkjghfggfgtgesthfuredttddtjeenucfhrhhomhepfdftrghfrggvlhculfdrucghhihsohgtkhhifdcuoehrjhifsehrjhifhihsohgtkhhirdhnvghtqeenucggtffrrghtthgvrhhnpedvffeuiedtgfdvtddugeeujedtffetteegfeekffdvfedttddtuefhgeefvdejhfenucfkphepudelhedrudefiedrudelrdelgeenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepihhnvghtpeduleehrddufeeirdduledrleegpdhhvghlohepkhhrvggrtghhvghrrdhlohgtrghlnhgvthdpmhgrihhlfhhrohhmpehrjhifsehrjhifhihsohgtkhhirdhnvghtpdhnsggprhgtphhtthhopeeipdhrtghpthhtoheplhhinhhugidqphhmsehvghgvrhdrkhgvrhhnvghlrdhorhhgpdhrtghpthhtoheplhhinhhugidqkhgvrhhnvghlsehvghgvrhdrkhgvrhhnvghlrdhorhhgpdhrtghpthhtohepuggrnhhivghlrdhlvgiitggrnhhosehlihhnrghrohdrohhrghdprhgtphhtthhopegthhhrihhsthhirghnrdhlohgvhhhlvgesrghrmhdrtghomhdprhgtphhtthhopegrrhhtvghmrdgsihhthihuthhskhhihieslhh X-DCC--Metrics: v370.home.net.pl 1024; Body=6 Fuz1=6 Fuz2=6 From: Rafael J. Wysocki When giving up on making a high-confidence prediction, get_typical_interval() always returns UINT_MAX which means that the next idle interval prediction will be based entirely on the time till the next timer. However, the information represented by the most recent intervals may not be completely useless in those cases. Namely, the largest recent idle interval is an upper bound on the recently observed idle duration, so it is reasonable to assume that the next idle duration is unlikely to exceed it. Moreover, this is still true after eliminating the suspected outliers if the sample set still under consideration is at least as large as 50% of the maximum sample set size. Accordingly, make get_typical_interval() return the current maximum recent interval value in that case instead of UINT_MAX. Signed-off-by: Rafael J. Wysocki --- drivers/cpuidle/governors/menu.c | 13 ++++++++++++- 1 file changed, 12 insertions(+), 1 deletion(-) --- a/drivers/cpuidle/governors/menu.c +++ b/drivers/cpuidle/governors/menu.c @@ -190,8 +190,19 @@ * This can deal with workloads that have long pauses interspersed * with sporadic activity with a bunch of short pauses. */ - if ((divisor * 4) <= INTERVALS * 3) + if (divisor * 4 <= INTERVALS * 3) { + /* + * If there are sufficiently many data points still under + * consideration after the outliers have been eliminated, + * returning without a prediction would be a mistake because it + * is likely that the next interval will not exceed the current + * maximum, so return the latter in that case. + */ + if (divisor >= INTERVALS / 2) + return max; + return UINT_MAX; + } /* Update the thresholds for the next round. */ if (avg - min > max - avg)