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

[Kayra Cizmeci <kayracizmeci@gmail.com>]

Hi Qing,

On Thu, Oct 29, 2026 at 03:30:17PM +0800, Qing Wang wrote:
> On Wed, 28 Oct 2026 at 17:01, Kayra Cizmeci <kayracizmeci@gmail.com> 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.

But there are no numbers showing whether the bursts have any effect or
not.

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

IMO, I'd like to keep the current code if there are no numbers.
It isn’t worth it.

The test results of Prateek on this version don't reflect v4,
since they were taken with this bug.

BTW, this patch removes sched_rng() which breaks the build on Linus's
tree and tip:

kernel/sched/fair.c:8663:55: error: implicit declaration of function ‘sched_rng’ [-Wimplicit-function-declaration]

Thanks,

Kayra :-)