[PATCH] timers: Make the lower-level timer function first call than higher-level

[PATCH] timers: Make the lower-level timer function first call than higher-level

[Muchun Song]

The elements of the heads array are a linked list of timer events that
expire at the current time. And it can contain up to LVL_DEPTH levels
and the lower the level represents the smaller the time granularity.

Now the result is that the function, which will be called when the timer
expires, in the higher-level is called first than the lower-level function.
I think it might be better to call the lower-level timer function first
than the higher-level function. Because the lower-level has the smaller
granularity and delay has less impact on higher-level. So fix it.

Signed-off-by: Muchun Song <smuchun@gmail.com>
---
 kernel/time/timer.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index fa49cd753dea..7c757b27aa58 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -1674,12 +1674,13 @@ static inline void __run_timers(struct timer_base *base)
 	base->must_forward_clk = false;
 
 	while (time_after_eq(jiffies, base->clk)) {
+		int i;
 
 		levels = collect_expired_timers(base, heads);
 		base->clk++;
 
-		while (levels--)
-			expire_timers(base, heads + levels);
+		for (i = 0; i < levels; i++)
+			expire_timers(base, heads + i);
 	}
 	base->running_timer = NULL;
 	raw_spin_unlock_irq(&base->lock);
-- 
2.17.1

Re: [PATCH] timers: Make the lower-level timer function first call than higher-level

[John Stultz]

On Mon, Nov 19, 2018 at 6:10 AM, Muchun Song <smuchun@gmail.com> wrote:
> The elements of the heads array are a linked list of timer events that
> expire at the current time. And it can contain up to LVL_DEPTH levels
> and the lower the level represents the smaller the time granularity.
>
> Now the result is that the function, which will be called when the timer
> expires, in the higher-level is called first than the lower-level function.
> I think it might be better to call the lower-level timer function first
> than the higher-level function. Because the lower-level has the smaller
> granularity and delay has less impact on higher-level. So fix it.

Interesting.

Do you have any specific examples of where this was helpful?  Maybe
data on how much this helped the case your concerned about?

thanks
-john

Re: [PATCH] timers: Make the lower-level timer function first call than higher-level

[Muchun Song]

Hi John,

Thanks for your review.

John Stultz <john.stultz@linaro.org> 于2018年11月20日周二 上午2:16写道：
>
> On Mon, Nov 19, 2018 at 6:10 AM, Muchun Song <smuchun@gmail.com> wrote:
> > The elements of the heads array are a linked list of timer events that
> > expire at the current time. And it can contain up to LVL_DEPTH levels
> > and the lower the level represents the smaller the time granularity.
> >
> > Now the result is that the function, which will be called when the timer
> > expires, in the higher-level is called first than the lower-level function.
> > I think it might be better to call the lower-level timer function first
> > than the higher-level function. Because the lower-level has the smaller
> > granularity and delay has less impact on higher-level. So fix it.
>
> Interesting.
>
> Do you have any specific examples of where this was helpful?  Maybe
> data on how much this helped the case your concerned about?
>

                     heads(with HZ > 100)
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|  0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |
+--+--+--+--+--+--+-----+-----+-----+-----+-----+-----+
   |     |     |
   |     |     |
   |     |     +--->timer4--->timer5
   |     +--->timer1--->timer2--->timer3
   +--->timer0

If we have 6 timers that expire at the current time. And the heads array
layout as shown above. The collect_expired_timers() will return 3. If timer0
belong to the first wheel level(level 0), timer1-3 belong to level 2 and
timer4-5 belong to level 5.

Follow the current code logic, the timer0 function is called until the
function call of timer1-5 is completed. So the delay of timer0 is the time
spent by other timer function calls. If we can call the timer function in
the following order, this should be more friendly to lower-level timers.

        timer0->timer1->->timer2->->timer3->->timer4->->timer5

Although not friendly to higher-level timers, higher-level has larger
granularity. Therefore the delay has less impact on higher-level.

Is it right?

Thanks.

Re: [PATCH] timers: Make the lower-level timer function first call than higher-level

[Thomas Gleixner]

