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

[Kayra Cizmeci]

On Fri, Oct 30, 2026 at 05:19:46PM +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.
> 
> A quick simulation where the ratio jumps to a random value in
> [0, 1023] every 512 calls (20000 windows):
> 
>                       Bresenham      random dice
> max per-window error  0.5 attempts   41 attempts
> 
> The max per-window error is the max difference between the actual
> and expected number of attempts within a window; Bresenham's error
> is much smaller.
> 
> Signed-off-by: Qing Wang <wangqing7171@xxxxxxxxx>
Hi Qing,


Tested on Zen 3 with tbench (8 cores, 16 threads) 5 runs:

C = Client, Higher is better. MB/s.

One boot per kernel.


-C--+--------(BASE)---------+-------(PATCH)---------
 1  |     311.19 (0.00 pct) |    313.42 ( 0.72 pct)
 8  |    2097.95 (0.00 pct) |   2113.36 ( 0.73 pct)
 16 |    3271.83 (0.00 pct) |   3229.59 (-1.29 pct)
 32 |    3341.13 (0.00 pct) |   3286.98 (-1.62 pct)


stddev:
-C--+-----(BASE)--+----(PATCH)--
 1  |      0.93   |      1.07
 8  |      8.35   |     10.24
 16 |     15.06   |      7.56
 32 |      2.92   |      4.04


There's a loss at 32 Clients. Some gain at 1 clients maybe.

Still, these results don’t show a performance gain for Bresenham,
no?

Thanks,

Kayra :-).