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@xxxxxxxxxxxxx> 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@xxxxxxxxxxxxx> 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