[PATCH v3] sched/fair: Replace random newidle_balance with Bresenham accumulator

[PATCH v3] sched/fair: Replace random newidle_balance with Bresenham accumulator

[Qing Wang]

The current NI_RANDOM implementation uses a random dice roll to allow
newidle_balance attempts according to the success rate. There is a better
way to implement it.

Replace the random dice with a Bresenham accumulator that distributes the
allowed attempts uniformly across a 1024-step window:

Each step does the following:
  - Accumulate (1 + newidle_ratio) into newidle_window_pos.
  - If the accumulator reaches 1024, allow the balance attempt and
    subtract 1024.

This guarantees exactly (1 + newidle_ratio) newidle_balance operations per
1024 steps, uniformly spaced for any ratio in [0, 1023].

Tested-by: K Prateek Nayak <kprateek.nayak@amd.com>
Signed-off-by: Qing Wang <wangqing7171@gmail.com>
---
v2:
Removed sched_rnd_state and sched_rng() since they are no longer used.

v3:
Corrected the code comments.

Performance testing results from Prateek using tbench
(most sensitive workload for newidle balance):

    Clients:        tip                  bresenham_accm
        1      321.65 (0.00 pct)       313.97 (-2.38 pct)
        2      641.92 (0.00 pct)       638.74 (-0.49 pct)
        4     1245.65 (0.00 pct)      1237.26 (-0.67 pct)
        8     2435.80 (0.00 pct)      2442.23 ( 0.26 pct)
       16     4717.66 (0.00 pct)      4688.19 (-0.62 pct)
       32     9303.53 (0.00 pct)      9390.71 ( 0.93 pct)
       64    18002.57 (0.00 pct)     17911.56 (-0.50 pct)
      128    27729.26 (0.00 pct)     27621.95 (-0.38 pct)
      256    47134.77 (0.00 pct)     46137.36 (-2.11 pct)
      512    43179.41 (0.00 pct)     43277.53 ( 0.22 pct)
     1024    40339.30 (0.00 pct)     40176.49 (-0.40 pct)

The %diff is within the noise range, indicating no performance regression.


 include/linux/sched/topology.h |  1 +
 kernel/sched/core.c            |  3 ---
 kernel/sched/fair.c            | 19 ++++++++++++++-----
 kernel/sched/sched.h           |  6 ------
 kernel/sched/topology.c        |  1 +
 5 files changed, 16 insertions(+), 14 deletions(-)

