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

[PATCH v4] 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. This can be
replaced with a Bresenham accumulator.

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

Why Bresenham:
1. It is deterministic and reproducible. For a given ratio, the
   balance frequency is exact and not subject to random variance,
   which makes the behavior predictable when debugging or tracing.
2. Bresenham spaces the attempts evenly; the random dice can go for
   a long stretch without balancing or fire several times in a row,
   especially at low ratios.

A quick simulation where the ratio jumps to a random value in
[0, 1023] every 512 calls (20000 windows):

                      Bresenham      random dice
max per-window error  0.5 attempts   41 attempts

The max per-window error is the max difference between the actual
and expected number of attempts within a window; Bresenham's error
is much smaller.

Signed-off-by: Qing Wang <wangqing7171@gmail.com>
---
v1: https://lore.kernel.org/all/20260506024455.2799069-1-wangqing7171@gmail.com/

v2: https://lore.kernel.org/all/20260602054619.637201-1-wangqing7171@gmail.com/
Removed sched_rnd_state and sched_rng() since they are no longer used.

v3: https://lore.kernel.org/all/20261028034449.2368071-1-wangqing7171@gmail.com/
Corrected the code comments.

v4:
Recovered sched_rnd_state and sched_rng().

 include/linux/sched/topology.h |  1 +
 kernel/sched/fair.c            | 18 +++++++++++++-----
 kernel/sched/topology.c        |  1 +
 3 files changed, 15 insertions(+), 5 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/fair.c b/kernel/sched/fair.c
index cfc982205b98..b2661448759c 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -14931,16 +14931,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/topology.c b/kernel/sched/topology.c
index 919d0fb00bd9..79c477b47510 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -2002,6 +2002,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 v4] sched/fair: Replace random newidle_balance with Bresenham accumulator

[K Prateek Nayak]

Hello Qing,

