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

#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] | [standalone]

Back to top | Article view | linux.kernel

csiph-web