Re: questions on calc_delta_mine() in sched.c

Peter Zijlstra
2008-05-02T13:10:35Z

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