[PATCH v3] Add generic exponentially weighted moving average (EWMA) function

[PATCH v3] Add generic exponentially weighted moving average (EWMA) function

[Bruno Randolf]

This adds generic functions for calculating Exponentially Weighted Moving
Averages (EWMA). This implementation makes use of a structure which keeps the
EWMA parameters and a scaled up internal representation to reduce rounding
errors.

The original idea for this implementation came from the rt2x00 driver
(rt2x00link.c). I would like to use it in several places in the mac80211 and
ath5k code and I hope it can be useful in many other places in the kernel code.

Signed-off-by: Bruno Randolf <br1@einfach.org>

--
v3: Addressing Andrew Mortons comments: Implement in lib/average.c and make
    access and initalization functions. Use unsigned int for values. Rename
    functions to ewma_* since there might be other moving average
    implementations which are not exponentially weighted.

v2: Renamed 'samples' to 'weight'. Added more documentation. Use avg_val
    pointer. Add a WARN_ON_ONCE for invalid values of 'weight'. Divide
    and round up/down.
---
 include/linux/average.h |   32 +++++++++++++++++++++++++
 lib/Makefile            |    2 +-
 lib/average.c           |   59 +++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 92 insertions(+), 1 deletions(-)
 create mode 100644 include/linux/average.h
 create mode 100644 lib/average.c

diff --git a/include/linux/average.h b/include/linux/average.h
new file mode 100644
index 0000000..56bef6c
--- /dev/null
+++ b/include/linux/average.h
@@ -0,0 +1,32 @@
+#ifndef _LINUX_AVERAGE_H
+#define _LINUX_AVERAGE_H
+
+#include <linux/kernel.h>
+
+/* Exponentially weighted moving average (EWMA) */
+
+/* For more documentation see lib/average.c */
+
+struct ewma {
+	unsigned int internal;
+	unsigned int factor;
+	unsigned int weight;
+};
+
+extern struct ewma* ewma_init(struct ewma *avg, const unsigned int factor,
+			      const unsigned int weight);
+
+extern struct ewma* ewma_add(struct ewma *avg, const unsigned int val);
+
+/**
+ * ewma_get() - Get average value
+ * @avg: Average structure
+ *
+ * Returns the average value held in @avg.
+ */
+static inline unsigned int ewma_get(const struct ewma *avg)
+{
+	return DIV_ROUND_CLOSEST(avg->internal, avg->factor);
+}
+
+#endif /* _LINUX_AVERAGE_H */
diff --git a/lib/Makefile b/lib/Makefile
index e6a3763..f66acf7 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -21,7 +21,7 @@ lib-y	+= kobject.o kref.o klist.o
 
 obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \
 	 bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \
-	 string_helpers.o gcd.o lcm.o list_sort.o uuid.o
+	 string_helpers.o gcd.o lcm.o list_sort.o uuid.o average.o
 
 ifeq ($(CONFIG_DEBUG_KOBJECT),y)
 CFLAGS_kobject.o += -DDEBUG
diff --git a/lib/average.c b/lib/average.c
new file mode 100644
index 0000000..081a8fd
--- /dev/null
+++ b/lib/average.c
@@ -0,0 +1,59 @@
+/*
+ * lib/average.c
+ *
+ * This source code is licensed under the GNU General Public License,
+ * Version 2.  See the file COPYING for more details.
+ */
+
+#include <linux/module.h>
+#include <linux/average.h>
+
+/**
+ * DOC: Exponentially Weighted Moving Average (EWMA)
+ *
+ * These are generic functions for calculating Exponentially Weighted Moving
+ * Averages (EWMA). We keep a structure with the EWMA parameters and a scaled
+ * up internal representation of the average value to prevent rounding errors.
+ * The factor for scaling up and the exponential weight (or decay rate) have to
+ * be specified thru the init fuction. The structure should not be accessed
+ * directly but only thru the helper functions.
+ */
+
+/**
+ * ewma_init() - Initialize EWMA parameters
+ * @avg: Average structure
+ * @factor: Factor to use for the scaled up internal value. The maximum value
+ *	of averages can be UINT_MAX/(factor*weight).
+ * @weight: Exponential weight, or decay rate. This defines how fast the
+ * 	influence of older values decreases. Has to be bigger than 1.
+ *
+ * Initialize the EWMA parameters for a given struct ewma @avg.
+ */
+struct ewma*
+ewma_init(struct ewma *avg, const unsigned int factor,
+	  const unsigned int weight)
+{
+	WARN_ON(weight <= 1 || factor == 0);
+	avg->weight = weight;
+	avg->factor = factor;
+	return avg;
+}
+EXPORT_SYMBOL(ewma_init);
+
+/**
+ * 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);

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

[Peter Zijlstra]

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?

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

[Bruno Randolf]

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

bruno

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

[Peter Zijlstra]

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.

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

[KOSAKI Motohiro]

Hi

I'm plaing this a bit and I have to say this doesn't works as I expected
because ewma_init() has very easy confusable.

so, I have one request.


> +/**
> + * ewma_init() - Initialize EWMA parameters
> + * @avg: Average structure
> + * @factor: Factor to use for the scaled up internal value. The maximum value
> + *	of averages can be UINT_MAX/(factor*weight).
> + * @weight: Exponential weight, or decay rate. This defines how fast the
> + * 	influence of older values decreases. Has to be bigger than 1.
> + *
> + * Initialize the EWMA parameters for a given struct ewma @avg.
> + */
> +struct ewma*
> +ewma_init(struct ewma *avg, const unsigned int factor,
> +	  const unsigned int weight)
> +{
> +	WARN_ON(weight <= 1 || factor == 0);
> +	avg->weight = weight;
> +	avg->factor = factor;
> +	return avg;
> +}
> +EXPORT_SYMBOL(ewma_init);

