Skip to contentSkip to conversation

Add generic exponentially weighted moving average (EWMA) function

PATCH Superseded Bruno Randolf 5 participants 13 messages Nov 11, 2010 – Nov 15, 2010 Library code

v6 of 8 Superseded Latest is v8 →

lore
Share & tools
lore
#0 lore raw

PATCH v6 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.

--

Excuse me, but can I expect this to be merged anytime soon? Where do I check if it got merged? I'm resending the patch in case it got lost.

Thanks,
bruno

--

v6: Fixed ULONG_MAX in comment. Add reviewed by KOSAKI Motohiro.

v5: Use unsigned long instead of insigned int.

v4: Initialize internal variable to 0. Remove unneeded const qualifiers.

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           |   58 +++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 91 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..f3b36d4
@@ -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 long internal;
+	unsigned long factor;
+	unsigned long weight;
+};
+
+extern struct ewma *ewma_init(struct ewma *avg, unsigned long factor,
+			      unsigned long weight);
+
+extern struct ewma *ewma_add(struct ewma *avg, unsigned long val);
+
+/**
+ * ewma_get() - Get average value
+ * @avg: Average structure
+ *
+ * Returns the average value held in @avg.
+ */
+static inline unsigned long 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 +58 -0

58 lines not on this page · raw message

maintainer
#1 lore raw
Quoted 9 lines · On Thu, 11 Nov 2010 12:47:56 +0900 Bruno Randolf <[email protected]> wrote:

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.

Quoted 7 lines

--

Excuse me, but can I expect this to be merged anytime soon? Where do I check if it got merged? I'm resending the patch in case it got lost.

Yes, sorry, this is buried in my exponentially increasing backlog. It's going to take me a while to catch up again.

Unless I just merge stuff without looking at it. hm, I wonder if that would make any difference??

Quoted 10 lines

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

<reads Documentation/kernel-doc-nano-HOWTO.txt>

Well, I never knew about "DOC:".

#2 lore raw
Quoted 14 lines · On Thu November 11 2010 12:53:29 Andrew Morton wrote:
Quoted 13 lines · On Thu, 11 Nov 2010 12:47:56 +0900 Bruno Randolf <[email protected]> wrote:

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.

Quoted 7 lines
Quoted 4 lines

--

Excuse me, but can I expect this to be merged anytime soon? Where do I check if it got merged? I'm resending the patch in case it got lost.

Yes, sorry, this is buried in my exponentially increasing backlog. It's going to take me a while to catch up again.

I don't mean to be pushy, so please take your time...

bruno

maintainer
#3 lore raw
In reply to Bruno Randolf
Quoted 12 lines · On Thu, 11 Nov 2010 12:47:56 +0900 Bruno Randolf <[email protected]> wrote:

...

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.

...

lib/Makefile lib-y += kobject.o kref.o klist.o · line 24

Quoted 5 lines
lib/Makefile +1 -1
@@ -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

It would be a bit strange to merge this into 2.6.36-rcX when there are no callers. But you do want it to be present in some tree for your own testing and distribution purposes.

So perhaps it would be best to merge this via the wireless tree, so everything exists in one place and it can be fed into linux-next and into mainline in an orderly fashion.

If that sounds like a plan then I can send this patch in John's direction. Which means that if he merges it into mainline without also merging any of your patches which _use_ this function then we still end up with unused code in mainline, but at least that way it wasn't my fault ;)

Let me know your thoughts?

(And it's a bit sad that the function will exist in the base vmlinux even for people who don't ever use it, but that's a problem which we don't really have a good solution for).

#4 lore raw
Quoted 30 lines · On Thu November 11 2010 13:02:31 Andrew Morton wrote:
Quoted 12 lines · On Thu, 11 Nov 2010 12:47:56 +0900 Bruno Randolf <[email protected]> wrote:

...

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.

...

lib/Makefile lib-y += kobject.o kref.o klist.o · line 27

Quoted 8 lines
lib/Makefile +1 -1
@@ -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

It would be a bit strange to merge this into 2.6.36-rcX when there are no callers. But you do want it to be present in some tree for your own testing and distribution purposes.

So perhaps it would be best to merge this via the wireless tree, so everything exists in one place and it can be fed into linux-next and into mainline in an orderly fashion.

Quoted 7 lines

If that sounds like a plan then I can send this patch in John's direction. Which means that if he merges it into mainline without also merging any of your patches which _use_ this function then we still end up with unused code in mainline, but at least that way it wasn't my fault ;)

Let me know your thoughts?

Sounds like a good plan to me. But let's hear Johns opinion.

I have a patch or two using this function, which I hope will get merged into wireless-testing soon after, but obviously it's up to John. There are more places in the wireless part which could make use of this function (right now each have their own EWMA implementation), and I'll try to get them all updated, but finally it's the individual maintainers, who decide if they want to make that change or not, I guess.

