Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1436184 > unrolled thread

Re: [rfc patch] sched/fair: Use instantaneous load for fork/exec balancing

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [rfc patch] sched/fair: Use instantaneous load for fork/exec  balancing Matt Fleming <matt@codeblueprint.co.uk> - 2016-07-04 17:10 +0200
    Re: [rfc patch] sched/fair: Use instantaneous load for fork/exec  balancing Mike Galbraith <umgwanakikbuti@gmail.com> - 2016-07-04 19:50 +0200
      Re: [rfc patch] sched/fair: Use instantaneous load for fork/exec  balancing Matt Fleming <matt@codeblueprint.co.uk> - 2016-07-06 13:50 +0200
        Re: [rfc patch] sched/fair: Use instantaneous load for fork/exec  balancing Mike Galbraith <umgwanakikbuti@gmail.com> - 2016-07-06 14:30 +0200
    Re: [rfc patch] sched/fair: Use instantaneous load for fork/exec  balancing Dietmar Eggemann <dietmar.eggemann@arm.com> - 2016-07-11 11:00 +0200
      Re: [rfc patch] sched/fair: Use instantaneous load for fork/exec  balancing Matt Fleming <matt@codeblueprint.co.uk> - 2016-07-12 13:20 +0200

#1436184 — Re: [rfc patch] sched/fair: Use instantaneous load for fork/exec balancing

On Wed, 15 Jun, at 04:32:58PM, Dietmar Eggemann wrote:
> On 14/06/16 17:40, Mike Galbraith wrote:
> > On Tue, 2016-06-14 at 15:14 +0100, Dietmar Eggemann wrote:
> > 
> >> IMHO, the hackbench performance "boost" w/o 0905f04eb21f is due to the
> >> fact that a new task gets all it's load decayed (making it a small task)
> >> in the __update_load_avg() call in remove_entity_load_avg() because its
> >> se->avg.last_update_time value is 0 which creates a huge time difference
> >> comparing it to cfs_rq->avg.last_update_time. The patch 0905f04eb21f
> >> avoids this and thus the task stays big se->avg.load_avg = 1024.
> > 
> > I don't care much at all about the hackbench "regression" in its own
> > right, and what causes it, for me, bottom line is that there are cases
> > where we need to be able to resolve, and can't, simply because we're
> > looking at a fuzzy (rippling) reflection.
> 
> Understood. I just thought it would be nice to know why 0905f04eb21f
> makes this problem even more visible. But so far I wasn't able to figure
> out why this diff in se->avg.load_avg [1024 versus 0] has this effect on
> cfs_rq->runnable_load_avg making it even less suitable in find idlest*.
> enqueue_entity_load_avg()'s cfs_rq->runnable_load_* += sa->load_* looks
> suspicious though.

In my testing without 0905f04eb21f I saw that se->avg.load_avg
actually managed to skip being decayed at all before the task was
dequeued, which meant that cfs_rq->runnable_load_avg was more likely
to be zero after dequeue, for those workloads like hackbench that
essentially are just a fork bomb.

se->avg.load_avg evaded decay because se->avg.period_contrib was being
zero'd in __update_load_avg().

With 0905f04eb21f applied, it's less likely (though not impossible)
that ->period_contrib will be zero'd and so we usually end up with
some residual load in cfs_rq->runnable_load_avg on dequeue, and hence,

	cfs_rq->runnable_load_avg > se->avg.load_avg

even if 'se' is the only task on the runqueue.

FYI, below is my quick and dirty hack that restored hackbench
performance for the few machines I checked. I didn't try schbench with
it.

---

From 4e9856ea3dc56e356195ca035dab7302754ce59b Mon Sep 17 00:00:00 2001
From: Matt Fleming <matt@codeblueprint.co.uk>
Date: Thu, 9 Jun 2016 19:48:14 +0100
Subject: [PATCH] sched/fair: Reset ::runnable_load_avg when dequeueing last
 entity

The task and runqueue load averages maintained in p->se.avg.load_avg
and cfs_rq->runnable_load_avg respectively, can decay at different
wall clock rates, which means that enqueueing and then dequeueing a
task on an otherwise empty runqueue doesn't always leave
::runnable_load_avg with its initial value.

