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

[Qing Wang]

On Wed, 28 Oct 2026 at 17:01, Kayra Cizmeci <kayracizmeci@xxxxxxxxx> 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.
> > 
> > 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.

Sorry for not explaining this clearly in the changelog. My reasoning is:

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. The attempts are evenly spaced, without bursts. With Bresenham the
   interval between two balance attempts is uniform, whereas with the
   random dice the number of skipped attempts follows a geometric
   distribution: at low ratios we may go for a long stretch without
   balancing, or balance several times in a row.

Also, looking through the scheduler code, I found very few places that
rely on random-number-based probabilistic decisions like this. IMHO
that approach is not a great fit for a kernel mechanism where
predictability matters. Using a window and spreading a fixed number of
allowed attempts evenly within it seems more reasonable to me.

I'll put this rationale into the changelog in the next version.

> 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 :-)?

You're right, this is a bug. I wrongly assumed that newidle_ratio is
updated once every 1024 calls, so I reset newidle_window_pos in the
update path. 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.

The reset isn't needed at all. newidle_window_pos always stays within
[0, 1024), since weight <= 1024 and we subtract 1024 whenever it
reaches the threshold, so the residue can simply carry over across
ratio updates. Dropping the reset fixes the issue. I'll send a v4 with
it removed.
--
Best regards,
Qing