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

[K Prateek Nayak]

Hello Qing,

On 5/6/2026 8:14 AM, 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 implememte it.
> 
> Replace the random dice with a Bresenham accumulator that distributes the
> allowed attempts with uniformly spaced evenly across a 1024-step window:
> 
> Each step do those:
>   - 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 per 1024 steps
> and per newidle_balance with uniformly spaced for any ratio in [0, 1023].

I took the most sensitive workload I have for newidle balance (tbench)
and took it for a spin with these changes. Following are the results:

    Clients:        tip                  bresenham_accm
        1      321.65 (0.00 pct)       313.97 (-2.38 pct)
        2      641.92 (0.00 pct)       638.74 (-0.49 pct)
        4     1245.65 (0.00 pct)      1237.26 (-0.67 pct)
        8     2435.80 (0.00 pct)      2442.23 ( 0.26 pct)
       16     4717.66 (0.00 pct)      4688.19 (-0.62 pct)
       32     9303.53 (0.00 pct)      9390.71 ( 0.93 pct)
       64    18002.57 (0.00 pct)     17911.56 (-0.50 pct)
      128    27729.26 (0.00 pct)     27621.95 (-0.38 pct)
      256    47134.77 (0.00 pct)     46137.36 (-2.11 pct)
      512    43179.41 (0.00 pct)     43277.53 ( 0.22 pct)
     1024    40339.30 (0.00 pct)     40176.49 (-0.40 pct)

The %diff is in noise range which is a good indication that there
shouldn't be any surprises. I'll queue a run overnight to see if
there are other benchmarks that like / dislike these changes.

I'll let Peter comment on the change itself since he knows these
bits best ;-)

-- 
Thanks and Regards,
Prateek