linux-kernel - Re: [PATCH v3] Add generic exponentially weighted moving average (EWMA) function

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <1287655475.3488.99.camel@twins>
Date:	Thu, 21 Oct 2010 12:04:35 +0200
From:	Peter Zijlstra <peterz@...radead.org>
To:	Bruno Randolf <br1@...fach.org>
Cc:	randy.dunlap@...cle.com, akpm@...ux-foundation.org,
	kevin.granade@...il.com, Lars_Ericsson@...ia.com,
	blp@...stanford.edu, linux-kernel@...r.kernel.org
Subject: Re: [PATCH v3] Add generic exponentially weighted moving average
 (EWMA) function

On Thu, 2010-10-21 at 14:40 +0900, Bruno Randolf wrote:
> On Thu October 21 2010 00:03:43 Peter Zijlstra wrote:
> > On Wed, 2010-10-20 at 17:23 +0900, Bruno Randolf wrote:
> > > +/**
> > > + * ewma_add() - Exponentially weighted moving average (EWMA)
> > > + * @avg: Average structure
> > > + * @val: Current value
> > > + *
> > > + * Add a sample to the average.
> > > + */
> > > +struct ewma*
> > > +ewma_add(struct ewma *avg, const unsigned int val)
> > > +{
> > > +       avg->internal = avg->internal  ?
> > > +               (((avg->internal * (avg->weight - 1)) +
> > > +                       (val * avg->factor)) / avg->weight) :
> > > +               (val * avg->factor);
> > > +       return avg;
> > > +}
> > > +EXPORT_SYMBOL(ewma_add);
> > 
> > How can it be a weighted avg if each sample has the same weight?
> 
> by applying the weight again and again, we get an exponential weighting.
> 
> http://en.wikipedia.org/wiki/Exponentially_weighted_moving_average

Ah, thanks. It might be worth adding some of that explanation to the
actual comment.

I think the naming is somewhat unfortunate since a weighted average
makes me think of:

       \Sum w_i * v_i
 wa = ---------------
         \Sum w_i

Instead of the described algorithm.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/