Quoted 3 lines

(And it's a bit sad that the function will exist in the base vmlinux even for people who don't ever use it, but that's a problem which we don't really have a good solution for).

Hmm, should I switch it back to all inlines?

On the other hand, if a generic EWMA function is useful at all I guess it could be used in many places all over the kernel. Unfortunately I don't have time and knowledge to find all these places and update them to use the generic code.

bruno

#5 lore raw
Quoted 13 lines · Bruno Randolf
Quoted 11 lines · On Thu November 11 2010 13:02:31 Andrew Morton wrote:

So perhaps it would be best to merge this via the wireless tree, so everything exists in one place and it can be fed into linux-next and into mainline in an orderly fashion.

If that sounds like a plan then I can send this patch in John's direction. Which means that if he merges it into mainline without also merging any of your patches which _use_ this function then we still end up with unused code in mainline, but at least that way it wasn't my fault ;)

Let me know your thoughts?

Quoted 8 lines

Sounds like a good plan to me. But let's hear Johns opinion.

I have a patch or two using this function, which I hope will get merged into wireless-testing soon after, but obviously it's up to John. There are more places in the wireless part which could make use of this function (right now each have their own EWMA implementation), and I'll try to get them all updated, but finally it's the individual maintainers, who decide if they want to make that change or not, I guess.

It seems totally clear-cut to me that code like this is submitted together with at least one call site, and it is submitted through the tree in which that call site is maintained.

Quoted 5 lines
Quoted 3 lines

(And it's a bit sad that the function will exist in the base vmlinux even for people who don't ever use it, but that's a problem which we don't really have a good solution for).

Hmm, should I switch it back to all inlines?

Add a hidden Kconfig variable for it which is SELECTed by those Kconfig prompts that require it? That's the good solution that we use for a number of similar library functions.

$ cat lib/Makefile
Quoted 4 lines

On the other hand, if a generic EWMA function is useful at all I guess it could be used in many places all over the kernel. Unfortunately I don't have time and knowledge to find all these places and update them to use the generic code.

Don't worry. There are people who specialize in this sort of activity.

Two remarks on your patch:

You use WARN_ON in lib/average.c. You should include <linux/bug.h>.

Why do ewma_init() and ewma_add() return their first argument? They look to me like they can be straight-forward void functions.

Signature · 3 lines
Stefan Richter
-=====-==-=- =-== -=-==
http://arcgraph.de/sr/
#6 lore raw
Quoted 3 lines · On Fri November 12 2010 03:17:34 Stefan Richter wrote:

It seems totally clear-cut to me that code like this is submitted together with at least one call site, and it is submitted through the tree in which that call site is maintained.

Ok. So I'll re-send the patch thru John's wireless tree after I fixed up your comments.

Quoted 10 lines
Quoted 5 lines
Quoted 3 lines

(And it's a bit sad that the function will exist in the base vmlinux even for people who don't ever use it, but that's a problem which we don't really have a good solution for).

Hmm, should I switch it back to all inlines?

Add a hidden Kconfig variable for it which is SELECTed by those Kconfig prompts that require it? That's the good solution that we use for a number of similar library functions.

$ cat lib/Makefile

Ok.

Quoted 1 line

You use WARN_ON in lib/average.c. You should include <linux/bug.h>.

Thanks.

Quoted 2 lines

Why do ewma_init() and ewma_add() return their first argument? They look to me like they can be straight-forward void functions.

You are right, for ewma_init() it does not make sense.

