Add generic exponentially weighted moving average function
PATCH v2 1/1 Add generic exponentially weighted moving average function
This adds a generic exponentially weighted moving average function. This implementation makes use of a structure which keeps a scaled up internal representation to reduce rounding errors.
The idea for this implementation comes from the rt2x00 driver (rt2x00link.c) and I would like to use it in several places in the mac80211 and ath5k code.
--
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 | 37 +++++++++++++++++++++++++++++++++++++ 1 files changed, 37 insertions(+), 0 deletions(-) create mode 100644 include/linux/average.h
include/linux/average.h new file +37 -0
@@ -0,0 +1,37 @@ +#ifndef _LINUX_AVERAGE_H +#define _LINUX_AVERAGE_H + +#define AVG_FACTOR 1000 + +struct avg_val { +int value; +int internal; +}; + +/** +* moving_average() - Exponentially weighted moving average (EWMA) +* @avg: Average structure +* @val: Current value +* @weight: This defines how fast the influence of older values decreases. +* Has to be higher than 1. Use the same number every time you call this +* function for a single struct avg_val! +* +* This implementation make use of a struct avg_val which keeps a scaled up +* internal representation to prevent rounding errors. Due to this, the maximum +* range of values is MAX_INT/(AVG_FACTOR*weight). +* +* The current average value can be accessed by using avg_val.value. +*/ +static inline void +moving_average (struct avg_val *avg,const int val,const int weight) +{ +if (WARN_ON_ONCE (weight <=1 )) +return ; + avg->internal = avg->internal ? + (((avg->internal * (weight -1 )) + + (val *AVG_FACTOR )) / weight) : + (val *AVG_FACTOR ); + avg->value =DIV_ROUND_CLOSEST (avg->internal,AVG_FACTOR ); +} + +#endif /* _LINUX_AVERAGE_H */
Quoted 9 lines · Bruno Randolf
This adds a generic exponentially weighted moving average function. This implementation makes use of a structure which keeps a scaled up internal representation to reduce rounding errors.
The idea for this implementation comes from the rt2x00 driver (
rt2x00link.c) and I would like to use it in several places in the mac80211 and ath5k code.Signed-off-by Bruno Randolf <[email protected]>
Sorry for the resend, gmail auto-switched to html.
Probably not worth the paper it's written on, but fwiw:
Quoted 54 lines
--
v2: Renamed 'samples' to 'weight'. Added more documentation. Useavg_valpointer. Add aWARN_ON_ONCEfor invalid values of 'weight'. Divide and round up/down.
---
include/linux/average.h | 37 +++++++++++++++++++++++++++++++++++++1 files changed, 37 insertions(+), 0 deletions(-)create mode 100644
include/linux/average.hinclude/linux/average.h new file +37
-0@@ -0,0 +1,37 @@ +#ifndef _LINUX_AVERAGE_H +#define _LINUX_AVERAGE_H + +#define AVG_FACTOR 1000 + +struct avg_val { + int value; + int internal; +}; + +/** +* moving_average() - Exponentially weighted moving average (EWMA) +* @avg: Average structure +* @val: Current value +* @weight: This defines how fast the influence of older values decreases. +* Has to be higher than 1. Use the same number every time you call this +* function for a single struct avg_val! +* +* This implementation make use of a struct avg_val which keeps a scaled up +* internal representation to prevent rounding errors. Due to this, the maximum +* range of values is MAX_INT/(AVG_FACTOR*weight). +* +* The current average value can be accessed by using avg_val.value. +*/ +static inline void +moving_average (struct avg_val *avg,const int val,const int weight) +{ + if (WARN_ON_ONCE(weight <= 1)) + return; + avg->internal = avg->internal ? + (((avg->internal * (weight - 1)) + + (val * AVG_FACTOR)) / weight) : + (val * AVG_FACTOR); + avg->value = DIV_ROUND_CLOSEST(avg->internal, AVG_FACTOR); +} + +#endif /* _LINUX_AVERAGE_H */
Quoted 8 lines · On Tue, 19 Oct 2010 17:36:35 +0900 Bruno Randolf wrote:
This adds a generic exponentially weighted moving average function. This implementation makes use of a structure which keeps a scaled up internal representation to reduce rounding errors.
The idea for this implementation comes from the rt2x00 driver (
rt2x00link.c) and I would like to use it in several places in the mac80211 and ath5k code.Signed-off-by Bruno Randolf <[email protected]>
Quoted 43 lines
--
v2: Renamed 'samples' to 'weight'. Added more documentation. Useavg_val
pointer. Add aWARN_ON_ONCEfor invalid values of 'weight'. Divide and round up/down.--- include/linux/average.h | 37 +++++++++++++++++++++++++++++++++++++ 1 files changed, 37 insertions(+), 0 deletions(-) create mode 100644 include/linux/average.hinclude/linux/average.h new file +27
-0@@ -0,0 +1,37 @@ +#ifndef _LINUX_AVERAGE_H +#define _LINUX_AVERAGE_H + +#define AVG_FACTOR 1000 + +struct avg_val { +int value; +int internal; +}; + +/** +* moving_average() - Exponentially weighted moving average (EWMA) +* @avg: Average structure +* @val: Current value +* @weight: This defines how fast the influence of older values decreases. +* Has to be higher than 1. Use the same number every time you call this +* function for a single struct avg_val! +* +* This implementation make use of a struct avg_val which keeps a scaled up +* internal representation to prevent rounding errors. Due to this, the maximum +* range of values is MAX_INT/(AVG_FACTOR*weight). +* +* The current average value can be accessed by using avg_val.value. +*/ +static inline void +moving_average (struct avg_val *avg,const int val,const int weight) +{
include/linux/average.h line 37
Quoted 10 lines
include/linux/average.h new file +10
-0+if (WARN_ON_ONCE (weight <=1 )) +return ; + avg->internal = avg->internal ? + (((avg->internal * (weight -1 )) + + (val *AVG_FACTOR )) / weight) : + (val *AVG_FACTOR ); + avg->value = DIV_ROUND_CLOSEST(avg->internal, AVG_FACTOR); +} + +#endif /* _LINUX_AVERAGE_H */
---
~Randy
*** Remember to use Documentation/SubmitChecklist when testing your code ***
Andrew Morton
maintainerQuoted 9 lines · On Tue, 19 Oct 2010 17:36:35 +0900 Bruno Randolf <[email protected]> wrote:
This adds a generic exponentially weighted moving average function. This implementation makes use of a structure which keeps a scaled up internal representation to reduce rounding errors.
The idea for this implementation comes from the rt2x00 driver (
rt2x00link.c) and I would like to use it in several places in the mac80211 and ath5k code.Signed-off-by Bruno Randolf <[email protected]>
hm, interesting. I suspect there are a few places in MM/VFS/writeback which could/should be using something like this. Of course, if we do this then your nice little function will end up 250 lines long, utterly incomprehensible and full of subtle bugs. We like things to be that way.
Thanks for proposing it as generic code, btw. Let's merge it and see what happens.
Quoted 33 lines
include/linux/average.h new file +27
-0@@ -0,0 +1,37 @@ +#ifndef _LINUX_AVERAGE_H +#define _LINUX_AVERAGE_H + +#define AVG_FACTOR 1000 + +struct avg_val { +int value; +int internal; +}; + +/** +* moving_average() - Exponentially weighted moving average (EWMA) +* @avg: Average structure +* @val: Current value +* @weight: This defines how fast the influence of older values decreases. +* Has to be higher than 1. Use the same number every time you call this +* function for a single struct avg_val! +* +* This implementation make use of a struct avg_val which keeps a scaled up +* internal representation to prevent rounding errors. Due to this, the maximum +* range of values is MAX_INT/(AVG_FACTOR*weight). +* +* The current average value can be accessed by using avg_val.value. +*/ +static inline void +moving_average (struct avg_val *avg,const int val,const int weight) +{
include/linux/average.h line 37
Quoted 10 lines
include/linux/average.h new file +10
-0+if (WARN_ON_ONCE (weight <=1 )) +return ; + avg->internal = avg->internal ? + (((avg->internal * (weight -1 )) + + (val *AVG_FACTOR )) / weight) : + (val *AVG_FACTOR ); + avg->value = DIV_ROUND_CLOSEST(avg->internal, AVG_FACTOR); +} + +#endif /* _LINUX_AVERAGE_H */
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Andrew Morton
maintainerQuoted 13 lines · On Tue, 19 Oct 2010 15:37:56 -0700 Andrew Morton <[email protected]>…
Quoted 9 lines · On Tue, 19 Oct 2010 17:36:35 +0900 Bruno Randolf <[email protected]> wrote:
This adds a generic exponentially weighted moving average function. This implementation makes use of a structure which keeps a scaled up internal representation to reduce rounding errors.
The idea for this implementation comes from the rt2x00 driver (
rt2x00link.c) and I would like to use it in several places in the mac80211 and ath5k code.Signed-off-by Bruno Randolf <[email protected]>
Quoted 7 lines
hm, interesting. I suspect there are a few places in MM/VFS/writeback which could/should be using something like this. Of course, if we do this then your nice little function will end up 250 lines long, utterly incomprehensible and full of subtle bugs. We like things to be that way.
Thanks for proposing it as generic code, btw. Let's merge it and see what happens.
I looked at the code..
Quoted 10 lines
include/linux/average.h line 4
Quoted 10 lines
include/linux/average.h new file +4
-0@@ -0,0 +1,37 @@ +#ifndef _LINUX_AVERAGE_H +#define _LINUX_AVERAGE_H + +#define AVG_FACTOR 1000
Can you please document the magic number? What does it do? I'd have though it likely that one day this will become variable, initialised in moving_average_init().
Quoted 4 lines
include/linux/average.h line 9
Quoted 4 lines
include/linux/average.h new file +4
-0+struct avg_val { +int value; +int internal; +};
So it's using integer types.
I guess that makes sense, maybe. Does your application use negative quantities? They're pretty rare beasts in the kernel. I expect most callers will want an unsigned type?
Quoted 17 lines
Quoted 17 lines
include/linux/average.h new file +17
-0+/** +* moving_average() - Exponentially weighted moving average (EWMA) +* @avg: Average structure +* @val: Current value +* @weight: This defines how fast the influence of older values decreases. +* Has to be higher than 1. Use the same number every time you call this +* function for a single struct avg_val! +* +* This implementation make use of a struct avg_val which keeps a scaled up +* internal representation to prevent rounding errors. Due to this, the maximum +* range of values is MAX_INT/(AVG_FACTOR*weight). +* +* The current average value can be accessed by using avg_val.value. +*/ +static inline void +moving_average (struct avg_val *avg,const int val,const int weight) +{
Quoted 8 lines
include/linux/average.h line 35
Quoted 8 lines
include/linux/average.h new file +8
-0+if (WARN_ON_ONCE (weight <=1 )) +return ; + avg->internal = avg->internal ? + (((avg->internal * (weight -1 )) + + (val *AVG_FACTOR )) / weight) : + (val *AVG_FACTOR ); + avg->value =DIV_ROUND_CLOSEST (avg->internal,AVG_FACTOR ); +}
This function is really already too large to be inlined, and I'd suggest that lib/moving_average.c would be a better home for it.
Is it expected that weight' will have the same value for all calls of moving_average() against a particular avg_val? If so then perhaps we should do away with this argument and place weight' into the avg_val struct, and set that up in moving_average_init().
And I do think that we need a moving_average_init(), because at present you require that callers initialise the avg_val() by hand. This means that if we later add more fields to that struct, all callers will need to be updated. Any which are out-of-tree will have been made buggy.
Also, perhaps moving_average() should end with a
return avg->value;
for convenience on the callers side. Or maybe not - I haven't looked at any calling code...
Finally, it's a little ugly to have callers poking around inside the avg_val to get the current average. The main problem with this is that it restricts future implementations: they must maintain their average in avg_val.value. If they instead were to call
moving_average_read(struct avg_val *)
then we get more freedom regarding future implementations. The current moving_average_read() could be inlined. That would require that avg_val be defined in the header file rather than in .c. This is a bit sad, but acceptable.
And finally+1: moving_average() needs locking to protect internal state. Right now, the caller must provide that locking. And that's a fine design IMO - we have no business here assuming that we can use mutex_lock() or spin_lock() or spin_lock_irq() or spin_lock_irqsave() - let the caller decide that.
But the need for this caller-provided locking should be described in the API documentation, please.
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>
Quoted 1 line · On Wed October 20 2010 07:54:06 Andrew Morton wrote:
I looked at the code..
Thank you for your review!
Quoted 5 lines
Quoted 1 line
Quoted 1 line
+#define
AVG_FACTOR1000Can you please document the magic number? What does it do? I'd have though it likely that one day this will become variable, initialised in
moving_average_init().
OK. I thought I'd get away without it ;) but you convinced me it's better to have a moving_average_init().
Quoted 10 lines
Quoted 4 lines
include/linux/average.h line 9
Quoted 4 lines
include/linux/average.h new file +4
-0+struct avg_val { +int value; +int internal; +};So it's using integer types.
I guess that makes sense, maybe. Does your application use negative quantities? They're pretty rare beasts in the kernel. I expect most callers will want an unsigned type?
I want to use it with negative numbers (signal strength in dBm), but it's easy enough to convert them to positive numbers, so I'll change the variables to unsigned. I guess averaging between positive and negative numbers is really rare...
Quoted 6 lines
Quoted 6 lines
Quoted 6 lines
include/linux/average.h new file +6
-0+static inline void +moving_average (struct avg_val *avg,const int val,const int weight) +{ +if (WARN_ON_ONCE (weight <=1 )) +return ; + avg->internal = avg->internal ?
Quoted 8 lines
Quoted 5 lines
include/linux/average.h line 35
Quoted 5 lines
include/linux/average.h new file +5
-0+ (((avg->internal * (weight -1 )) + + (val * AVG_FACTOR)) / weight) : + (val *AVG_FACTOR ); + avg->value =DIV_ROUND_CLOSEST (avg->internal,AVG_FACTOR ); +}This function is really already too large to be inlined, and I'd suggest that
lib/moving_average.cwould be a better home for it.
OK. Maybe we could call it lib/average.c so other averaging implementations - should there be any in the future - could go there as well?
Quoted 4 lines
Is it expected that
weight' will have the same value for all calls of moving_average() against a particular avg_val? If so then perhaps we should do away with this argument and placeweight' into theavg_valstruct, and set that up inmoving_average_init().
Yes. So I'll make a moving_average_init(scaling_factor, weight).
Quoted 4 lines
And I do think that we need a
moving_average_init(), because at present you require that callers initialise theavg_val()by hand. This means that if we later add more fields to that struct, all callers will need to be updated. Any which are out-of-tree will have been made buggy.
Well, the initialization we currently require is just to make sure is is zeroed out... But I agree to the other benefits using an init function.
Quoted 6 lines
Also, perhaps
moving_average()should end with areturn avg->value;for convenience on the callers side. Or maybe not - I haven't looked at any calling code...
Ok. No problem.
Quoted 11 lines
Finally, it's a little ugly to have callers poking around inside the
avg_valto get the current average. The main problem with this is that it restricts future implementations: they must maintain their average in avg_val.value. If they instead were to call
moving_average_read(struct avg_val *)then we get more freedom regarding future implementations. The current
moving_average_read()could be inlined. That would require thatavg_valbe defined in the header file rather than in .c. This is a bit sad, but acceptable.
I see.
Quoted 8 lines
And finally+1:
moving_average()needs locking to protect internal state. Right now, the caller must provide that locking. And that's a fine design IMO - we have no business here assuming that we can usemutex_lock()orspin_lock()orspin_lock_irq()orspin_lock_irqsave()- let the caller decide that.But the need for this caller-provided locking should be described in the API documentation, please.
Will do that and resend an improved version shortly.
Thanks,
Bruno
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>