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.