* [PATCH] sched: fair: Improve PELT decay_load calculation comments
@ 2017-03-10 20:23 Joel Fernandes
2017-03-22 14:16 ` Peter Zijlstra
0 siblings, 1 reply; 5+ messages in thread
From: Joel Fernandes @ 2017-03-10 20:23 UTC (permalink / raw)
To: linux-kernel
Cc: Joel Fernandes, Paul Turner, Dietmar Eggemann, Juri Lelli,
Patrick Bellasi, Peter Zijlstra, Ingo Molnar
The PELT decay_load comments are a bit confusing, first of all
the 1/2^N should be (1/2)^N so that the reader doesn't get confused.
Secondly, the y^N splitting into a 2-part decay factor deserves
a better explanation. This patch improves the comments.
Cc: Paul Turner <pjt@google.com>
Cc: Dietmar Eggemann <dietmar.eggemann@arm.com>
Cc: Juri Lelli <Juri.Lelli@arm.com>
Cc: Patrick Bellasi <patrick.bellasi@arm.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Signed-off-by: Joel Fernandes <joelaf@google.com>
---
kernel/sched/fair.c | 14 +++++++++-----
1 file changed, 9 insertions(+), 5 deletions(-)
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 6559d197e08a..1e1f2d77751e 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -2761,11 +2761,15 @@ static __always_inline u64 decay_load(u64 val, u64 n)
local_n = n;
/*
- * As y^PERIOD = 1/2, we can combine
- * y^n = 1/2^(n/PERIOD) * y^(n%PERIOD)
- * With a look-up table which covers y^n (n<PERIOD)
- *
- * To achieve constant time decay_load.
+ * As y^PERIOD = 1/2, we can decay the load by 1/2
+ * for n/PERIOD number of PERIOD sized instances. Then
+ * we decay by the remaining windows in the final PERIOD,
+ * that is n%PERIOD. In other words, the decay factor
+ * y^N in terms of PERIOD becomes:
+ * y^n = (1/2)^(n/PERIOD) * y^(n%PERIOD).
+ * Since now we only need to compute powers of y where
+ * n < PERIOD, we use a look-up table for y^N (N<PERIOD).
+ * This helps achieve constant time decay_load.
*/
if (unlikely(local_n >= LOAD_AVG_PERIOD)) {
val >>= local_n / LOAD_AVG_PERIOD;
--
2.12.0.246.ga2ecc84866-goog
^ permalink raw reply related [flat|nested] 5+ messages in thread
* Re: [PATCH] sched: fair: Improve PELT decay_load calculation comments
2017-03-10 20:23 [PATCH] sched: fair: Improve PELT decay_load calculation comments Joel Fernandes
@ 2017-03-22 14:16 ` Peter Zijlstra
2017-03-22 16:35 ` Joel Fernandes
0 siblings, 1 reply; 5+ messages in thread
From: Peter Zijlstra @ 2017-03-22 14:16 UTC (permalink / raw)
To: Joel Fernandes
Cc: linux-kernel, Paul Turner, Dietmar Eggemann, Juri Lelli,
Patrick Bellasi, Ingo Molnar
On Fri, Mar 10, 2017 at 12:23:41PM -0800, Joel Fernandes wrote:
> The PELT decay_load comments are a bit confusing, first of all
> the 1/2^N should be (1/2)^N so that the reader doesn't get confused.
I'm thinking you're confused. They're identical.
(1/2)^N = (2^-1)^N = 2^-N = 1/2^N
> Secondly, the y^N splitting into a 2-part decay factor deserves
> a better explanation. This patch improves the comments.
I find its actually harder to read.
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] sched: fair: Improve PELT decay_load calculation comments
2017-03-22 14:16 ` Peter Zijlstra
@ 2017-03-22 16:35 ` Joel Fernandes
2017-03-22 17:02 ` Peter Zijlstra
0 siblings, 1 reply; 5+ messages in thread
From: Joel Fernandes @ 2017-03-22 16:35 UTC (permalink / raw)
To: Peter Zijlstra
Cc: LKML, Paul Turner, Dietmar Eggemann, Juri Lelli, Patrick Bellasi,
Ingo Molnar
On Wed, Mar 22, 2017 at 7:16 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Fri, Mar 10, 2017 at 12:23:41PM -0800, Joel Fernandes wrote:
>> The PELT decay_load comments are a bit confusing, first of all
>> the 1/2^N should be (1/2)^N so that the reader doesn't get confused.
>
> I'm thinking you're confused. They're identical.
>
> (1/2)^N = (2^-1)^N = 2^-N = 1/2^N
They are identical I know, but I meant by enclosing the 1/2 in
brackets, it is more clear that we multiply by 1/2 N times to the
first time reader - for the reason that we'd like to reduce the PELT
calculated load by 1/2 N times.
>> Secondly, the y^N splitting into a 2-part decay factor deserves
>> a better explanation. This patch improves the comments.
>
> I find its actually harder to read.
Oh, which part? Can you help improve it? Maybe I didn't word something
correctly?
Regards,
Joel
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] sched: fair: Improve PELT decay_load calculation comments
2017-03-22 16:35 ` Joel Fernandes
@ 2017-03-22 17:02 ` Peter Zijlstra
2017-03-22 19:19 ` Joel Fernandes
0 siblings, 1 reply; 5+ messages in thread
From: Peter Zijlstra @ 2017-03-22 17:02 UTC (permalink / raw)
To: Joel Fernandes
Cc: LKML, Paul Turner, Dietmar Eggemann, Juri Lelli, Patrick Bellasi,
Ingo Molnar
On Wed, Mar 22, 2017 at 09:35:43AM -0700, Joel Fernandes wrote:
> On Wed, Mar 22, 2017 at 7:16 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> > On Fri, Mar 10, 2017 at 12:23:41PM -0800, Joel Fernandes wrote:
> >> The PELT decay_load comments are a bit confusing, first of all
> >> the 1/2^N should be (1/2)^N so that the reader doesn't get confused.
> >
> > I'm thinking you're confused. They're identical.
> >
> > (1/2)^N = (2^-1)^N = 2^-N = 1/2^N
>
> They are identical I know, but I meant by enclosing the 1/2 in
> brackets, it is more clear that we multiply by 1/2 N times to the
> first time reader - for the reason that we'd like to reduce the PELT
> calculated load by 1/2 N times.
Must be me then, because I've never been confused about that. Esp. so
since the first part: y^p = 1/2, explicitly mentions half. So its clear
from the factorization that half is meant.
> >> Secondly, the y^N splitting into a 2-part decay factor deserves
> >> a better explanation. This patch improves the comments.
> >
> > I find its actually harder to read.
>
> Oh, which part? Can you help improve it? Maybe I didn't word something
> correctly?
I think the fact that there's now words actually makes it worse.
The equation very concisely shows what we do. I don't see why we need
extra words there to obscure things.
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] sched: fair: Improve PELT decay_load calculation comments
2017-03-22 17:02 ` Peter Zijlstra
@ 2017-03-22 19:19 ` Joel Fernandes
0 siblings, 0 replies; 5+ messages in thread
From: Joel Fernandes @ 2017-03-22 19:19 UTC (permalink / raw)
To: Peter Zijlstra
Cc: LKML, Paul Turner, Dietmar Eggemann, Juri Lelli, Patrick Bellasi,
Ingo Molnar
Hi Peter,
On Wed, Mar 22, 2017 at 10:02 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Wed, Mar 22, 2017 at 09:35:43AM -0700, Joel Fernandes wrote:
>> On Wed, Mar 22, 2017 at 7:16 AM, Peter Zijlstra <peterz@infradead.org> wrote:
>> > On Fri, Mar 10, 2017 at 12:23:41PM -0800, Joel Fernandes wrote:
>> >> The PELT decay_load comments are a bit confusing, first of all
>> >> the 1/2^N should be (1/2)^N so that the reader doesn't get confused.
>> >
>> > I'm thinking you're confused. They're identical.
>> >
>> > (1/2)^N = (2^-1)^N = 2^-N = 1/2^N
>>
>> They are identical I know, but I meant by enclosing the 1/2 in
>> brackets, it is more clear that we multiply by 1/2 N times to the
>> first time reader - for the reason that we'd like to reduce the PELT
>> calculated load by 1/2 N times.
>
> Must be me then, because I've never been confused about that. Esp. so
> since the first part: y^p = 1/2, explicitly mentions half. So its clear
> from the factorization that half is meant.
Yes that's true.
>> >> Secondly, the y^N splitting into a 2-part decay factor deserves
>> >> a better explanation. This patch improves the comments.
>> >
>> > I find its actually harder to read.
>>
>> Oh, which part? Can you help improve it? Maybe I didn't word something
>> correctly?
>
> I think the fact that there's now words actually makes it worse.
>
> The equation very concisely shows what we do. I don't see why we need
> extra words there to obscure things.
Ok, I agree with you and will kill this patch then. Thanks for the review.
Regards,
Joel
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2017-03-22 19:19 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-03-10 20:23 [PATCH] sched: fair: Improve PELT decay_load calculation comments Joel Fernandes
2017-03-22 14:16 ` Peter Zijlstra
2017-03-22 16:35 ` Joel Fernandes
2017-03-22 17:02 ` Peter Zijlstra
2017-03-22 19:19 ` Joel Fernandes
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).