questions on calc_delta_mine() in sched.c
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
Quoted 14 lines · Joel Schopp
Ingo,
I have a few questions regarding this code in
kernel/sched.cstatic unsigned long
calc_delta_mine(unsigned longdelta_exec, unsigned long weight,
structload_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.cseems to makeinv_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 ;-/
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
@@ -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 scheddequeue_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 );
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
@@ -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 scheddequeue_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 );
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
-1tmp = (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 scheddequeue_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.
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_64to 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 ;-)
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.cseems to makeinv_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.