[PATCH 23/30] sched: optimize effective_load()

Peter Zijlstra
2008-06-27T12:05:10Z

[-- Attachment #1: sched-simplyfy-effective-load.patch --]
[-- Type: text/plain, Size: 1084 bytes --]

s_i = S * rw_i / \Sum_j rw_j

-> \Sum_j rw_j = S * rw_i / s_i

-> s'_i = S * (rw_i + w) / (\Sum_j rw_j + w)

delta s = s' - s = S * (rw + w) / ((S * rw / s) + w)
= s * (S * (rw + w) / (S * rw + s * w) - 1)

a = S*(rw+w), b = S*rw + s*w

delta s = s * (a-b) / b

IOW, trade one divide for two multiplies

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

Index: linux-2.6/kernel/sched_fair.c
===================================================================
--- linux-2.6.orig/kernel/sched_fair.c
+++ linux-2.6/kernel/sched_fair.c
@@ -1079,16 +1079,16 @@ static unsigned long effective_load(stru
for_each_sched_entity(se) {
#define D(n) (likely(n) ? (n) : 1)

- long S, Srw, rw, s, sn;
+ long S, rw, s, a, b;

S = se->my_q->tg->shares;
s = se->my_q->shares;
rw = se->my_q->load.weight;

- Srw = S * rw / D(s);
- sn = S * (rw + wl) / D(Srw + wg);
+ a = S*(rw + wl);
+ b = S*rw + s*wg;

- wl = sn - s;
+ wl = s*(a-b)/D(b);
wg = 0;
#undef D
}

--