This can lead to the situation where cfs_rq->runnable_load_avg has a
non-zero value even though there are no runnable entities on the
runqueue. Assuming no entity is enqueued on this runqueue for some
time this residual load average will decay gradually as the load
averages are updated.

But we can optimise the special case of dequeueing the last entity and
reset ::runnable_load_avg early, which gives a performance improvement
to workloads that trigger the load balancer, such as fork-heavy
applications when SD_BALANCE_FORK is set, because it gives a more up
to date view of how busy the cpu is.

Signed-off-by: Matt Fleming <matt@codeblueprint.co.uk>
---
 kernel/sched/fair.c | 14 ++++++++++++--
 1 file changed, 12 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index c6dd8bab010c..408ee90c7ea8 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -3007,10 +3007,20 @@ enqueue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
 static inline void
 dequeue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
+	unsigned long load_avg = 0;
+
 	update_load_avg(se, 1);
 
-	cfs_rq->runnable_load_avg =
-		max_t(long, cfs_rq->runnable_load_avg - se->avg.load_avg, 0);
+	/*
+	 * If we're about to dequeue the last runnable entity we can
+	 * reset the runnable load average to zero instead of waiting
+	 * for it to decay naturally. This gives the load balancer a
+	 * more timely and accurate view of how busy this cpu is.
+	 */
+	if (cfs_rq->nr_running > 1)
+		load_avg = max_t(long, cfs_rq->runnable_load_avg - se->avg.load_avg, 0);
+
+	cfs_rq->runnable_load_avg = load_avg;
 	cfs_rq->runnable_load_sum =
 		max_t(s64,  cfs_rq->runnable_load_sum - se->avg.load_sum, 0);
 }
-- 
2.7.3

[toc] | [next] | [standalone]

#1436452

On Mon, 2016-07-04 at 16:04 +0100, Matt Fleming wrote:

> But we can optimise the special case of dequeueing the last entity and
> reset ::runnable_load_avg early, which gives a performance improvement
> to workloads that trigger the load balancer, such as fork-heavy
> applications when SD_BALANCE_FORK is set, because it gives a more up
> to date view of how busy the cpu is.

Begs the question: what's so special about this case vs any other
dequeue/enqueue?

I've given up on this as being a waste of time.  Either you serialize
everything box wide (not!) and can then make truly accurate evaluations
of state, or you're making an educated guess based upon what once was.

The only place I've seen where using the average consistently has
issues is with a longish period periodic load (schbench).

	-Mike

[toc] | [prev] | [next] | [standalone]

#1437655

On Mon, 04 Jul, at 07:43:14PM, Mike Galbraith wrote:
> On Mon, 2016-07-04 at 16:04 +0100, Matt Fleming wrote:
> 
> > But we can optimise the special case of dequeueing the last entity and
> > reset ::runnable_load_avg early, which gives a performance improvement
> > to workloads that trigger the load balancer, such as fork-heavy
> > applications when SD_BALANCE_FORK is set, because it gives a more up
> > to date view of how busy the cpu is.
> 
> Begs the question: what's so special about this case vs any other
> dequeue/enqueue?
 
All that makes this special is that this is the behaviour seen when
running hackbench - initial heavy forking by some master task which
eventually wakes everyone up. So you get this huge sequence of "fork,
enqueue, run, dequeue". Yes, it's a complete hack.

> I've given up on this as being a waste of time.  Either you serialize
> everything box wide (not!) and can then make truly accurate evaluations
> of state, or you're making an educated guess based upon what once was.
> 
> The only place I've seen where using the average consistently has
> issues is with a longish period periodic load (schbench).

I'm open to any suggestion that restores performance to that seen
before commit 0905f04eb21f, whether or not that involves changing how
load averages are used.

[toc] | [prev] | [next] | [standalone]

#1437675

