Skip to contentSkip to conversation

questions on calc_delta_mine() in sched.c

DISCUSSION Joel Schopp 2 participants 7 messages May 1, 2008 – May 2, 2008

lore
Share & tools
lore
#0 lore raw

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

#1 lore raw
Quoted 14 lines · 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);
Quoted 2 lines

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.

Quoted 3 lines

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.

Quoted 3 lines

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 ;-/

#2 lore raw
Quoted 1 line · Peter Zijlstra

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):

---
 kernel/sched.c |   22 ++++++++++++++++++----
 1 file changed, 18 insertions(+), 4 deletions(-)
kernel/sched.c +18 -4
Index: 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);
#3 lore raw
Quoted 9 lines · Peter Zijlstra
Quoted 1 line · Peter Zijlstra

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

---
 kernel/sched.c |   27 +++++++++++++++++++++++----
 1 file changed, 23 insertions(+), 4 deletions(-)
kernel/sched.c +23 -4
Index: 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);
#4 lore raw
Quoted 1 line

This one builds and... boots

I'll try to test in on my end.

kernel/sched.c calc_delta_mine(unsigned long delta_exec · line 1444

Quoted 13 lines
kernel/sched.c +4 -2
+	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.

kernel/sched.c calc_delta_mine(unsigned long delta_exec · line 1456

Quoted 12 lines
kernel/sched.c +12 -0
+		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.

kernel/sched.c calc_delta_mine(unsigned long delta_exec · line 1461

Quoted 5 lines
kernel/sched.c +5 -0
+		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.

Quoted 15 lines
kernel/sched.c +1 -1
 	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

kernel/sched.c static void __set_se_shares(struct sched · line 8717

Quoted 8 lines
kernel/sched.c +1 -1
@@ -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.

#5 lore raw
Quoted 20 lines · Joel Schopp
Quoted 1 line

This one builds and... boots

I'll try to test in on my end.

kernel/sched.c calc_delta_mine(unsigned long delta_exec · line 1444

Quoted 13 lines
kernel/sched.c +4 -2
+	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.

Quoted 15 lines

kernel/sched.c calc_delta_mine(unsigned long delta_exec · line 1456

Quoted 12 lines
kernel/sched.c +12 -0
+		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.

Quoted 9 lines

kernel/sched.c calc_delta_mine(unsigned long delta_exec · line 1461

Quoted 5 lines
kernel/sched.c +5 -0
+		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 ;-)

Quoted 2 lines

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 ;-)

#6 lore raw
In reply to Peter Zijlstra
Quoted 8 lines
Quoted 5 lines
     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.

Quoted 10 lines
Quoted 2 lines

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.