On 10/30/2026 2:49 PM, Qing Wang wrote:
> diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
> index 919d0fb00bd9..79c477b47510 100644
> --- a/kernel/sched/topology.c
> +++ b/kernel/sched/topology.c
> @@ -2002,6 +2002,7 @@ sd_init(struct sched_domain_topology_level *tl,
>  		.newidle_call		= 512,
>  		.newidle_success	= 256,
>  		.newidle_ratio		= 512,
> +		.newidle_window_pos	= 0,

nit.

I think this value should start in a way that allows newidle balance to run at
first attempt and then stabilize. Maybe '512; is a good number if not higher?

>  		.newidle_stamp		= now,
>  
>  		.max_newidle_lb_cost	= 0,

-- 
Thanks and Regards,
Prateek

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

[Peter Zijlstra]

On Fri, Oct 30, 2026 at 03:16:13PM +0530, K Prateek Nayak wrote:
> Hello Qing,
> 
> On 10/30/2026 2:49 PM, Qing Wang wrote:
> > diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
> > index 919d0fb00bd9..79c477b47510 100644
> > --- a/kernel/sched/topology.c
> > +++ b/kernel/sched/topology.c
> > @@ -2002,6 +2002,7 @@ sd_init(struct sched_domain_topology_level *tl,
> >  		.newidle_call		= 512,
> >  		.newidle_success	= 256,
> >  		.newidle_ratio		= 512,
> > +		.newidle_window_pos	= 0,
> 
> nit.
> 
> I think this value should start in a way that allows newidle balance to run at
> first attempt and then stabilize. Maybe '512; is a good number if not higher?

Funnily enough, treating this as an independent variable and using a
random number works and 'fixes' the slope change problems.

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

[Qing Wang]

On Fri, 30 Oct 2026 at 17:46, K Prateek Nayak <kprateek.nayak@amd.com> wrote:
> On 10/30/2026 2:49 PM, Qing Wang wrote:
> > diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
> > index 919d0fb00bd9..79c477b47510 100644
> > --- a/kernel/sched/topology.c
> > +++ b/kernel/sched/topology.c
> > @@ -2002,6 +2002,7 @@ sd_init(struct sched_domain_topology_level *tl,
> >  		.newidle_call		= 512,
> >  		.newidle_success	= 256,
> >  		.newidle_ratio		= 512,
> > +		.newidle_window_pos	= 0,
>
> nit.
>
> I think this value should start in a way that allows newidle balance to run at
> first attempt and then stabilize. Maybe '512; is a good number if not higher?

Thanks for the review.

The initial value of newidle_window_pos can be any value in [0, 1023];
it only affects when the first balance is allowed, not the spacing of
subsequent balances. I'm not sure which value is better here.

--
Best regards,
Qing

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

[Qing Wang]

On Fri, 30 Oct 2026 at 17:56, Peter Zijlstra <peterz@infradead.org> wrote:
> Funnily enough, treating this as an independent variable and using a
> random number works and 'fixes' the slope change problems.

Hi Peter,

I explained this in the v3 thread: on a slope change, carrying
newidle_window_pos over from the previous window only shifts the
first allowed balance in the new-slope window (512 calls) earlier or
later; subsequent balances are still uniformly spaced. So the
initial value can be anything — it doesn't matter.

--
Best regards,
Qing

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

[Peter Zijlstra]

On Fri, Oct 30, 2026 at 06:22:26PM +0800, Qing Wang wrote:
> On Fri, 30 Oct 2026 at 17:56, Peter Zijlstra <peterz@infradead.org> wrote:
> > Funnily enough, treating this as an independent variable and using a
> > random number works and 'fixes' the slope change problems.
> 
> Hi Peter,
> 
> I explained this in the v3 thread: on a slope change, carrying
> newidle_window_pos over from the previous window only shifts the
> first allowed balance in the new-slope window (512 calls) earlier or
> later; subsequent balances are still uniformly spaced. So the
> initial value can be anything — it doesn't matter.

It does matter; you're rounding down. If you discard two fractions that
sum up to more than a whole, you've lost a call.

Let '/' be the integer division; then (3/2 + 3/2) = 2, but (3+3)/2 = 3.

IOW integer division (flooring) does not distribute.

The result here is less newidle calls than should have happened.

You cannot argue they are equal, you can argue the difference is
irrelevant. But so far you seem unable to see this distinction :-(

Also, the uniformity isn't a feature per se, another thing I called out
earlier. One reason why uniform distribution can be detrimental is if
two CPUs end up in a synchronized pattern, then you increase contention.

Now, again, there's plenty arguments to be had why that isn't a likely
issue in this case, but you cannot blindly state that uniform is better.

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

[Kayra Cizmeci]

On Fri, Oct 30, 2026 at 05:19:46PM +0800, Qing Wang wrote:
> The current NI_RANDOM implementation uses a random dice roll to allow
> newidle_balance attempts according to the success rate. This can be
> replaced with a Bresenham accumulator.
> 
> Replace the random dice with a Bresenham accumulator. Each step does
> the following:
>   - Accumulate (1 + newidle_ratio) into newidle_window_pos(accumulator).
>   - If the accumulator reaches 1024, allow the balance attempt and
>     subtract 1024.
> 
> Why Bresenham:
> 1. It is deterministic and reproducible. For a given ratio, the
>    balance frequency is exact and not subject to random variance,
>    which makes the behavior predictable when debugging or tracing.
> 2. Bresenham spaces the attempts evenly; the random dice can go for
>    a long stretch without balancing or fire several times in a row,
>    especially at low ratios.
> 
> A quick simulation where the ratio jumps to a random value in
> [0, 1023] every 512 calls (20000 windows):
> 
>                       Bresenham      random dice
> max per-window error  0.5 attempts   41 attempts
> 
> The max per-window error is the max difference between the actual
> and expected number of attempts within a window; Bresenham's error
> is much smaller.
> 
> Signed-off-by: Qing Wang <wangqing7171@gmail.com>
Hi Qing,


Tested on Zen 3 with tbench (8 cores, 16 threads) 5 runs:

C = Client, Higher is better. MB/s.

One boot per kernel.


-C--+--------(BASE)---------+-------(PATCH)---------
 1  |     311.19 (0.00 pct) |    313.42 ( 0.72 pct)
 8  |    2097.95 (0.00 pct) |   2113.36 ( 0.73 pct)
 16 |    3271.83 (0.00 pct) |   3229.59 (-1.29 pct)
 32 |    3341.13 (0.00 pct) |   3286.98 (-1.62 pct)


stddev:
-C--+-----(BASE)--+----(PATCH)--
 1  |      0.93   |      1.07
 8  |      8.35   |     10.24
 16 |     15.06   |      7.56
 32 |      2.92   |      4.04


There's a loss at 32 Clients. Some gain at 1 clients maybe.

Still, these results don’t show a performance gain for Bresenham,
no?

Thanks,

Kayra :-).