questions on calc_delta_mine() in sched.c

questions on calc_delta_mine() in sched.c

[Joel Schopp]

Ingo,

I have a few questions regarding  this code in kernel/sched.c

static unsigned long
calc_delta_mine(unsigned long delta_exec, unsigned long weight,
         struct load_weight *lw)
{
     u64 tmp;

     if (unlikely(!lw->inv_weight))
         lw->inv_weight = (WMULT_CONST-lw->weight/2) / (lw->weight+1);


Q1) This code is hit often in scenarios I run, is this really unlikely for 
others?
Q2) The rest of the code in sched.c seems to make inv_weight == 
WMULT_CONST/weight and I was wondering if you could explain why this 
instance is different.
Q3) That division is pretty expensive, could we sacrifice some accuracy and 
do a precompute table?  Do you have another idea how we could get rid of 
the divide?

-Joel Schopp

Re: questions on calc_delta_mine() in sched.c

[Peter Zijlstra]

On Thu, 2008-05-01 at 15:45 -0500, Joel Schopp wrote:
> Ingo,
> 
> I have a few questions regarding  this code in kernel/sched.c
> 
> static unsigned long
> calc_delta_mine(unsigned long delta_exec, unsigned long weight,
>          struct load_weight *lw)
> {
>      u64 tmp;
> 
>      if (unlikely(!lw->inv_weight))
>          lw->inv_weight = (WMULT_CONST-lw->weight/2) / (lw->weight+1);
> 
> 
> Q1) This code is hit often in scenarios I run, is this really unlikely for 
> others?

I think it became a lot more likely recently, perhaps removing that
unlikely is not such a bad idea.

> Q2) The rest of the code in sched.c seems to make inv_weight == 
> WMULT_CONST/weight and I was wondering if you could explain why this 
> instance is different.

because the rest of the code is wrong, there are only 2 other sites, and
I have a patch that removes those div64_64() with =0;

The idea is to use rounding division: (x + y/2) / y
but we can't because 'x' is touching the limits of our modulo space,
hence we do: (x - y/2) / y
which comes in 1 short, that fixup has been lost along the way.

> Q3) That division is pretty expensive, could we sacrifice some accuracy and 
> do a precompute table?  Do you have another idea how we could get rid of 
> the divide?

Is a full memory miss not more expensive on most modern machines?

And, no sadly I have no ideas on how to get rid of it ;-/

Re: questions on calc_delta_mine() in sched.c

[Peter Zijlstra]

On Fri, 2008-05-02 at 14:14 +0200, Peter Zijlstra wrote:

> And, no sadly I have no ideas on how to get rid of it ;-/

Well, not quite true - I've once thought about a small cache of recently
computed inverse values. Esp for say a ping-pong scenario you end up
re-computing basically the same values over and over again.

Maybe something like this (fully untested):

Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
---
 kernel/sched.c |   22 ++++++++++++++++++----
 1 file changed, 18 insertions(+), 4 deletions(-)