On Wed, 2016-07-06 at 12:45 +0100, Matt Fleming wrote:
> On Mon, 04 Jul, at 07:43:14PM, Mike Galbraith wrote:
> > On Mon, 2016-07-04 at 16:04 +0100, Matt Fleming wrote:
> > 
> > > But we can optimise the special case of dequeueing the last entity and
> > > reset ::runnable_load_avg early, which gives a performance improvement
> > > to workloads that trigger the load balancer, such as fork-heavy
> > > applications when SD_BALANCE_FORK is set, because it gives a more up
> > > to date view of how busy the cpu is.
> > 
> > Begs the question: what's so special about this case vs any other
> > dequeue/enqueue?
>  
> All that makes this special is that this is the behaviour seen when
> running hackbench - initial heavy forking by some master task which
> eventually wakes everyone up. So you get this huge sequence of "fork,
> enqueue, run, dequeue". Yes, it's a complete hack.

I'm a bit concerned that poking holes in the logic to make hackbench a
bit happier will eradicate the calming effect that avg/aging business
has on load balancing, inflicting harm on real world loads.  That would
be a bad trade.

> > I've given up on this as being a waste of time.  Either you serialize
> > everything box wide (not!) and can then make truly accurate evaluations
> > of state, or you're making an educated guess based upon what once was.
> > 
> > The only place I've seen where using the average consistently has
> > issues is with a longish period periodic load (schbench).
> 
> I'm open to any suggestion that restores performance to that seen
> before commit 0905f04eb21f, whether or not that involves changing how
> load averages are used.

None here.  That hackbench was fond of that dead bug is just too bad,
as Peter seldom resurrects bugs once swatted :)  FWIW, I took a peek at
distribution on my little desktop box while fiddling, and while it was
not a pretty flat line, it wasn't a stock market crash graph either.

	-Mike

[toc] | [prev] | [next] | [standalone]

#1440378

On 04/07/16 16:04, Matt Fleming wrote:
> On Wed, 15 Jun, at 04:32:58PM, Dietmar Eggemann wrote:
>> On 14/06/16 17:40, Mike Galbraith wrote:
>>> On Tue, 2016-06-14 at 15:14 +0100, Dietmar Eggemann wrote:
>>>
>>>> IMHO, the hackbench performance "boost" w/o 0905f04eb21f is due to the
>>>> fact that a new task gets all it's load decayed (making it a small task)
>>>> in the __update_load_avg() call in remove_entity_load_avg() because its
>>>> se->avg.last_update_time value is 0 which creates a huge time difference
>>>> comparing it to cfs_rq->avg.last_update_time. The patch 0905f04eb21f
>>>> avoids this and thus the task stays big se->avg.load_avg = 1024.
>>>
>>> I don't care much at all about the hackbench "regression" in its own
>>> right, and what causes it, for me, bottom line is that there are cases
>>> where we need to be able to resolve, and can't, simply because we're
>>> looking at a fuzzy (rippling) reflection.
>>
>> Understood. I just thought it would be nice to know why 0905f04eb21f
>> makes this problem even more visible. But so far I wasn't able to figure
>> out why this diff in se->avg.load_avg [1024 versus 0] has this effect on
>> cfs_rq->runnable_load_avg making it even less suitable in find idlest*.
>> enqueue_entity_load_avg()'s cfs_rq->runnable_load_* += sa->load_* looks
>> suspicious though.
> 
> In my testing without 0905f04eb21f I saw that se->avg.load_avg
> actually managed to skip being decayed at all before the task was
> dequeued, which meant that cfs_rq->runnable_load_avg was more likely
> to be zero after dequeue, for those workloads like hackbench that
> essentially are just a fork bomb.

Do you mean the first dequeue when the task is forked?

These are the pelt related functions which are called when the task is
forked:

detach_entity_load_avg
attach_entity_load_avg
remove_entity_load_avg <-- se->avg.load_avg is set to 0 w/o 0905f04eb21f
                           se->avg.load_avg stays 1024 w/ 0905f04eb21f
enqueue_entity_load_avg
attach_entity_load_avg (double attach is fixed on tip/sched/core)
dequeue_entity_load_avg

> se->avg.load_avg evaded decay because se->avg.period_contrib was being
> zero'd in __update_load_avg().

I don't see the relation to se->avg.period_contrib here. IMHO,
se->avg.period_contrib is purely there to manage the 3 different update
phases in __update_load_avg().