Please initalize avg->internal too.


and nit, I don't understand what you intend by 'const unsigned int'. I think
we can remove this const safely. it's more easy readable.

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

[Bruno Randolf]

On Thu October 21 2010 19:31:47 KOSAKI Motohiro wrote:
> Hi
> 
> I'm plaing this a bit and I have to say this doesn't works as I expected
> because ewma_init() has very easy confusable.
> 
> so, I have one request.
> 
> > +/**
> > + * ewma_init() - Initialize EWMA parameters
> > + * @avg: Average structure
> > + * @factor: Factor to use for the scaled up internal value. The maximum
> > value + *	of averages can be UINT_MAX/(factor*weight).
> > + * @weight: Exponential weight, or decay rate. This defines how fast the
> > + * 	influence of older values decreases. Has to be bigger than 1.
> > + *
> > + * Initialize the EWMA parameters for a given struct ewma @avg.
> > + */
> > +struct ewma*
> > +ewma_init(struct ewma *avg, const unsigned int factor,
> > +	  const unsigned int weight)
> > +{
> > +	WARN_ON(weight <= 1 || factor == 0);
> > +	avg->weight = weight;
> > +	avg->factor = factor;
> > +	return avg;
> > +}
> > +EXPORT_SYMBOL(ewma_init);
> 
> Please initalize avg->internal too.

Oh, sorry! I forgot that!
 
> and nit, I don't understand what you intend by 'const unsigned int'. I
> think we can remove this const safely. it's more easy readable.

O.K. Will resend.

Apart from that, what didn't work as you expected?

Bruno

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

[KOSAKI Motohiro]

> > and nit, I don't understand what you intend by 'const unsigned int'. I
> > think we can remove this const safely. it's more easy readable.
> 
> O.K. Will resend.
> 
> Apart from that, what didn't work as you expected?

It works. I meant this const has no meaning.


few additional reviewing comments is here.


> +struct ewma {
> +	unsigned int internal;
> +	unsigned int factor;
> +	unsigned int weight;
> +};

I think unsigned long is better because long is natual register size
on both 32bit and 64bit arch.
and, example, almost linux resource limit is using long or ulong. then
uint may have overflow risk if we are using this one on 64bit arch.
Does uint has any benefit? (note: scheduler loadavg has already used ulong)

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

Hm, if ewma_add has this function prototype, we almost always need to
typing "new = ewma_get(ewma_add(&ewma, val))". Is this intentional?
if so, why?

Why can't we simple do following?

unsigned long ewma_add(struct ewma *avg, const unsigned int val)
{
(snip)
	return ewma_get(avg);
}

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

[Bruno Randolf]

On Fri October 22 2010 10:11:38 KOSAKI Motohiro wrote:
> few additional reviewing comments is here.
> 
> > +struct ewma {
> > +	unsigned int internal;
> > +	unsigned int factor;
> > +	unsigned int weight;
> > +};
> 
> I think unsigned long is better because long is natual register size
> on both 32bit and 64bit arch.
> and, example, almost linux resource limit is using long or ulong. then
> uint may have overflow risk if we are using this one on 64bit arch.
> Does uint has any benefit? (note: scheduler loadavg has already used ulong)

You know more about this than me. I have no specific reason to use unsigned 
int. I'll change it to unsigned long, if that's better.

> > +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;
> 
> Hm, if ewma_add has this function prototype, we almost always need to
> typing "new = ewma_get(ewma_add(&ewma, val))". Is this intentional?
> if so, why?
>
> Why can't we simple do following?
> 
> unsigned long ewma_add(struct ewma *avg, const unsigned int val)
> {
> (snip)
> 	return ewma_get(avg);
> }

Hmm, I guess that depends on the way you want to use it. In my case, most of 
the times when I add a value to the average, I don't need to get the value. 
I'd call ewma_add() many more times than ewma_get(). Having the functions 
defined like this gives us the flexibility to choose and IMHO  
ewma_get(ewma_add(&ewma, val)) isn't so bad?

bruno

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

[KOSAKI Motohiro]

> On Fri October 22 2010 10:11:38 KOSAKI Motohiro wrote:
> > few additional reviewing comments is here.
> > 
> > > +struct ewma {
> > > +	unsigned int internal;
> > > +	unsigned int factor;
> > > +	unsigned int weight;
> > > +};
> > 
> > I think unsigned long is better because long is natual register size
> > on both 32bit and 64bit arch.
> > and, example, almost linux resource limit is using long or ulong. then
> > uint may have overflow risk if we are using this one on 64bit arch.
> > Does uint has any benefit? (note: scheduler loadavg has already used ulong)
> 
> You know more about this than me. I have no specific reason to use unsigned 
> int. I'll change it to unsigned long, if that's better.

Thank you.


> > > +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;
> > 
> > Hm, if ewma_add has this function prototype, we almost always need to
> > typing "new = ewma_get(ewma_add(&ewma, val))". Is this intentional?
> > if so, why?
> >
> > Why can't we simple do following?
> > 
> > unsigned long ewma_add(struct ewma *avg, const unsigned int val)
> > {
> > (snip)
> > 	return ewma_get(avg);
> > }
> 
> Hmm, I guess that depends on the way you want to use it. In my case, most of 
> the times when I add a value to the average, I don't need to get the value. 
> I'd call ewma_add() many more times than ewma_get(). Having the functions 
> defined like this gives us the flexibility to choose and IMHO  
> ewma_get(ewma_add(&ewma, val)) isn't so bad?

OK. I've got it. I agree we don't change this. Thank you for very
quick responce!