[-- Attachment #1: Type: text/plain, Size: 2276 bytes --]

Song,

On Tue, 20 Nov 2018, Muchun Song wrote:
> John Stultz <john.stultz@linaro.org> 于2018年11月20日周二 上午2:16写道：
> >
> > On Mon, Nov 19, 2018 at 6:10 AM, Muchun Song <smuchun@gmail.com> wrote:
> > > The elements of the heads array are a linked list of timer events that
> > > expire at the current time. And it can contain up to LVL_DEPTH levels
> > > and the lower the level represents the smaller the time granularity.
> > >
> > > Now the result is that the function, which will be called when the timer
> > > expires, in the higher-level is called first than the lower-level function.
> > > I think it might be better to call the lower-level timer function first
> > > than the higher-level function. Because the lower-level has the smaller
> > > granularity and delay has less impact on higher-level. So fix it.
> >
> > Interesting.
> >
> > Do you have any specific examples of where this was helpful?  Maybe
> > data on how much this helped the case your concerned about?
> >
> 
>                      heads(with HZ > 100)
> +-----+-----+-----+-----+-----+-----+-----+-----+-----+
> |  0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |
> +--+--+--+--+--+--+-----+-----+-----+-----+-----+-----+
>    |     |     |
>    |     |     |
>    |     |     +--->timer4--->timer5
>    |     +--->timer1--->timer2--->timer3
>    +--->timer0
> 
> If we have 6 timers that expire at the current time. And the heads array
> layout as shown above. The collect_expired_timers() will return 3. If timer0
> belong to the first wheel level(level 0), timer1-3 belong to level 2 and
> timer4-5 belong to level 5.
> 
> Follow the current code logic, the timer0 function is called until the
> function call of timer1-5 is completed. So the delay of timer0 is the time
> spent by other timer function calls. If we can call the timer function in
> the following order, this should be more friendly to lower-level timers.
> 
>         timer0->timer1->->timer2->->timer3->->timer4->->timer5
> 
> Although not friendly to higher-level timers, higher-level has larger
> granularity. Therefore the delay has less impact on higher-level.

Well yes, that's clear. But is it a problem in practice and if so, what is
the measurable benefit.

Thanks,

	tglx

Re: [PATCH] timers: Make the lower-level timer function first call than higher-level

[Thomas Gleixner]

Song,

On Wed, 21 Nov 2018, Thomas Gleixner wrote:
> On Tue, 20 Nov 2018, Muchun Song wrote:
> > Follow the current code logic, the timer0 function is called until the
> > function call of timer1-5 is completed. So the delay of timer0 is the time
> > spent by other timer function calls. If we can call the timer function in
> > the following order, this should be more friendly to lower-level timers.
> > 
> >         timer0->timer1->->timer2->->timer3->->timer4->->timer5
> > 
> > Although not friendly to higher-level timers, higher-level has larger
> > granularity. Therefore the delay has less impact on higher-level.
> 
> Well yes, that's clear. But is it a problem in practice and if so, what is
> the measurable benefit.

Polite reminder. Can you please describe what the practical relevance is of
that and what real world problem you are solving? Ideally with numbers
backing it up.

Thanks,

	tglx

Re: [PATCH] timers: Make the lower-level timer function first call than higher-level

[Muchun Song]

Hi tglx,

I'm sorry. Thanks for your reminder.

Thomas Gleixner <tglx@linutronix.de> 于2018年11月28日周三 下午11:15写道：
>
> Song,
>
> On Wed, 21 Nov 2018, Thomas Gleixner wrote:
> > On Tue, 20 Nov 2018, Muchun Song wrote:
> > > Follow the current code logic, the timer0 function is called until the
> > > function call of timer1-5 is completed. So the delay of timer0 is the time
> > > spent by other timer function calls. If we can call the timer function in
> > > the following order, this should be more friendly to lower-level timers.
> > >
> > >         timer0->timer1->->timer2->->timer3->->timer4->->timer5
> > >
> > > Although not friendly to higher-level timers, higher-level has larger
> > > granularity. Therefore the delay has less impact on higher-level.
> >
> > Well yes, that's clear. But is it a problem in practice and if so, what is
> > the measurable benefit.
>
> Polite reminder. Can you please describe what the practical relevance is of
> that and what real world problem you are solving? Ideally with numbers
> backing it up.
>

I just think that this change might be better for me when I read the code.
Maybe what I think is not a problem. So if there is something wrong,
please ignore the patch. Sorry.

Thanks.