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

[Qing Wang <wangqing7171@gmail.com>]

Hi Peter,

Thanks for the review. The newidle balance throttling you added is a
really nice optimization. I only have a slightly different view on
how to implement it.

On Wed, 28 Oct 2026 at 17:05, Peter Zijlstra <peterz@infradead.org> wrote:
> 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.

Sorry, the "sd->newidle_window_pos = 0" in update_newidle_stats() is
a bug and I'll send a v4 with it removed. I wrongly assumed that
newidle_ratio is updated once every 1024 calls. Since newidle_call
is halved after each update, the update actually happens every 512
calls, and the reset discards the accumulated value before it can
reach 1024.

Right, Bresenham assumes a constant slope. But the only effect of a
slope change is that the first attempt after it may come a bit earlier
or later.

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

                      accumulator    random dice
max per-window error  0.5 attempts   41 attempts (~16%)

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

I don't understand which boundaries you mean here. Could you spell
it out?

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

I'll add more explanation in the v4 changelog.

--
Best regards,
Qing