* [PATCH v2] sched/pelt: Skip redundant decay and divisions when sched_avg is zero
@ 2026-11-17 12:50 Chris Wiseman
2026-11-17 14:41 ` Vincent Guittot
2026-11-17 15:46 ` Peter Zijlstra
0 siblings, 2 replies; 6+ messages in thread
From: Chris Wiseman @ 2026-11-17 12:50 UTC (permalink / raw)
To: Ingo Molnar, Peter Zijlstra, Juri Lelli, Vincent Guittot
Cc: Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, Qais Yousef, John Stultz,
linux-kernel, Chris Wiseman
Commit d040e0734fb3 ("schied/fair: Skip calculating @contrib without
load") skipped __accumulate_pelt_segments() inside accumulate_sum() when
load is zero, noting that ___update_load_sum() is called with load == 0
45x more often than with non-zero load.
However, when load is zero and sa->load_sum, sa->runnable_sum, and
sa->util_sum have already decayed to zero, accumulate_sum() still
executes decay_load(0, periods) three times whenever a 1024us PELT
period boundary is crossed, and ___update_load_avg() still executes
three divisions of zero (0 / divider).
In addition, update_irq_load_avg(rq, 0) unconditionally invokes
cap_scale() twice and a second ___update_load_sum(rq->clock,
&rq->avg_irq, 1, 1, 1) call even when running == 0. Because the first
___update_load_sum() call already advanced last_update_time to
rq->clock & ~1023ULL, the second call sees delta < 1024 and always
returns 0 after redundant clock and capacity scaling arithmetic.
In accumulate_sum(), when !load and !(sa->load_sum | sa->runnable_sum |
sa->util_sum), update sa->period_contrib and return periods before
Step 1. In ___update_load_avg(), set *_avg to 0 instead of dividing when
the corresponding *_sum is 0. In update_irq_load_avg(), skip the
capacity scaling and second ___update_load_sum() call when !running.
Evaluating update_other_load_avgs() over 1,000,000 randomized steps
confirms bit-for-bit identical sched_avg state and return values across
all fields, while 20,000,000-iteration microbenchmarks on x86_64 and
arm64 show:
Regime (1ms blocked-avg updates) Base (cyc) Patched (cyc) Delta
------------------------------------ ---------- ------------- ------
x86_64 Idle RT/DL/HW/IRQ 78.53 32.82 -58.2%
x86_64 100% active RT+DL+HW+IRQ 116.01 117.63 +1.4%
arm64 Idle RT/DL/HW/IRQ 77.78 37.91 -51.3%
arm64 100% active RT+DL+HW+IRQ 120.40 113.52 -5.7%
Suggested-by: Vincent Guittot <vincent.guittot@linaro.org>
Signed-off-by: Chris Wiseman <chriswiseman@google.com>
---
Changes in v2:
- Move the zero-sum fast path into accumulate_sum() before Step 1 and
still return periods (Vincent Guittot).
- Avoid dividing in ___update_load_avg() when *_sum is 0, dropping the
sa->load_avg check and the kernel/sched/fair.c change (Vincent Guittot).
- Add arm64 cycle measurements alongside x86_64.
- v1: https://lore.kernel.org/r/18e837a02ddbadb6.3137322e32332e3235332e313736.1b3220.0000sendgmr@google.com
kernel/sched/pelt.c | 25 ++++++++++++++++++-------
1 file changed, 18 insertions(+), 7 deletions(-)
diff --git a/kernel/sched/pelt.c b/kernel/sched/pelt.c
index 779eb58a4261..7308fb28b0fa 100644
--- a/kernel/sched/pelt.c
+++ b/kernel/sched/pelt.c
@@ -109,6 +109,11 @@ accumulate_sum(u64 delta, struct sched_avg *sa,
delta += sa->period_contrib;
periods = delta / 1024; /* A period is 1024us (~1ms) */
+ if (!load && !(sa->load_sum | sa->runnable_sum | sa->util_sum)) {
+ sa->period_contrib = delta % 1024;
+ return periods;
+ }
+
/*
* Step 1: decay old *_sum if we crossed period boundaries.
*/
@@ -262,9 +267,11 @@ ___update_load_avg(struct sched_avg *sa, unsigned long load)
/*
* Step 2: update *_avg.
*/
- sa->load_avg = div_u64(load * sa->load_sum, divider);
- sa->runnable_avg = div_u64(sa->runnable_sum, divider);
- WRITE_ONCE(sa->util_avg, sa->util_sum / divider);
+ sa->load_avg = sa->load_sum ? div_u64(load * sa->load_sum, divider) : 0;
+ sa->runnable_avg = sa->runnable_sum ?
+ div_u64(sa->runnable_sum, divider) : 0;
+ WRITE_ONCE(sa->util_avg,
+ sa->util_sum ? sa->util_sum / divider : 0);
}
/*
@@ -437,8 +444,10 @@ int update_irq_load_avg(struct rq *rq, u64 running)
* clock_task. Instead we directly scale the running time to
* reflect the real amount of computation
*/
- running = cap_scale(running, arch_scale_freq_capacity(cpu_of(rq)));
- running = cap_scale(running, arch_scale_cpu_capacity(cpu_of(rq)));
+ if (running) {
+ running = cap_scale(running, arch_scale_freq_capacity(cpu_of(rq)));
+ running = cap_scale(running, arch_scale_cpu_capacity(cpu_of(rq)));
+ }
/*
* We know the time that has been used by interrupt since last update
@@ -455,10 +464,12 @@ int update_irq_load_avg(struct rq *rq, u64 running)
0,
0,
0);
- ret += ___update_load_sum(rq->clock, &rq->avg_irq,
- 1,
- 1,
- 1);
+ if (running) {
+ ret += ___update_load_sum(rq->clock, &rq->avg_irq,
+ 1,
+ 1,
+ 1);
+ }
if (ret) {
___update_load_avg(&rq->avg_irq, 1);
--
2.47.0
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: [PATCH v2] sched/pelt: Skip redundant decay and divisions when sched_avg is zero
2026-11-17 12:50 [PATCH v2] sched/pelt: Skip redundant decay and divisions when sched_avg is zero Chris Wiseman
@ 2026-11-17 14:41 ` Vincent Guittot
2026-11-17 15:46 ` Peter Zijlstra
1 sibling, 0 replies; 6+ messages in thread
From: Vincent Guittot @ 2026-11-17 14:41 UTC (permalink / raw)
To: Chris Wiseman
Cc: Ingo Molnar, Peter Zijlstra, Juri Lelli, Dietmar Eggemann,
Steven Rostedt, Ben Segall, Mel Gorman, Valentin Schneider,
K Prateek Nayak, Qais Yousef, John Stultz, linux-kernel
On Tue, 17 Nov 2026 at 13:50, Chris Wiseman <chriswiseman@google.com> wrote:
>
> Commit d040e0734fb3 ("schied/fair: Skip calculating @contrib without
> load") skipped __accumulate_pelt_segments() inside accumulate_sum() when
> load is zero, noting that ___update_load_sum() is called with load == 0
> 45x more often than with non-zero load.
>
> However, when load is zero and sa->load_sum, sa->runnable_sum, and
> sa->util_sum have already decayed to zero, accumulate_sum() still
> executes decay_load(0, periods) three times whenever a 1024us PELT
> period boundary is crossed, and ___update_load_avg() still executes
> three divisions of zero (0 / divider).
>
> In addition, update_irq_load_avg(rq, 0) unconditionally invokes
> cap_scale() twice and a second ___update_load_sum(rq->clock,
> &rq->avg_irq, 1, 1, 1) call even when running == 0. Because the first
> ___update_load_sum() call already advanced last_update_time to
> rq->clock & ~1023ULL, the second call sees delta < 1024 and always
> returns 0 after redundant clock and capacity scaling arithmetic.
>
> In accumulate_sum(), when !load and !(sa->load_sum | sa->runnable_sum |
> sa->util_sum), update sa->period_contrib and return periods before
> Step 1. In ___update_load_avg(), set *_avg to 0 instead of dividing when
> the corresponding *_sum is 0. In update_irq_load_avg(), skip the
> capacity scaling and second ___update_load_sum() call when !running.
>
> Evaluating update_other_load_avgs() over 1,000,000 randomized steps
> confirms bit-for-bit identical sched_avg state and return values across
> all fields, while 20,000,000-iteration microbenchmarks on x86_64 and
> arm64 show:
>
> Regime (1ms blocked-avg updates) Base (cyc) Patched (cyc) Delta
> ------------------------------------ ---------- ------------- ------
> x86_64 Idle RT/DL/HW/IRQ 78.53 32.82 -58.2%
> x86_64 100% active RT+DL+HW+IRQ 116.01 117.63 +1.4%
> arm64 Idle RT/DL/HW/IRQ 77.78 37.91 -51.3%
> arm64 100% active RT+DL+HW+IRQ 120.40 113.52 -5.7%
>
> Suggested-by: Vincent Guittot <vincent.guittot@linaro.org>
FWIW, you can remove the suggested-by. I only commented on your v1 but
it didn't deeply change what you proposed.
> Signed-off-by: Chris Wiseman <chriswiseman@google.com>
Reviewed-by: Vincent Guittot <vincent.guittot@linaro.org>
> ---
> Changes in v2:
> - Move the zero-sum fast path into accumulate_sum() before Step 1 and
> still return periods (Vincent Guittot).
> - Avoid dividing in ___update_load_avg() when *_sum is 0, dropping the
> sa->load_avg check and the kernel/sched/fair.c change (Vincent Guittot).
> - Add arm64 cycle measurements alongside x86_64.
> - v1: https://lore.kernel.org/r/18e837a02ddbadb6.3137322e32332e3235332e313736.1b3220.0000sendgmr@google.com
>
> kernel/sched/pelt.c | 25 ++++++++++++++++++-------
> 1 file changed, 18 insertions(+), 7 deletions(-)
>
> diff --git a/kernel/sched/pelt.c b/kernel/sched/pelt.c
> index 779eb58a4261..7308fb28b0fa 100644
> --- a/kernel/sched/pelt.c
> +++ b/kernel/sched/pelt.c
> @@ -109,6 +109,11 @@ accumulate_sum(u64 delta, struct sched_avg *sa,
> delta += sa->period_contrib;
> periods = delta / 1024; /* A period is 1024us (~1ms) */
>
> + if (!load && !(sa->load_sum | sa->runnable_sum | sa->util_sum)) {
> + sa->period_contrib = delta % 1024;
> + return periods;
> + }
> +
> /*
> * Step 1: decay old *_sum if we crossed period boundaries.
> */
> @@ -262,9 +267,11 @@ ___update_load_avg(struct sched_avg *sa, unsigned long load)
> /*
> * Step 2: update *_avg.
> */
> - sa->load_avg = div_u64(load * sa->load_sum, divider);
> - sa->runnable_avg = div_u64(sa->runnable_sum, divider);
> - WRITE_ONCE(sa->util_avg, sa->util_sum / divider);
> + sa->load_avg = sa->load_sum ? div_u64(load * sa->load_sum, divider) : 0;
> + sa->runnable_avg = sa->runnable_sum ?
> + div_u64(sa->runnable_sum, divider) : 0;
> + WRITE_ONCE(sa->util_avg,
> + sa->util_sum ? sa->util_sum / divider : 0);
> }
>
> /*
> @@ -437,8 +444,10 @@ int update_irq_load_avg(struct rq *rq, u64 running)
> * clock_task. Instead we directly scale the running time to
> * reflect the real amount of computation
> */
> - running = cap_scale(running, arch_scale_freq_capacity(cpu_of(rq)));
> - running = cap_scale(running, arch_scale_cpu_capacity(cpu_of(rq)));
> + if (running) {
> + running = cap_scale(running, arch_scale_freq_capacity(cpu_of(rq)));
> + running = cap_scale(running, arch_scale_cpu_capacity(cpu_of(rq)));
> + }
>
> /*
> * We know the time that has been used by interrupt since last update
> @@ -455,10 +464,12 @@ int update_irq_load_avg(struct rq *rq, u64 running)
> 0,
> 0,
> 0);
> - ret += ___update_load_sum(rq->clock, &rq->avg_irq,
> - 1,
> - 1,
> - 1);
> + if (running) {
> + ret += ___update_load_sum(rq->clock, &rq->avg_irq,
> + 1,
> + 1,
> + 1);
> + }
>
> if (ret) {
> ___update_load_avg(&rq->avg_irq, 1);
> --
> 2.47.0
^ permalink raw reply [flat|nested] 6+ messages in thread* Re: [PATCH v2] sched/pelt: Skip redundant decay and divisions when sched_avg is zero
2026-11-17 12:50 [PATCH v2] sched/pelt: Skip redundant decay and divisions when sched_avg is zero Chris Wiseman
2026-11-17 14:41 ` Vincent Guittot
@ 2026-11-17 15:46 ` Peter Zijlstra
2026-11-17 16:05 ` Peter Zijlstra
1 sibling, 1 reply; 6+ messages in thread
From: Peter Zijlstra @ 2026-11-17 15:46 UTC (permalink / raw)
To: Chris Wiseman
Cc: Ingo Molnar, Juri Lelli, Vincent Guittot, Dietmar Eggemann,
Steven Rostedt, Ben Segall, Mel Gorman, Valentin Schneider,
K Prateek Nayak, Qais Yousef, John Stultz, linux-kernel
On Tue, Nov 17, 2026 at 12:50:01PM +0000, Chris Wiseman wrote:
> + sa->load_avg = sa->load_sum ? div_u64(load * sa->load_sum, divider) : 0;
> + sa->runnable_avg = sa->runnable_sum ?
> + div_u64(sa->runnable_sum, divider) : 0;
> + WRITE_ONCE(sa->util_avg,
> + sa->util_sum ? sa->util_sum / divider : 0);
This is micro-architectural.
Gemini is trying to sell me:
IDIV latency (32/64) Branch mispredict
Apple P-core (M4 tested): 7 13-15
AMD Zen[45]: 10-13 / 15-20 15-20
Intel Golven Cove+: 12-16 17-22
So on these architectures it is more expensive to mispredict than to
just do the division.
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH v2] sched/pelt: Skip redundant decay and divisions when sched_avg is zero
2026-11-17 15:46 ` Peter Zijlstra
@ 2026-11-17 16:05 ` Peter Zijlstra
2026-11-17 16:09 ` Vincent Guittot
0 siblings, 1 reply; 6+ messages in thread
From: Peter Zijlstra @ 2026-11-17 16:05 UTC (permalink / raw)
To: Chris Wiseman
Cc: Ingo Molnar, Juri Lelli, Vincent Guittot, Dietmar Eggemann,
Steven Rostedt, Ben Segall, Mel Gorman, Valentin Schneider,
K Prateek Nayak, Qais Yousef, John Stultz, linux-kernel
On Tue, Nov 17, 2026 at 04:46:56PM +0100, Peter Zijlstra wrote:
> On Tue, Nov 17, 2026 at 12:50:01PM +0000, Chris Wiseman wrote:
>
> > + sa->load_avg = sa->load_sum ? div_u64(load * sa->load_sum, divider) : 0;
> > + sa->runnable_avg = sa->runnable_sum ?
> > + div_u64(sa->runnable_sum, divider) : 0;
> > + WRITE_ONCE(sa->util_avg,
> > + sa->util_sum ? sa->util_sum / divider : 0);
>
> This is micro-architectural.
>
> Gemini is trying to sell me:
>
> IDIV latency (32/64) Branch mispredict
>
> Apple P-core (M4 tested): 7 13-15
> AMD Zen[45]: 10-13 / 15-20 15-20
> Intel Golven Cove+: 12-16 17-22
>
> So on these architectures it is more expensive to mispredict than to
> just do the division.
That same Gemini thing is also telling me most modern uarch should have
an early out when dividing 0 (making it cheaper still). OTOH it also
noted that if the prediction rate is near 100% the conditional might
win out because of reduced port contention.
As per obvious, if your uarch sucks at divisions its most always going
to be a win.
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH v2] sched/pelt: Skip redundant decay and divisions when sched_avg is zero
2026-11-17 16:05 ` Peter Zijlstra
@ 2026-11-17 16:09 ` Vincent Guittot
2026-11-17 16:28 ` Chris Wiseman
0 siblings, 1 reply; 6+ messages in thread
From: Vincent Guittot @ 2026-11-17 16:09 UTC (permalink / raw)
To: Peter Zijlstra
Cc: Chris Wiseman, Ingo Molnar, Juri Lelli, Dietmar Eggemann,
Steven Rostedt, Ben Segall, Mel Gorman, Valentin Schneider,
K Prateek Nayak, Qais Yousef, John Stultz, linux-kernel
On Tue, 17 Nov 2026 at 17:05, Peter Zijlstra <peterz@infradead.org> wrote:
>
> On Tue, Nov 17, 2026 at 04:46:56PM +0100, Peter Zijlstra wrote:
> > On Tue, Nov 17, 2026 at 12:50:01PM +0000, Chris Wiseman wrote:
> >
> > > + sa->load_avg = sa->load_sum ? div_u64(load * sa->load_sum, divider) : 0;
> > > + sa->runnable_avg = sa->runnable_sum ?
> > > + div_u64(sa->runnable_sum, divider) : 0;
> > > + WRITE_ONCE(sa->util_avg,
> > > + sa->util_sum ? sa->util_sum / divider : 0);
> >
> > This is micro-architectural.
> >
> > Gemini is trying to sell me:
> >
> > IDIV latency (32/64) Branch mispredict
> >
> > Apple P-core (M4 tested): 7 13-15
> > AMD Zen[45]: 10-13 / 15-20 15-20
> > Intel Golven Cove+: 12-16 17-22
> >
> > So on these architectures it is more expensive to mispredict than to
> > just do the division.
>
> That same Gemini thing is also telling me most modern uarch should have
> an early out when dividing 0 (making it cheaper still). OTOH it also
> noted that if the prediction rate is near 100% the conditional might
> win out because of reduced port contention.
Yeah it seems that arm64 has optimized div with an early exit when the
dividend is null so it would be better to always do the div
>
> As per obvious, if your uarch sucks at divisions its most always going
> to be a win.
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH v2] sched/pelt: Skip redundant decay and divisions when sched_avg is zero
2026-11-17 16:09 ` Vincent Guittot
@ 2026-11-17 16:28 ` Chris Wiseman
0 siblings, 0 replies; 6+ messages in thread
From: Chris Wiseman @ 2026-11-17 16:28 UTC (permalink / raw)
To: Vincent Guittot, Peter Zijlstra
Cc: Ingo Molnar, Juri Lelli, Dietmar Eggemann, Steven Rostedt,
Ben Segall, Mel Gorman, Valentin Schneider, K Prateek Nayak,
Qais Yousef, John Stultz, linux-kernel
On Tue, Nov 17, 2026 at 05:09:08PM +0100, Vincent Guittot wrote:
> Yeah it seems that arm64 has optimized div with an early exit when the
> dividend is null so it would be better to always do the div
Sounds like the consensus is to drop the ___update_load_avg() hunk
(and Suggested-by) and roll with just the accumulate_sum() and
update_irq_load_avg() skips in v3.
Thanks,
Chris
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2026-11-17 16:29 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2026-11-17 12:50 [PATCH v2] sched/pelt: Skip redundant decay and divisions when sched_avg is zero Chris Wiseman
2026-11-17 14:41 ` Vincent Guittot
2026-11-17 15:46 ` Peter Zijlstra
2026-11-17 16:05 ` Peter Zijlstra
2026-11-17 16:09 ` Vincent Guittot
2026-11-17 16:28 ` Chris Wiseman
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®