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

[Chengfeng Lin]

Hi Qing and Peter,

I tested v4 with the native MMTests sembench workload on v7.3. It improves
throughput by about 2% at 815 workers, much less than the improvement from
disabling NI_RANDOM in an earlier diagnostic comparison.
These tests use the posted v4, with newidle_window_pos initialized to zero.

The machine is an i7-12700KF with 32 GiB RAM. All 20 logical CPUs are
available, including SMT and E-cores. The original benchmark binds each
worker to one logical CPU, cycling through the allowed CPUs. Its main
thread remains free to migrate and scans the work items to wake workers.
Workers do very little work before waiting again. I used sembench-ng at
26350892f66d [1], built with:

  gcc -O2 -g sembench.c -lpthread -lm -o sembench

The two native futex wake/sleep conditions are:

  ./sembench -r 30 -o 2 -t 8   -w 4
  ./sembench -r 30 -o 2 -t 815 -w 101

Here, -r 30 requests a 30-second run, -o 2 selects futex operations,
-t sets the worker-thread count, and -w limits each main-thread iteration
to at most 4 or 101 worker wakeups, respectively.

The benchmark's execution loop and affinity code are unchanged. The kernels
use full preemption, powersave with balance_performance, and Turbo enabled.

First, matched v7.3 baseline / v4 / baseline builds, using the same config
and GCC 15.2.0, gave this mean throughput in worker completions/s
(the benchmark's "burns/s"). Each column is a fresh boot with nine measured
calls per condition; NI_RANDOM and NI_RATE stay on.

  Workers      Baseline A           v4          Baseline B
        8      2,668,465         2,876,585          2,674,225
      815      1,112,251         1,136,952          1,117,457

The 815-worker gain is 1.98%, or about 22,100 additional completions/s,
with a maximum within-boot CV of 1.24% and 0.47% baseline drift.
At 8 workers the mean gain is 7.68%, but the patch group's CV is 3.32%,
so that result is less precise.

For context, the earlier same-image NI_RANDOM on / off / on comparison
used the same workload and nine measured calls per condition. The toggle
is NI_RANDOM / NO_NI_RANDOM in /sys/kernel/debug/sched/features:

  Workers      NI_RANDOM      NO_NI_RANDOM      NI_RANDOM return
        8      2,687,751         2,698,677          2,691,362
      815      1,108,891         1,367,185          1,105,461

At 815 workers, the mean gain is 23.48%, or about 260,000 additional
completions/s, relative to the mean of the two baselines; the baseline
return differs by -0.31%.
The disabled group has a 7.18% CV, but all nine runs are above both
baseline groups. The 8-worker change is +0.34%. NI_RATE and the other
features are unchanged.

I also ran separate main-thread-only perf stat diagnostics at 815 workers,
with three runs per setting. Counts cover each complete benchmark
invocation and are normalized by that run's total worker completions:

  Main-thread metric                    NI_RANDOM    NO_NI_RANDOM
  CPU time / worker completion (us)          0.673           0.593
  Context switches / 1,000 completions     286.62          242.82
  CPU migrations / 1,000 completions         0.593           1.973

CPU time per completion falls by 11.85% and context switches by 15.28%,
while migrations rise 3.33-fold. The main thread uses less CPU time and
incurs fewer context switches for the same number of worker completions,
despite migrating more. These diagnostics are separate from the clean
throughput measurements above.

For historical context, reverting 155213a2aed4 on matched v6.15.11 also
recovered throughput; migration stacks showed other CPUs pulling the
main thread through new-idle balancing. That commit raised the estimated
cost after failed attempts and has since been reverted upstream.

I hope these results are useful to the discussion. The feature toggle is
a diagnostic control, not a recommendation to disable it generally.
I'd be happy to test follow-up changes if that would help.

Thanks,
Chengfeng

[1] https://github.com/davidlohr/sembench-ng/tree/26350892f66df56e6fa06a0c7c104ef1de322136