This difference in the initial se->avg.load_avg value [0 or 1024] has an
influence in wake_affine() [weight = p->se.avg.load_avg;] for the wakeup
handling of the hackbench tasks in the 'send/receive data' phase.

There are a couple of patches on tip/sched/core which might change the
behaviour of this: fork path, no double attach_entity_load_avg for new
task, no remove_entity_load_avg for new task, changes in effective_load ...

> With 0905f04eb21f applied, it's less likely (though not impossible)
> that ->period_contrib will be zero'd and so we usually end up with
> some residual load in cfs_rq->runnable_load_avg on dequeue, and hence,
> 
> 	cfs_rq->runnable_load_avg > se->avg.load_avg
> 
> even if 'se' is the only task on the runqueue.
> 
> FYI, below is my quick and dirty hack that restored hackbench
> performance for the few machines I checked. I didn't try schbench with
> it.
> 
> ---
> 
> From 4e9856ea3dc56e356195ca035dab7302754ce59b Mon Sep 17 00:00:00 2001
> From: Matt Fleming <matt@codeblueprint.co.uk>
> Date: Thu, 9 Jun 2016 19:48:14 +0100
> Subject: [PATCH] sched/fair: Reset ::runnable_load_avg when dequeueing last
>  entity
> 
> The task and runqueue load averages maintained in p->se.avg.load_avg
> and cfs_rq->runnable_load_avg respectively, can decay at different
> wall clock rates, which means that enqueueing and then dequeueing a
> task on an otherwise empty runqueue doesn't always leave
> ::runnable_load_avg with its initial value.
> 
> This can lead to the situation where cfs_rq->runnable_load_avg has a
> non-zero value even though there are no runnable entities on the
> runqueue. Assuming no entity is enqueued on this runqueue for some
> time this residual load average will decay gradually as the load
> averages are updated.
> 
> But we can optimise the special case of dequeueing the last entity and
> reset ::runnable_load_avg early, which gives a performance improvement
> to workloads that trigger the load balancer, such as fork-heavy
> applications when SD_BALANCE_FORK is set, because it gives a more up
> to date view of how busy the cpu is.
> 
> Signed-off-by: Matt Fleming <matt@codeblueprint.co.uk>
> ---
>  kernel/sched/fair.c | 14 ++++++++++++--
>  1 file changed, 12 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index c6dd8bab010c..408ee90c7ea8 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -3007,10 +3007,20 @@ enqueue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
>  static inline void
>  dequeue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
>  {
> +	unsigned long load_avg = 0;
> +
>  	update_load_avg(se, 1);
>  
> -	cfs_rq->runnable_load_avg =
> -		max_t(long, cfs_rq->runnable_load_avg - se->avg.load_avg, 0);
> +	/*
> +	 * If we're about to dequeue the last runnable entity we can
> +	 * reset the runnable load average to zero instead of waiting
> +	 * for it to decay naturally. This gives the load balancer a
> +	 * more timely and accurate view of how busy this cpu is.
> +	 */
> +	if (cfs_rq->nr_running > 1)
> +		load_avg = max_t(long, cfs_rq->runnable_load_avg - se->avg.load_avg, 0);
> +
> +	cfs_rq->runnable_load_avg = load_avg;
>  	cfs_rq->runnable_load_sum =
>  		max_t(s64,  cfs_rq->runnable_load_sum - se->avg.load_sum, 0);
>  }
> 

[toc] | [prev] | [next] | [standalone]

#1441262

On Mon, 11 Jul, at 09:58:52AM, Dietmar Eggemann wrote:
> This difference in the initial se->avg.load_avg value [0 or 1024] has an
> influence in wake_affine() [weight = p->se.avg.load_avg;] for the wakeup
> handling of the hackbench tasks in the 'send/receive data' phase.
 
The way I was running hackbench made it very susceptible to changes in
fork behaviour, i.e. running it with a small number of loops.

> There are a couple of patches on tip/sched/core which might change the
> behaviour of this: fork path, no double attach_entity_load_avg for new
> task, no remove_entity_load_avg for new task, changes in effective_load ...
 
Indeed they do! Things are much improved when running the latest
tip/sched/core, thanks for the pointer.

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web