Index: linux-2.6-2/kernel/sched.c
===================================================================
--- linux-2.6-2.orig/kernel/sched.c
+++ linux-2.6-2/kernel/sched.c
@@ -537,6 +537,9 @@ struct rq {
 	unsigned long nr_load_updates;
 	u64 nr_switches;
 
+	struct load_weight[4] lw_cache;
+	int lw_cache_idx;
+
 	struct cfs_rq cfs;
 	struct rt_rq rt;
 
@@ -1438,8 +1441,19 @@ calc_delta_mine(unsigned long delta_exec
 {
 	u64 tmp;
 
-	if (unlikely(!lw->inv_weight))
-		lw->inv_weight = (WMULT_CONST-lw->weight/2) / (lw->weight+1);
+	if (!lw->inv_weight) {
+		struct rq *rq = cpu_rq(smp_processor_id());
+
+		for (i = 0; i < ARRAY_SIZE(rq->lw_cache); i++) {
+			if (rq->lw_cache[i].weight == lw->weight)
+				lw->inv_weight = rq->lw_cache[i].inv_weight;
+			goto got_inv;
+		}
+		lw->inv_weight = 1 + (WMULT_CONST-lw->weight/2) / (lw->weight+1);
+		rq->lw_cache[rq->lw_cache_idx] = *lw;
+		rq->lw_cache_idx = (rq->lw_cache_idx + 1) % ARRAY_SIZE(rq->lw_cache);
+	}
+ got_inv:
 
 	tmp = (u64)delta_exec * weight;
 	/*
@@ -8025,7 +8039,7 @@ static void init_tg_cfs_entry(struct tas
 
 	se->my_q = cfs_rq;
 	se->load.weight = tg->shares;
-	se->load.inv_weight = div64_64(1ULL<<32, se->load.weight);
+	se->load.inv_weight = 0;
 	se->parent = parent;
 }
 #endif
@@ -8692,7 +8706,7 @@ static void __set_se_shares(struct sched
 		dequeue_entity(cfs_rq, se, 0);
 
 	se->load.weight = shares;
-	se->load.inv_weight = div64_64((1ULL<<32), shares);
+	se->load.inv_weight = 0;
 
 	if (on_rq)
 		enqueue_entity(cfs_rq, se, 0);

Re: questions on calc_delta_mine() in sched.c

[Peter Zijlstra]

On Fri, 2008-05-02 at 14:30 +0200, Peter Zijlstra wrote: 
> On Fri, 2008-05-02 at 14:14 +0200, Peter Zijlstra wrote:
> 
> > And, no sadly I have no ideas on how to get rid of it ;-/
> 
> Well, not quite true - I've once thought about a small cache of recently
> computed inverse values. Esp for say a ping-pong scenario you end up
> re-computing basically the same values over and over again.
> 
> Maybe something like this (fully untested):

This one builds and... boots


Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
---
 kernel/sched.c |   27 +++++++++++++++++++++++----
 1 file changed, 23 insertions(+), 4 deletions(-)

Index: linux-2.6-2/kernel/sched.c
===================================================================
--- linux-2.6-2.orig/kernel/sched.c
+++ linux-2.6-2/kernel/sched.c
@@ -537,6 +537,9 @@ struct rq {
 	unsigned long nr_load_updates;
 	u64 nr_switches;
 
+	struct load_weight lw_cache[4];
+	int lw_cache_idx;
+
 	struct cfs_rq cfs;
 	struct rt_rq rt;
 
@@ -1438,8 +1441,24 @@ calc_delta_mine(unsigned long delta_exec
 {
 	u64 tmp;
 
-	if (unlikely(!lw->inv_weight))
-		lw->inv_weight = (WMULT_CONST-lw->weight/2) / (lw->weight+1);
+	if (!lw->inv_weight) {
+		struct rq *rq = cpu_rq(smp_processor_id());
+		unsigned long weight = lw->weight;
+		int i;
+
+		for (i = 0; i < ARRAY_SIZE(rq->lw_cache); i++) {
+			if (rq->lw_cache[i].weight == weight)
+				lw->inv_weight = rq->lw_cache[i].inv_weight;
+			goto got_inv;
+		}
+		if (unlikely(!weight))
+			weight++;
+		lw->inv_weight = 1 + (WMULT_CONST - weight/2) / weight;
+		rq->lw_cache[rq->lw_cache_idx] = *lw;
+		rq->lw_cache_idx++;
+		rq->lw_cache_idx %= ARRAY_SIZE(rq->lw_cache);
+	}
+ got_inv:
 
 	tmp = (u64)delta_exec * weight;
 	/*
@@ -8025,7 +8044,7 @@ static void init_tg_cfs_entry(struct tas
 
 	se->my_q = cfs_rq;
 	se->load.weight = tg->shares;
-	se->load.inv_weight = div64_64(1ULL<<32, se->load.weight);
+	se->load.inv_weight = 0;
 	se->parent = parent;
 }
 #endif
@@ -8692,7 +8711,7 @@ static void __set_se_shares(struct sched
 		dequeue_entity(cfs_rq, se, 0);
 
 	se->load.weight = shares;
-	se->load.inv_weight = div64_64((1ULL<<32), shares);
+	se->load.inv_weight = 0;
 
 	if (on_rq)
 		enqueue_entity(cfs_rq, se, 0);

Re: questions on calc_delta_mine() in sched.c

[Joel Schopp]

> This one builds and... boots

I'll try to test in on my end.

> +	struct load_weight lw_cache[4];
> +	int lw_cache_idx;
> +
>  	struct cfs_rq cfs;
>  	struct rt_rq rt;
>  
> @@ -1438,8 +1441,24 @@ calc_delta_mine(unsigned long delta_exec
>  {
>  	u64 tmp;
>  
> -	if (unlikely(!lw->inv_weight))
> -		lw->inv_weight = (WMULT_CONST-lw->weight/2) / (lw->weight+1);
> +	if (!lw->inv_weight) {

Yep, got to get rid of unlikely.

> +		struct rq *rq = cpu_rq(smp_processor_id());
> +		unsigned long weight = lw->weight;
> +		int i;
> +
> +		for (i = 0; i < ARRAY_SIZE(rq->lw_cache); i++) {
> +			if (rq->lw_cache[i].weight == weight)
> +				lw->inv_weight = rq->lw_cache[i].inv_weight;
> +			goto got_inv;
> +		}
> +		if (unlikely(!weight))
> +			weight++;
> +		lw->inv_weight = 1 + (WMULT_CONST - weight/2) / weight;

I bet just dividing by weight + 1 unconditionally would be cheaper than 
doing the test and shouldn't skew results too badly.

> +		rq->lw_cache[rq->lw_cache_idx] = *lw;
> +		rq->lw_cache_idx++;
> +		rq->lw_cache_idx %= ARRAY_SIZE(rq->lw_cache);
> +	}
> + got_inv:

Doctor, I think the cure is worse than the disease.   I'd expect that even 
if all these extra loads hit cache they should together be more expensive 
than the divide they save.   Not that I have any better solutions myself.

>  
>  	tmp = (u64)delta_exec * weight;
>  	/*
> @@ -8025,7 +8044,7 @@ static void init_tg_cfs_entry(struct tas
>  
>  	se->my_q = cfs_rq;
>  	se->load.weight = tg->shares;
> -	se->load.inv_weight = div64_64(1ULL<<32, se->load.weight);
> +	se->load.inv_weight = 0;
>  	se->parent = parent;
>  }
>  #endif
> @@ -8692,7 +8711,7 @@ static void __set_se_shares(struct sched
>  		dequeue_entity(cfs_rq, se, 0);
>  
>  	se->load.weight = shares;
> -	se->load.inv_weight = div64_64((1ULL<<32), shares);
> +	se->load.inv_weight = 0;
>  
>  	if (on_rq)
>  		enqueue_entity(cfs_rq, se, 0);
> 
> 

I think a patch to get rid of unlikely and to change these two div64_64 to 
0s should be pushed up.  Not sure what we do about the divide.

Re: questions on calc_delta_mine() in sched.c

[Peter Zijlstra]

On Fri, 2008-05-02 at 13:46 -0500, Joel Schopp wrote:
> > This one builds and... boots
> 
> I'll try to test in on my end.
> 
> > +	struct load_weight lw_cache[4];
> > +	int lw_cache_idx;
> > +
> >  	struct cfs_rq cfs;
> >  	struct rt_rq rt;
> >  
> > @@ -1438,8 +1441,24 @@ calc_delta_mine(unsigned long delta_exec
> >  {
> >  	u64 tmp;
> >  
> > -	if (unlikely(!lw->inv_weight))
> > -		lw->inv_weight = (WMULT_CONST-lw->weight/2) / (lw->weight+1);
> > +	if (!lw->inv_weight) {
> 
> Yep, got to get rid of unlikely.
> 
> > +		struct rq *rq = cpu_rq(smp_processor_id());
> > +		unsigned long weight = lw->weight;
> > +		int i;
> > +
> > +		for (i = 0; i < ARRAY_SIZE(rq->lw_cache); i++) {
> > +			if (rq->lw_cache[i].weight == weight)
> > +				lw->inv_weight = rq->lw_cache[i].inv_weight;
> > +			goto got_inv;
> > +		}
> > +		if (unlikely(!weight))
> > +			weight++;
> > +		lw->inv_weight = 1 + (WMULT_CONST - weight/2) / weight;
> 
> I bet just dividing by weight + 1 unconditionally would be cheaper than 
> doing the test and shouldn't skew results too badly.

Yeah... probably - getting rid of that one case where it can happen is
on my todo list somewhere.

> > +		rq->lw_cache[rq->lw_cache_idx] = *lw;
> > +		rq->lw_cache_idx++;
> > +		rq->lw_cache_idx %= ARRAY_SIZE(rq->lw_cache);
> > +	}
> > + got_inv:
> 
> Doctor, I think the cure is worse than the disease.   I'd expect that even 
> if all these extra loads hit cache they should together be more expensive 
> than the divide they save.   Not that I have any better solutions myself.

Probably, but since you seemed in benchmarking mood I thought you might
as well give it a go ;-)

> I think a patch to get rid of unlikely and to change these two div64_64 to 
> 0s should be pushed up.  Not sure what we do about the divide.

Ok, I'll stick such a patch in to to-mingo queue ;-)

Re: questions on calc_delta_mine() in sched.c

[Joel Schopp]

>>      if (unlikely(!lw->inv_weight))
>>          lw->inv_weight = (WMULT_CONST-lw->weight/2) / (lw->weight+1);
>>
>>
>> Q1) This code is hit often in scenarios I run, is this really unlikely for 
>> others?
> 
> I think it became a lot more likely recently, perhaps removing that
> unlikely is not such a bad idea.

Especially if you remove the divide in the other locations, then this might 
even be likely.

> 
>> Q2) The rest of the code in sched.c seems to make inv_weight == 
>> WMULT_CONST/weight and I was wondering if you could explain why this 
>> instance is different.
> 
> because the rest of the code is wrong, there are only 2 other sites, and
> I have a patch that removes those div64_64() with =0;
> 
> The idea is to use rounding division: (x + y/2) / y
> but we can't because 'x' is touching the limits of our modulo space,
> hence we do: (x - y/2) / y
> which comes in 1 short, that fixup has been lost along the way.

Ah, that makes more sense, and the fact that it is broken explains why I 
couldn't figure it out.