[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 :-).

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

[Qing Wang]

On Fri, 30 Oct 2026 at 18:39, Peter Zijlstra <peterz@infradead.org> wrote:
> 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 :-(

Thanks again for your patience.

I think we talked past each other: the lost-calls problem from repeated
rounding down is already fixed in v4 by not clearing newidle_window_pos.
The position is never reset, so the total number of balances is
floor((initial_pos + total accumulated weight) / 1024) -- the long-run
count is exact.

My last mail was only about the initial value of newidle_window_pos in
sd_init(): it shifts the timing of first balance call.

> 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.

You're right, and I'm sorry for that. I favored uniformity without a
strong argument, and I kept claiming "equivalent" where the honest claim
is "the difference is bounded" -- the distinction you point out.

Performance-wise, the uniform version should be on par with the random.
And it can indeed run into the synchronization problem you describe,
but that can be mitigated by giving each sd a different initial value.
e.g.:

    .newidle_window_pos = (cpu * 1024) / cpumask_weight(cpu_map)

That leaves the per-window deviation as the only remaining advantage,
as described in v4: the call count stays within one call of the
expected value in every window (vs up to ~41 call for the random
dice in the simulation). I understand if that alone is not enough to justify
the patch -- I'm grateful for the rounds of discussion.

--
Best regards,
Qing

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

[Chengfeng Lin]

Hi Qing and Peter,

I tested v4 with the native MMTests sembench workload on v7.3. It improves
throughput by about 2% at 815 workers, much less than the improvement from
disabling NI_RANDOM in an earlier diagnostic comparison.
These tests use the posted v4, with newidle_window_pos initialized to zero.

The machine is an i7-12700KF with 32 GiB RAM. All 20 logical CPUs are
available, including SMT and E-cores. The original benchmark binds each
worker to one logical CPU, cycling through the allowed CPUs. Its main
thread remains free to migrate and scans the work items to wake workers.
Workers do very little work before waiting again. I used sembench-ng at
26350892f66d [1], built with:

  gcc -O2 -g sembench.c -lpthread -lm -o sembench

The two native futex wake/sleep conditions are:

  ./sembench -r 30 -o 2 -t 8   -w 4
  ./sembench -r 30 -o 2 -t 815 -w 101

Here, -r 30 requests a 30-second run, -o 2 selects futex operations,
-t sets the worker-thread count, and -w limits each main-thread iteration
to at most 4 or 101 worker wakeups, respectively.

The benchmark's execution loop and affinity code are unchanged. The kernels
use full preemption, powersave with balance_performance, and Turbo enabled.

First, matched v7.3 baseline / v4 / baseline builds, using the same config
and GCC 15.2.0, gave this mean throughput in worker completions/s
(the benchmark's "burns/s"). Each column is a fresh boot with nine measured
calls per condition; NI_RANDOM and NI_RATE stay on.

  Workers      Baseline A           v4          Baseline B
        8      2,668,465         2,876,585          2,674,225
      815      1,112,251         1,136,952          1,117,457

The 815-worker gain is 1.98%, or about 22,100 additional completions/s,
with a maximum within-boot CV of 1.24% and 0.47% baseline drift.
At 8 workers the mean gain is 7.68%, but the patch group's CV is 3.32%,
so that result is less precise.

For context, the earlier same-image NI_RANDOM on / off / on comparison
used the same workload and nine measured calls per condition. The toggle
is NI_RANDOM / NO_NI_RANDOM in /sys/kernel/debug/sched/features:

  Workers      NI_RANDOM      NO_NI_RANDOM      NI_RANDOM return
        8      2,687,751         2,698,677          2,691,362
      815      1,108,891         1,367,185          1,105,461

At 815 workers, the mean gain is 23.48%, or about 260,000 additional
completions/s, relative to the mean of the two baselines; the baseline
return differs by -0.31%.
The disabled group has a 7.18% CV, but all nine runs are above both
baseline groups. The 8-worker change is +0.34%. NI_RATE and the other
features are unchanged.

I also ran separate main-thread-only perf stat diagnostics at 815 workers,
with three runs per setting. Counts cover each complete benchmark
invocation and are normalized by that run's total worker completions:

  Main-thread metric                    NI_RANDOM    NO_NI_RANDOM
  CPU time / worker completion (us)          0.673           0.593
  Context switches / 1,000 completions     286.62          242.82
  CPU migrations / 1,000 completions         0.593           1.973

CPU time per completion falls by 11.85% and context switches by 15.28%,
while migrations rise 3.33-fold. The main thread uses less CPU time and
incurs fewer context switches for the same number of worker completions,
despite migrating more. These diagnostics are separate from the clean
throughput measurements above.

For historical context, reverting 155213a2aed4 on matched v6.15.11 also
recovered throughput; migration stacks showed other CPUs pulling the
main thread through new-idle balancing. That commit raised the estimated
cost after failed attempts and has since been reverted upstream.

I hope these results are useful to the discussion. The feature toggle is
a diagnostic control, not a recommendation to disable it generally.
I'd be happy to test follow-up changes if that would help.

Thanks,
Chengfeng

[1] https://github.com/davidlohr/sembench-ng/tree/26350892f66df56e6fa06a0c7c104ef1de322136

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

[Tim Chen]

On Fri, 2026-10-30 at 17:19 +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.
> 

Hi Qing,

I think the deterministic behavior is problematic:

newidle_ratio is not a fixed setting. It is learned from the balance
attempts we actually make: if those attempts pull tasks, the ratio
goes up and we try more often; if they fail, it goes down and we try
less often.

For that to work, the attempts must be a fair sample of all the
newidle calls. In other words, the call we pick must not be biased
towards the call that tend to fail. Random picks
guarantee this. Picking every Nth call does not, because workloads
often repeat in a regular pattern, and a fixed stride can line up
with that pattern.

A simple example. Say a task is available to pull on every 4th
newidle call, so the real success rate is 1/4. If the ratio drops to
0, Bresenham attempts exactly once every 1024 calls. 1024 is a
multiple of 4, so every attempt lands on the same position in the
pattern. If that position is one of the empty calls, every attempt
fails, the ratio stays at 0, and this domain stops balancing for
good, even though 1 in 4 calls could have pulled a task. With the
random dice, about 1 in 4 attempts hits a good call, and the ratio
climbs back to the right level.

The same thing happens between CPUs. Every CPU starts its accumulator
at the same value with the same ratio, so CPUs that go idle at the
same time will all balance together or all skip together. Random
picks keep the CPUs independent, so their balancing does not end up
synchronized.

So the variance of the random dice is the price we pay for an
unbiased estimate, and I think it is worth paying. Unless there is
benchmark data showing a clear benefit (so far Kayra's tbench numbers
are roughly neutral), I think it is better to keep NI_RANDOM as it is.

Thanks,
Tim