Skip to contentSkip to conversation

Add generic exponentially weighted moving average (EWMA) function

PATCH Superseded Bruno Randolf 3 participants 9 messages Oct 20, 2010 – Oct 22, 2010 Library code

v3 of 8 Superseded Latest is v8 →

lore
Share & tools
lore
#0 lore raw

PATCH v3 1/1 Add generic exponentially weighted moving average (EWMA) function

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.

--
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
include/linux/average.h new file +32 -0
new file mode 100644
index 0000000..56bef6c
@@ -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 */
lib/Makefile +1 -1
index e6a3763..f66acf7 100644
@@ -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
lib/average.c new file +59 -0

59 lines not on this page · raw message

#1 lore raw
Quoted 7 lines · Bruno Randolf
lib/average.c new file +7 -0
+/**
+ * ewma_add() - Exponentially weighted moving average (EWMA)
+ * @avg: Average structure
+ * @val: Current value
+ *
+ * Add a sample to the average.
+ */

lib/average.c line 59

Quoted 10 lines
lib/average.c new file +10 -0
+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?

#2 lore raw
Quoted 12 lines · On Thu October 21 2010 00:03:43 Peter Zijlstra wrote:
Quoted 11 lines · Bruno Randolf
lib/average.c new file +11 -0
+/**
+ * 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  ?
Quoted 8 lines

lib/average.c line 59

Quoted 6 lines
lib/average.c new file +6 -0
+               (((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

#3 lore raw
Quoted 22 lines · Bruno Randolf
Quoted 12 lines · On Thu October 21 2010 00:03:43 Peter Zijlstra wrote:
Quoted 11 lines · Bruno Randolf
lib/average.c new file +11 -0
+/**
+ * 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  ?
Quoted 8 lines

lib/average.c line 59

Quoted 6 lines
lib/average.c new file +6 -0
+               (((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?

Quoted 3 lines

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.

#4 lore raw
In reply to Bruno Randolf

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.

Quoted 10 lines
lib/average.c new file +10 -0
+/**
+ * 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.
+ */

lib/average.c line 41

Quoted 10 lines
lib/average.c new file +10 -0
+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.

#5 lore raw
Quoted 21 lines · 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.

Quoted 14 lines

+/**
+ * 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.
+ */

lib/average.c new file +4 -0
+struct ewma*
+ewma_init(struct ewma *avg, const unsigned int factor,
+	  const unsigned int weight)
+{
Quoted 8 lines

lib/average.c line 41

Quoted 6 lines
lib/average.c new file +6 -0
+	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!

Quoted 2 lines

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

#6 lore raw
Quoted 6 lines
Quoted 2 lines

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.

include/linux/average.h line 14

Quoted 5 lines
include/linux/average.h new file +5 -0
+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)

lib/average.c line 57

Quoted 8 lines
lib/average.c new file +8 -0
+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);
}
#7 lore raw
Quoted 13 lines · On Fri October 22 2010 10:11:38 KOSAKI Motohiro wrote:

few additional reviewing comments is here.

include/linux/average.h line 14

Quoted 5 lines
include/linux/average.h new file +5 -0
+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.

Quoted 13 lines

lib/average.c line 57

Quoted 8 lines
lib/average.c new file +8 -0
+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?

Quoted 7 lines

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

#8 lore raw
Quoted 15 lines · On Fri October 22 2010 10:11:38 KOSAKI Motohiro wrote:
Quoted 13 lines

few additional reviewing comments is here.

include/linux/average.h line 14

Quoted 5 lines
include/linux/average.h new file +5 -0
+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)

Quoted 2 lines

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.

Quoted 21 lines
Quoted 13 lines

lib/average.c line 57

Quoted 8 lines
lib/average.c new file +8 -0
+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?

Quoted 7 lines

Why can't we simple do following?

unsigned long ewma_add(struct ewma *avg, const unsigned int val) {
(snip)

	return ewma_get(avg);
}
Quoted 5 lines

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!