diff --git a/include/linux/sched/topology.h b/include/linux/sched/topology.h
index f96812d71c51..e951d6f3fb0d 100644
--- a/include/linux/sched/topology.h
+++ b/include/linux/sched/topology.h
@@ -113,6 +113,7 @@ struct sched_domain {
 	unsigned int newidle_call;
 	unsigned int newidle_success;
 	unsigned int newidle_ratio;
+	unsigned int newidle_window_pos;
 	u64 newidle_stamp;
 	u64 max_newidle_lb_cost;
 	unsigned long last_decay_max_lb_cost;
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 1754d9f95f2c..4d764e68897c 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -128,7 +128,6 @@ EXPORT_TRACEPOINT_SYMBOL_GPL(sched_dl_server_start_tp);
 EXPORT_TRACEPOINT_SYMBOL_GPL(sched_dl_server_stop_tp);
 
 DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
-DEFINE_PER_CPU(struct rnd_state, sched_rnd_state);
 
 #ifdef CONFIG_SCHED_PROXY_EXEC
 DEFINE_STATIC_KEY_TRUE(__sched_proxy_exec);
@@ -8927,8 +8926,6 @@ void __init sched_init_smp(void)
 {
 	sched_init_numa(NUMA_NO_NODE);
 
-	prandom_init_once(&sched_rnd_state);
-
 	/*
 	 * There's no userspace yet to cause hotplug operations; hence all the
 	 * CPU masks are stable and all blatant races in the below code cannot
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 0f2364479f9d..172c4b53c11a 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -14198,6 +14198,7 @@ static inline void update_newidle_stats(struct sched_domain *sd, unsigned int su
 		ratio += sd->newidle_success;
 
 		sd->newidle_ratio = min(1024, ratio);
+		sd->newidle_window_pos = 0;
 		sd->newidle_call /= 2;
 		sd->newidle_success /= 2;
 	}
@@ -14928,16 +14929,24 @@ static int sched_balance_newidle(struct rq *this_rq, struct rq_flags *rf)
 
 			if (sched_feat(NI_RANDOM) && sd->newidle_ratio < 1024) {
 				/*
-				 * Throw a 1k sided dice; and only run
-				 * newidle_balance according to the success
-				 * rate.
+				 * Bresenham's line algorithm based accumulator
+				 *
+				 * At each invocation, the ratio is added to an
+				 * accumulator. A balance is triggered whenever
+				 * the sum >= 1024.
+				 *
+				 * This guarantees exactly 'ratio' balance
+				 * operations per 1024 calls, distributing them
+				 * as uniformly as possible across the interval.
 				 */
-				u32 d1k = sched_rng() % 1024;
 				weight = 1 + sd->newidle_ratio;
-				if (d1k > weight) {
+
+				sd->newidle_window_pos += weight;
+				if (sd->newidle_window_pos < 1024) {
 					update_newidle_stats(sd, 0);
 					continue;
 				}
+				sd->newidle_window_pos -= 1024;
 				weight = (1024 + weight/2) / weight;
 			}
 
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 4c25fbe84fb5..210aa35b5720 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -1424,12 +1424,6 @@ static inline bool is_migration_disabled(struct task_struct *p)
 }
 
 DECLARE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
-DECLARE_PER_CPU(struct rnd_state, sched_rnd_state);
-
-static inline u32 sched_rng(void)
-{
-	return prandom_u32_state(this_cpu_ptr(&sched_rnd_state));
-}
 
 static __always_inline struct rq *__this_rq(void)
 {
diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
index 3dab0253976f..8cc5315a6945 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -1984,6 +1984,7 @@ sd_init(struct sched_domain_topology_level *tl,
 		.newidle_call		= 512,
 		.newidle_success	= 256,
 		.newidle_ratio		= 512,
+		.newidle_window_pos	= 0,
 		.newidle_stamp		= now,
 
 		.max_newidle_lb_cost	= 0,
-- 
2.34.1

Re: [PATCH v3] sched/fair: Replace random newidle_balance with Bresenham accumulator

[Kayra Cizmeci]

On Wed, Oct 28, 2026 at 11:44:49AM +0800, Qing Wang wrote:
> The current NI_RANDOM implementation uses a random dice roll to allow
> newidle_balance attempts according to the success rate. There is a better
> way to implement it.
> 
> Replace the random dice with a Bresenham accumulator that distributes the
> allowed attempts uniformly across a 1024-step window:
> 
> Each step does the following:
>   - Accumulate (1 + newidle_ratio) into newidle_window_pos.
>   - If the accumulator reaches 1024, allow the balance attempt and
>     subtract 1024.
> 
> This guarantees exactly (1 + newidle_ratio) newidle_balance operations per
> 1024 steps, uniformly spaced for any ratio in [0, 1023].

I still quite don't understand why we need this. If there's not a gain,
the old code is simpler. I'm not against this but still I'm just asking.
Changelog just says "better way to implement it" but doesn't say why
it is better.

> 
> Tested-by: K Prateek Nayak <kprateek.nayak@amd.com>
> Signed-off-by: Qing Wang <wangqing7171@gmail.com>
> ---
> v2:
> Removed sched_rnd_state and sched_rng() since they are no longer used.
> 
> v3:
> Corrected the code comments.
> 
> Performance testing results from Prateek using tbench
> (most sensitive workload for newidle balance):
> 
>     Clients:        tip                  bresenham_accm
>         1      321.65 (0.00 pct)       313.97 (-2.38 pct)
>         2      641.92 (0.00 pct)       638.74 (-0.49 pct)
>         4     1245.65 (0.00 pct)      1237.26 (-0.67 pct)
>         8     2435.80 (0.00 pct)      2442.23 ( 0.26 pct)
>        16     4717.66 (0.00 pct)      4688.19 (-0.62 pct)
>        32     9303.53 (0.00 pct)      9390.71 ( 0.93 pct)
>        64    18002.57 (0.00 pct)     17911.56 (-0.50 pct)
>       128    27729.26 (0.00 pct)     27621.95 (-0.38 pct)
>       256    47134.77 (0.00 pct)     46137.36 (-2.11 pct)
>       512    43179.41 (0.00 pct)     43277.53 ( 0.22 pct)
>      1024    40339.30 (0.00 pct)     40176.49 (-0.40 pct)
> 
> The %diff is within the noise range, indicating no performance regression.
> 
> 
>  include/linux/sched/topology.h |  1 +
>  kernel/sched/core.c            |  3 ---
>  kernel/sched/fair.c            | 19 ++++++++++++++-----
>  kernel/sched/sched.h           |  6 ------
>  kernel/sched/topology.c        |  1 +
>  5 files changed, 16 insertions(+), 14 deletions(-)
> 
> diff --git a/include/linux/sched/topology.h b/include/linux/sched/topology.h
> index f96812d71c51..e951d6f3fb0d 100644
> --- a/include/linux/sched/topology.h
> +++ b/include/linux/sched/topology.h
> @@ -113,6 +113,7 @@ struct sched_domain {
>  	unsigned int newidle_call;
>  	unsigned int newidle_success;
>  	unsigned int newidle_ratio;
> +	unsigned int newidle_window_pos;
>  	u64 newidle_stamp;
>  	u64 max_newidle_lb_cost;
>  	unsigned long last_decay_max_lb_cost;
> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> index 1754d9f95f2c..4d764e68897c 100644
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -128,7 +128,6 @@ EXPORT_TRACEPOINT_SYMBOL_GPL(sched_dl_server_start_tp);
>  EXPORT_TRACEPOINT_SYMBOL_GPL(sched_dl_server_stop_tp);
>  
>  DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
> -DEFINE_PER_CPU(struct rnd_state, sched_rnd_state);
>  
>  #ifdef CONFIG_SCHED_PROXY_EXEC
>  DEFINE_STATIC_KEY_TRUE(__sched_proxy_exec);
> @@ -8927,8 +8926,6 @@ void __init sched_init_smp(void)
>  {
>  	sched_init_numa(NUMA_NO_NODE);
>  
> -	prandom_init_once(&sched_rnd_state);
> -
>  	/*
>  	 * There's no userspace yet to cause hotplug operations; hence all the
>  	 * CPU masks are stable and all blatant races in the below code cannot
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 0f2364479f9d..172c4b53c11a 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -14198,6 +14198,7 @@ static inline void update_newidle_stats(struct sched_domain *sd, unsigned int su
>  		ratio += sd->newidle_success;
>  
>  		sd->newidle_ratio = min(1024, ratio);
> +		sd->newidle_window_pos = 0;

Why do we need to make this 0? We need
512 calls for this to happen. But for balance to run we need
newidle_window_pos to be 1024.

So, we reset newidle_window_pos per 512 calls but we need it to be 1024
in order for balance to work When weight is 1, the newidle balance just
doesn't run.

Or am I missing something :-)?



Thanks,

Kayra

Re: [PATCH v3] sched/fair: Replace random newidle_balance with Bresenham accumulator

[Peter Zijlstra]

On Wed, Oct 28, 2026 at 11:44:49AM +0800, Qing Wang wrote:
> The current NI_RANDOM implementation uses a random dice roll to allow
> newidle_balance attempts according to the success rate. There is a better
> way to implement it.

Well, sorta. So Bresenham is a linear algorithm; it doesn't (and cannot)
properly deal with slope changes, and that is exactly what we do here.

Your solution:

> @@ -14198,6 +14198,7 @@ static inline void update_newidle_stats(struct sched_domain *sd, unsigned int su
>  		ratio += sd->newidle_success;
>  
>  		sd->newidle_ratio = min(1024, ratio);
> +		sd->newidle_window_pos = 0;
>  		sd->newidle_call /= 2;
>  		sd->newidle_success /= 2;
>  	}

is to simply delete the residual on slope change. If we were drawing
actual lines (like Bresenham was), everybody would be yelling at you for
creating jaggies.

Now, we can rescale the residual, but realistically this probably
doesn't matter.

> Replace the random dice with a Bresenham accumulator that distributes the
> allowed attempts uniformly across a 1024-step window:
> 
> Each step does the following:
>   - Accumulate (1 + newidle_ratio) into newidle_window_pos.
>   - If the accumulator reaches 1024, allow the balance attempt and
>     subtract 1024.
> 
> This guarantees exactly (1 + newidle_ratio) newidle_balance operations per
> 1024 steps, uniformly spaced for any ratio in [0, 1023].

Right, except you get the boundaries wrong. Also; as you mention, the
new pattern is uniform, which might (but probably doesn't) matter.

But the thing is; you didn't call out any of this. Can you please update
the Changelog to be explicit about these things and argue why it doesn't
matter.