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