On 07/11/2018 14:05, Peter Zijlstra wrote: > On Wed, Nov 07, 2018 at 11:52:31AM +0100, Daniel Lezcano wrote: >>> @@ -146,11 +152,38 @@ static void irqs_update(struct irqt_stat *irqs, u64 >>> ts) >>> */ >>> diff = interval - irqs->avg; >>> >>> + /* >>> + * Online average algorithm: >>> + * >>> + * new_average = average + ((value - average) / count) >>> + * >>> + * The variance computation depends on the new average >>> + * to be computed here first. >>> + * >>> + */ >>> + irqs->avg = irqs->avg + (diff >> IRQ_TIMINGS_SHIFT); >>> + >>> + /* >>> + * Online variance algorithm: >>> + * >>> + * new_variance = variance + (value - average) x (value - new_average) >>> + * >>> + * Warning: irqs->avg is updated with the line above, hence >>> + * 'interval - irqs->avg' is no longer equal to 'diff' >>> + */ >>> + irqs->variance = irqs->variance + (diff * (interval - irqs->avg)); >>> + >>> /* >>> * Increment the number of samples. >>> */ >>> irqs->nr_samples++; > > FWIW, I'm confused on this. The normal (Welford's) online algorithm > does: > > count++; > delta = value - mean; > mean += delta / count; > M2 += delta * (value - mean); > > But the above uses: > > mean += delta / 32; > > Which, for count >> 32, over-estimates the mean adjustment. But worse, > it significantly under-estimates the mean during training. > > How is the computed variance still correct with this? I can not find any > comments that clarifies this. I'm thinking that since the mean will > slowly wander towards it's actual location (assuming an actual standard > distribution input) the resulting variance will be far too large, since > the (value - mean) term will be much larger than 'expected'.
You are right, initially it was divided by min(count, 32) but for optimization reason, we decided to change that by a power of two constant assuming the number of samples will reach quickly 32 and the compiler will replace that by a shift. https://lkml.org/lkml/2017/3/23/696 >>> @@ -158,16 +191,12 @@ static void irqs_update(struct irqt_stat *irqs, u64 >>> ts) >>> * more than 32 and dividing by 32 instead of 31 is enough >>> * precise. >>> */ >>> + variance = irqs->variance >> IRQ_TIMINGS_SHIFT; > > Worse; variance is actually (as the comment states): > > s^2 = M2 / (count -1) > > But instead you compute: > > s^2 = M2 / 32; > > Which is again much larger than the actual result; assuming count >> 32. > > So you compute a variance that is inflated in two different ways. > > > I'm not seeing how this thing works reliably. I have to revisit this part of code soon, I will double check that. -- <http://www.linaro.org/> Linaro.org │ Open source software for ARM SoCs Follow Linaro: <http://www.facebook.com/pages/Linaro> Facebook | <http://twitter.com/#!/linaroorg> Twitter | <http://www.linaro.org/linaro-blog/> Blog
