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@xxxxxxx>
> Signed-off-by: Qing Wang <wangqing7171@xxxxxxxxx>
> ---
> 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