For ewma_add() I think it does. This has been discussed before (e.g.
http://linux.derkeiler.com/Mailing-Lists/Kernel/2010-10/msg09124.html).
Some people might want to get the value when they add a sample by using ewma_get(ewma_add(&ewma, val));

Bruno

#7 lore raw
Quoted 9 lines
Quoted 2 lines

Why do ewma_init() and ewma_add() return their first argument? They look to me like they can be straight-forward void functions.

You are right, for ewma_init() it does not make sense.

For ewma_add() I think it does. This has been discussed before (e.g.
http://linux.derkeiler.com/Mailing-Lists/Kernel/2010-10/msg09124.html).
Some people might want to get the value when they add a sample by using ewma_get(ewma_add(&ewma, val));

	ewma_add(&ewma, val);
	ewma_get(&ewma);

is enough simpler and cleaner. I don't oppse this :)

#8 lore raw
Quoted 9 lines · KOSAKI Motohiro
Quoted 8 lines
Quoted 2 lines

Why do ewma_init() and ewma_add() return their first argument? They look to me like they can be straight-forward void functions.

You are right, for ewma_init() it does not make sense.

For ewma_add() I think it does. This has been discussed before (e.g.
http://linux.derkeiler.com/Mailing-Lists/Kernel/2010-10/msg09124.html).
Some people might want to get the value when they add a sample by using ewma_get(ewma_add(&ewma, val));

Quoted 4 lines
	ewma_add(&ewma, val);
	ewma_get(&ewma);

is enough simpler and cleaner. I don't oppse this :)

There are more candidate colors for the bike shed: :-)
- an ewma_add_return could do what ewma_get(ewma_add(...)) is meant for,
- or ewma_add itself could return the result.

BTW, isn't "get" more usually used as a prefix for these kinds of functions in kernel APIs? "get" as a suffix more often means "get a reference" alias increase reference count rather than "get the value".

Signature · 3 lines
Stefan Richter
-=====-==-=- =-== -===-
http://arcgraph.de/sr/
#9 lore raw
Quoted 10 lines · On Sun November 14 2010 17:51:08 Stefan Richter wrote:
Quoted 10 lines
Quoted 10 lines
Quoted 2 lines

Why do ewma_init() and ewma_add() return their first argument? They look to me like they can be straight-forward void functions.

You are right, for ewma_init() it does not make sense.

For ewma_add() I think it does. This has been discussed before (e.g.
http://linux.derkeiler.com/Mailing-Lists/Kernel/2010-10/msg09124.html).
Some people might want to get the value when they add a sample by using ewma_get(ewma_add(&ewma, val));

Quoted 7 lines
Quoted 4 lines
	ewma_add(&ewma, val);
	ewma_get(&ewma);

is enough simpler and cleaner. I don't oppse this :)

There are more candidate colors for the bike shed: :-)
- an ewma_add_return could do what ewma_get(ewma_add(...)) is meant for,

I think this would be overkill. We're just talking about a return pointer...

Quoted 1 line

- or ewma_add itself could return the result.

The way I intend to use it, I will add samples much more often than I get a value, so IMHO it makes sense to split it.

Quoted 3 lines

BTW, isn't "get" more usually used as a prefix for these kinds of functions in kernel APIs? "get" as a suffix more often means "get a reference" alias increase reference count rather than "get the value".

Umm. I don't know and honstly I don't care. I think the API ewma_* is consistent. If you have a good reason to change it please let me know, otherwise i'd just leave it like it is now.

bruno

#10 lore raw
Quoted 9 lines · On Nov 15 Bruno Randolf wrote:
Quoted 4 lines · On Sun November 14 2010 17:51:08 Stefan Richter wrote:

BTW, isn't "get" more usually used as a prefix for these kinds of functions in kernel APIs? "get" as a suffix more often means "get a reference" alias increase reference count rather than "get the value".

Umm. I don't know and honstly I don't care. I think the API ewma_* is consistent. If you have a good reason to change it please let me know, otherwise i'd just leave it like it is now.

It is not about consistency of the API in itself but about consistency with the rest of the kernel. Cf. skb_get vs. get_unaligned and many more. I for one immediately think of "something is having its reference count incremented here" when I come across a something_get when reading code.

I don't know of such a convention being documented anywhere. But for an overkill of examples of "get" as prefix and suffix, grep for get_ and _get( in include/. The same convention exists IME with "put" that either writes a value or drops a reference.

Sorry for bringing this up so late but it is IMO not a trivial point.

Signature · 3 lines
Stefan Richter
-=====-==-=- =-== -====
http://arcgraph.de/sr/
#11 lore raw
Quoted 17 lines · On Mon November 15 2010 16:38:39 Stefan Richter wrote:
Quoted 9 lines · On Nov 15 Bruno Randolf wrote:
Quoted 4 lines · On Sun November 14 2010 17:51:08 Stefan Richter wrote:

BTW, isn't "get" more usually used as a prefix for these kinds of functions in kernel APIs? "get" as a suffix more often means "get a reference" alias increase reference count rather than "get the value".

Umm. I don't know and honstly I don't care. I think the API ewma_* is consistent. If you have a good reason to change it please let me know, otherwise i'd just leave it like it is now.

It is not about consistency of the API in itself but about consistency with the rest of the kernel. Cf. skb_get vs. get_unaligned and many more. I for one immediately think of "something is having its reference count incremented here" when I come across a something_get when reading code.

Quoted 6 lines

I don't know of such a convention being documented anywhere. But for an overkill of examples of "get" as prefix and suffix, grep for get_ and _get( in include/. The same convention exists IME with "put" that either writes a value or drops a reference.

Sorry for bringing this up so late but it is IMO not a trivial point.

That's allright, and I have no problem changing it.

So what would you prefer? And what is the opinion of other people?

bruno

#12 lore raw
Quoted 1 line · Bruno Randolf

So what would you prefer? And what is the opinion of other people?

ewma_read()