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

[Qing Wang]

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

You're right, there are no on-machine test results yet. All I have is
the output of a Python program I just wrote that compares the accuracy
of the two algorithms.

It re-randomizes the ratio to a value in [0, 1023] every 512 calls
(the actual update interval, since newidle_call is halved after
each update) and runs 20000 windows (~10M calls):

                      Bresenham      random dice
max per-window error  0.5 attempts   41 attempts (~16%)

Bresenham has a much lower error.

the python program code
```python
import random
random.seed(1)
W=512; NW=20000
pos=0; maxerr_win_b=0; maxerr_win_r=0
for _ in range(NW):
    w = 1 + random.randrange(1024)
    ideal = W*w/1024
    fb=0; fr=0
    for _ in range(W):
        pos += w
        if pos >= 1024: pos -= 1024; fb += 1
        if random.randrange(1024) <= w-1: fr += 1
    maxerr_win_b = max(maxerr_win_b, abs(fb-ideal))
    maxerr_win_r = max(maxerr_win_r, abs(fr-ideal))
print(f"bresenham: max per-window err = {maxerr_win_b:.1f}")
print(f"random   : max per-window err = {maxerr_win_r:.1f}")
```

Hi Prateek, I'll send a v4 soon that fixes a reset bug — it just
drops the "sd->newidle_window_pos = 0;" line in update_newidle_stats().
If you want to test before v4 lands, that's the only change needed.
Could you please re-run the tbench tests on it? Thanks!
Cc: K Prateek Nayak <kprateek.nayak@xxxxxxx>

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

Sorry about that. I'll fix the build in v4.

--
Best regards,
Qing