Messages in this thread | | | Subject | Re: [PATCH] sched: Avoid side-effect of tickless idle on update_cpu_load (v2) | From | Peter Zijlstra <> | Date | Mon, 17 May 2010 19:35:17 +0200 |
| |
On Mon, 2010-05-17 at 09:52 -0700, Venkatesh Pallipadi wrote:
> > load_i = ((2^i)-1)/(2^i) * load_i + 1/(2^i) * load_(i-1)
> > So because we're in no_hz, current load == 0 and we could approximate > > the thing by: > > > > load_i = ((2^i)-1)/(2^i) * load_i > > > > Because for i ~ 1, there is no new input, and for i >> 1 the fraction is > > small. > > Something like that. But, with total_updates = n and missed_updates = n - 1 > We do this for (n - 1) > load_i = ((2^i)-1)/(2^i) * load_i > And do this once. > load_i = ((2^i)-1)/(2^i) * load_i + 1/(2^i) * cur_load
> That way we do not differentiate between whether we are in tickless or > not and we use the same code path.
But by the above, that's not the same as without, because that does
load_i = ((2^i)-1)/(2^i) * load_i + 1/(2^i) * load_(i-1)
not
load_i = ((2^i)-1)/(2^i) * load_i + 1/(2^i) * cur_load
> > But why then do we precalculate these factors? It seems to me > > ((2^i)-1)/(2^i) is something that is trivial to compute and doesn't > > warrant a lookup table? > > > > Yes. Initially I had a for loop running for missed_updates to calculate > ((2^i)-1)/(2^i) * load_i > in a loop.
Ah, right! So you want to calculate:
(((2^i)-1)/(2^i))^n
Which ends up being a nasty binomial sum: 1/(2^ni) * \Sum_k^n (n choose k) * 2^k, so yeah, I don't see a fancy way to quickly compute that.
OK, could you summarize our discussion into that comment?
| |