Add generic exponentially weighted moving average function
PATCH 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.
--
Is this the right place to add it? Who to CC:?
--- include/linux/average.h | 32 ++++++++++++++++++++++++++++++++ 1 files changed, 32 insertions(+), 0 deletions(-) create mode 100644 include/linux/average.h
include/linux/average.h new file +32 -0
@@ -0,0 +1,32 @@ +#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 +* @avg: average structure +* @val: current value +* @samples: number of samples +* +* This implementation make use of a struct avg_val to prevent rounding +* errors. +*/ +static inline struct avg_val +moving_average (const struct avg_val avg,const int val,const int samples) +{ +struct avg_val ret; + ret.internal = avg.internal ? + (((avg.internal * (samples -1 )) + + (val *AVG_FACTOR )) / samples) : + (val *AVG_FACTOR ); + ret.value = ret.internal /AVG_FACTOR ; +return ret; +} + +#endif /* _LINUX_AVERAGE_H */
Quoted 8 lines · On Wed, 06 Oct 2010 18:32:25 +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]>
I guess I don't understand "exponentially weighted" or why that would be desirable. Please try to explain (briefly).
I'm attaching a test program that I did. I don't especially like the results of it. Maybe it's due to the exponential weighting. (?)
The test program tells me that the sum of 3 samples is 8 & average = 2:
i.e., not rounded up.
And that the sum of 6 samples is 30 & average = 4. (!!) And that the sum of 10 samples is 80 & average = 5. (!!)
Am I just not understanding the function or am I misusing it?
Complete test program output:
Quoted 1 line
./moving-avg
count: 1, val: 1, sum: 1, avg: 1, internal: 1000
count: 2, val: 3, sum: 4, avg: 2, internal: 2000
count: 3, val: 4, sum: 8, avg: 2, internal: 2666
count: 4, val: 6, sum: 14, avg: 3, internal: 3499
count: 5, val: 7, sum: 21, avg: 4, internal: 4199
count: 6, val: 9, sum: 30, avg: 4, internal: 4999
count: 7, val: 10, sum: 40, avg: 5, internal: 5713
count: 8, val: 12, sum: 52, avg: 6, internal: 6498
count: 9, val: 13, sum: 65, avg: 7, internal: 7220
count: 10, val: 15, sum: 80, avg: 7, internal: 7998
Quoted 5 lines
--
Is this the right place to add it? Who to CC:?
Try Andrew. (added)
Quoted 36 lines
--- include/linux/average.h | 32 ++++++++++++++++++++++++++++++++ 1 files changed, 32 insertions(+), 0 deletions(-) create mode 100644 include/linux/average.hinclude/linux/average.h new file +24
-0@@ -0,0 +1,32 @@ +#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 +* @avg: average structure +* @val: current value +* @samples: number of samples +* +* This implementation make use of a struct avg_val to prevent rounding +* errors. +*/ +static inline struct avg_val +moving_average (const struct avg_val avg,const int val,const int samples) +{ +struct avg_val ret; + ret.internal = avg.internal ?
include/linux/average.h
Quoted 10 lines
include/linux/average.h new file +8
-1+ (((avg.internal * (samples -1 )) + + (val * AVG_FACTOR)) / samples) : + (val *AVG_FACTOR ); + ret.value = ret.internal /AVG_FACTOR ; + return ret; +} + +#endif /* _LINUX_AVERAGE_H */ --
---
~Randy
*** Remember to use Documentation/SubmitChecklist when testing your code ***
#if 0
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. #endif
#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
* @avg: average structure
* @val: current value
* @samples: number of samples
*
* This implementation make use of a struct avg_val to prevent rounding
* errors.
*/
static inline struct avg_valmoving_average(const struct avg_val avg, const int val, const int samples)
{
struct avg_val ret;
ret.internal = avg.internal ?
(((avg.internal * (samples - 1)) +
(val * AVG_FACTOR)) / samples) :
(val * AVG_FACTOR);
ret.value = ret.internal / AVG_FACTOR;
return ret;
}#endif /* _LINUX_AVERAGE_H */
#include <stdio.h>
int main(int argc, char *argv[])
{
struct avg_val avg = {};
int count;
int val;
int sum = 0;
for (count = 1; count <= 10; count++) {
val = count + count/2;
sum += val;
avg = moving_average(avg, val, count);
printf("count: %d, val: %d, sum: %d, avg: %d, internal: %d\n",
count, val, sum, avg.value, avg.internal);
}
return 0;
}Hello Randy!
Thank you for taking the time to look at this!
Quoted 5 lines · On Wed October 13 2010 09:33:52 Randy Dunlap wrote:
Quoted 4 lines · On Wed, 06 Oct 2010 18:32:25 +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.
Quoted 8 lines
Quoted 5 lines
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]>I guess I don't understand "exponentially weighted" or why that would be desirable. Please try to explain (briefly).
It just means, that more recent values are given a higher priority. The influence of older values decreases exponentially.
This is desirable if we want to have an average, but we are more interested in the recent development. One example where that makes sense is the signal strength of a station in a wireless LAN. As the signal strength can vary significantly for every packet, just looking at one packet is misleading. We are not so much interested in a long term average, as a station might move
- we are more interested in the average of the last X (say 8) packets, giving most priority to the last value.
http://en.wikipedia.org/wiki/Exponentially_weighted_moving_average#Exponential_moving_average
This is one example, but I found several places in the kernel code where something like this is used, usually open coded. That's why I tought a general function for this can make sense.
Quoted 5 lines
I'm attaching a test program that I did. I don't especially like the results of it. Maybe it's due to the exponential weighting. (?)
The test program tells me that the sum of 3 samples is 8 & average = 2:
i.e., not rounded up.
Oh, I see. I guess I should use DIV_ROUND_CLOSEST. I attach a new version of the test program.
Quoted 4 lines
And that the sum of 6 samples is 30 & average = 4. (!!) And that the sum of 10 samples is 80 & average = 5. (!!)
Am I just not understanding the function or am I misusing it?
You should keep 'samples' constant every time you call the function. It is the factor which defines how fast the influence of older values decreases. Higher values will take more older samples into account. E.g. use it like this:
moving_average(avg, val, 4);
I should have documented that better, I guess... And maybe rename it to 'factor'.
Also a moving average makes more sense when you use it more often, depending on how high 'samples' is. E.g. here is the output of the test program with 'sampes' of 4 and 20 iterations. I also print 'savg' (simple average) which is sum/count:
count: 1, val: 1, sum: 1, savg: 1, avg: 1, internal: 1000
count: 2, val: 3, sum: 4, savg: 2, avg: 2, internal: 1500
count: 3, val: 4, sum: 8, savg: 2, avg: 2, internal: 2125
count: 4, val: 6, sum: 14, savg: 3, avg: 3, internal: 3093
count: 5, val: 7, sum: 21, savg: 4, avg: 4, internal: 4069
count: 6, val: 9, sum: 30, savg: 5, avg: 5, internal: 5301
count: 7, val: 10, sum: 40, savg: 5, avg: 6, internal: 6475
count: 8, val: 12, sum: 52, savg: 6, avg: 8, internal: 7856
count: 9, val: 13, sum: 65, savg: 7, avg: 9, internal: 9142
count: 10, val: 15, sum: 80, savg: 8, avg: 11, internal: 10606
count: 11, val: 16, sum: 96, savg: 8, avg: 12, internal: 11954
count: 12, val: 18, sum: 114, savg: 9, avg: 13, internal: 13465
count: 13, val: 19, sum: 133, savg: 10, avg: 15, internal: 14848
count: 14, val: 21, sum: 154, savg: 11, avg: 16, internal: 16386
count: 15, val: 22, sum: 176, savg: 11, avg: 18, internal: 17789
count: 16, val: 24, sum: 200, savg: 12, avg: 19, internal: 19341
count: 17, val: 25, sum: 225, savg: 13, avg: 21, internal: 20755
count: 18, val: 27, sum: 252, savg: 14, avg: 22, internal: 22316
count: 19, val: 28, sum: 280, savg: 14, avg: 24, internal: 23737
count: 20, val: 30, sum: 310, savg: 15, avg: 25, internal: 25302
Especially towards the end you can see how a moving average gives preference to the newer values.
Quoted 3 lines
Quoted 1 line
Is this the right place to add it? Who to CC:?
Try Andrew. (added)
I attach a new version of the test program. If you can generally agree that this can be included in the kernel, I'll work on an improved version of my patch.
Thank you for your feedback!
Bruno
#if 0
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. #endif
#ifndef _LINUX_AVERAGE_H
#define _LINUX_AVERAGE_H
#define AVG_FACTOR 1000
struct avg_val {
int value;
int internal;
};#define DIV_ROUND_CLOSEST(x, divisor)( \
{ \
typeof(divisor) __divisor = divisor; \
(((x) + ((__divisor) / 2)) / (__divisor)); \
} \)
/**
* moving_average - Exponentially weighted moving average
* @avg: average structure
* @val: current value
* @samples: number of samples. This defines how fast the influence of older
* values decreases. Use the same number every time you call this
* function for a single avg_val!.
*
* This implementation make use of a struct avg_val to prevent rounding
* errors.
*/
static inline struct avg_valmoving_average(const struct avg_val avg, const int val, const int samples)
{
struct avg_val ret;
ret.internal = avg.internal ?
(((avg.internal * (samples - 1)) +
(val * AVG_FACTOR)) / samples) :
(val * AVG_FACTOR);
ret.value = DIV_ROUND_CLOSEST(ret.internal, AVG_FACTOR);
return ret;
}#endif /* _LINUX_AVERAGE_H */
#include <stdio.h>
int main(int argc, char *argv[])
{
struct avg_val avg = {};
int count;
int val;
int sum = 0;
for (count = 1; count <= 20; count++) {
val = count + count/2;
sum += val;
avg = moving_average(avg, val, 4);
printf("count: %d, val: %d, sum: %d, savg: %d, avg: %d, internal: %d\n",
count, val, sum, sum/count, avg.value, avg.internal);
}
return 0;
}Quoted 14 lines · Bruno Randolf
Hello Randy!
Thank you for taking the time to look at this!
Quoted 9 lines · On Wed October 13 2010 09:33:52 Randy Dunlap wrote:
Quoted 8 lines · On Wed, 06 Oct 2010 18:32:25 +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.
Quoted 7 lines
Quoted 4 lines
Quoted 1 line
Signed-off-by Bruno Randolf <[email protected]>I guess I don't understand "exponentially weighted" or why that would be desirable. Please try to explain (briefly).
It just means, that more recent values are given a higher priority. The influence of older values decreases exponentially.
Got it, thanks.
Quoted 28 lines
This is desirable if we want to have an average, but we are more interested in the recent development. One example where that makes sense is the signal strength of a station in a wireless LAN. As the signal strength can vary significantly for every packet, just looking at one packet is misleading. We are not so much interested in a long term average, as a station might move
- we are more interested in the average of the last X (say 8) packets, giving most priority to the last value.http://en.wikipedia.org/wiki/Exponentially_weighted_moving_average#Exponential_moving_average
This is one example, but I found several places in the kernel code where something like this is used, usually open coded. That's why I tought a general function for this can make sense.
Quoted 5 lines
I'm attaching a test program that I did. I don't especially like the results of it. Maybe it's due to the exponential weighting. (?)
The test program tells me that the sum of 3 samples is 8 & average = 2:
i.e., not rounded up.Oh, I see. I guess I should use
DIV_ROUND_CLOSEST. I attach a new version of the test program.Quoted 4 lines
And that the sum of 6 samples is 30 & average = 4. (!!) And that the sum of 10 samples is 80 & average = 5. (!!)
Am I just not understanding the function or am I misusing it?
Quoted 8 lines
You should keep 'samples' constant every time you call the function. It is the factor which defines how fast the influence of older values decreases. Higher values will take more older samples into account. E.g. use it like this:
moving_average(avg, val, 4);I should have documented that better, I guess... And maybe rename it to 'factor'.
OK, now I see how it's used.
Quoted 29 lines
Also a moving average makes more sense when you use it more often, depending on how high 'samples' is. E.g. here is the output of the test program with 'sampes' of 4 and 20 iterations. I also print 'savg' (simple average) which is sum/count:
count: 1, val: 1, sum: 1, savg: 1, avg: 1, internal: 1000
count: 2, val: 3, sum: 4, savg: 2, avg: 2, internal: 1500
count: 3, val: 4, sum: 8, savg: 2, avg: 2, internal: 2125
count: 4, val: 6, sum: 14, savg: 3, avg: 3, internal: 3093
count: 5, val: 7, sum: 21, savg: 4, avg: 4, internal: 4069
count: 6, val: 9, sum: 30, savg: 5, avg: 5, internal: 5301
count: 7, val: 10, sum: 40, savg: 5, avg: 6, internal: 6475
count: 8, val: 12, sum: 52, savg: 6, avg: 8, internal: 7856
count: 9, val: 13, sum: 65, savg: 7, avg: 9, internal: 9142
count: 10, val: 15, sum: 80, savg: 8, avg: 11, internal: 10606
count: 11, val: 16, sum: 96, savg: 8, avg: 12, internal: 11954
count: 12, val: 18, sum: 114, savg: 9, avg: 13, internal: 13465
count: 13, val: 19, sum: 133, savg: 10, avg: 15, internal: 14848
count: 14, val: 21, sum: 154, savg: 11, avg: 16, internal: 16386
count: 15, val: 22, sum: 176, savg: 11, avg: 18, internal: 17789
count: 16, val: 24, sum: 200, savg: 12, avg: 19, internal: 19341
count: 17, val: 25, sum: 225, savg: 13, avg: 21, internal: 20755
count: 18, val: 27, sum: 252, savg: 14, avg: 22, internal: 22316
count: 19, val: 28, sum: 280, savg: 14, avg: 24, internal: 23737
count: 20, val: 30, sum: 310, savg: 15, avg: 25, internal: 25302Especially towards the end you can see how a moving average gives preference to the newer values.
Quoted 7 lines
Quoted 3 lines
Quoted 1 line
Is this the right place to add it? Who to CC:?
Try Andrew. (added)
I attach a new version of the test program. If you can generally agree that this can be included in the kernel, I'll work on an improved version of my patch.
Seems OK to me as long as there are multiple users of it.
Quoted 1 line
Thank you for your feedback!
Signature · 2 lines
~Randy *** Remember to use Documentation/SubmitChecklist when testing your code ***
Quoted 11 lines · Randy Dunlap
Quoted 6 lines · On Wed, 06 Oct 2010 18:32:25 +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.I guess I don't understand "exponentially weighted" or why that would be desirable. Please try to explain (briefly).
I wrote up a fairly non-brief explanation of exponentially weighted moving averages a few years ago:
http://www.stanford.edu/class/cs140/projects/pintos/pintos_7.html#SEC134
Signature · 2 lines
Ben Pfaff http://benpfaff.org
Quoted 11 lines · Ben Pfaff
Quoted 9 lines · Randy Dunlap
Quoted 6 lines · On Wed, 06 Oct 2010 18:32:25 +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.
Quoted 6 lines
Quoted 2 lines
I guess I don't understand "exponentially weighted" or why that would be desirable. Please try to explain (briefly).
I wrote up a fairly non-brief explanation of exponentially weighted moving averages a few years ago:
http://www.stanford.edu/class/cs140/projects/pintos/pintos_7.html#SEC134
Thanks, nice writeup.
Signature · 2 lines
~Randy *** Remember to use Documentation/SubmitChecklist when testing your code ***
Quoted 23 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]>--
Is this the right place to add it? Who to CC:?
---
include/linux/average.h | 32 ++++++++++++++++++++++++++++++++1 files changed, 32 insertions(+), 0 deletions(-)create mode 100644
include/linux/average.hinclude/linux/average.h new file +0
-0
include/linux/average.h line 4
Quoted 4 lines
include/linux/average.h new file +4
-0@@ -0,0 +1,32 @@ +#ifndef _LINUX_AVERAGE_H +#define _LINUX_AVERAGE_H + +#define AVG_FACTOR 1000
If this is going to be general use, wouldn't it be a good feature to make AVG_FACTOR adjustable?
include/linux/average.h line 9
Quoted 6 lines
include/linux/average.h new file +5
-0+ +struct avg_val { + int value; + int internal; +};
This has a scaled up copy of the moving average, which reduces the available range for the average to MAX_INT/(AVG_FACTOR*num_samples) instead of +/- MAX_INT, is that acceptable? Even if it is, shouldn't it be documented? For example, with num_samples = 10, it will roll over to a negative value if the average exceeds 214,748. This seems like a potentially surprising outcome.
Quoted 8 lines
include/linux/average.h new file +7
-0+ +/** +* moving_average - Exponentially weighted moving average +* @avg: average structure +* @val: current value +* @samples: number of samples +*
include/linux/average.h line 26
Quoted 10 lines
include/linux/average.h new file +10
-0+* This implementation make use of a struct avg_val to prevent rounding +* errors. +*/ +static inline struct avg_val +moving_average (const struct avg_val avg,const int val,const int samples) +{ + struct avg_val ret; + ret.internal = avg.internal ? + (((avg.internal * (samples - 1)) + + (val * AVG_FACTOR)) / samples) :
I'm not sure what the kernel standard is on this, but is it ok to have this potential div/0 in a general purpose function?
Thanks,
Kevin Granade
Quoted 14 lines
include/linux/average.h new file +6
-1+ (val * AVG_FACTOR); + ret.value = ret.internal / AVG_FACTOR; + return ret; +} + +#endif /* _LINUX_AVERAGE_H */ --To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Quoted 18 lines · On Wed October 13 2010 23:01:16 kevin granade wrote:
Quoted 17 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]>--
Is this the right place to add it? Who to CC:?--- include/linux/average.h | 32 ++++++++++++++++++++++++++++++++ 1 files changed, 32 insertions(+), 0 deletions(-) create mode 100644 include/linux/average.h
Quoted 13 lines
include/linux/average.h line 4
Quoted 10 lines
include/linux/average.h new file +4
-0@@ -0,0 +1,32 @@ +#ifndef _LINUX_AVERAGE_H +#define _LINUX_AVERAGE_H + +#define AVG_FACTOR 1000If this is going to be general use, wouldn't it be a good feature to make
AVG_FACTORadjustable?
Yes, could be, but how? Another argument to the function call? Actually AVG_FACTOR and 'samples' should stay constant for each struct, so we could also store them in the struct, but that would require an inititalization of the struct before we can use it.
Quoted 4 lines
Quoted 4 lines
include/linux/average.h new file +4
-0+ +struct avg_val { +int value; +int internal;
Quoted 8 lines
include/linux/average.h line 9
Quoted 1 line
include/linux/average.h new file +1
-0+};This has a scaled up copy of the moving average, which reduces the available range for the average to MAX_INT/(AVG_FACTOR*num_samples) instead of +/-
MAX_INT, is that acceptable? Even if it is, shouldn't it be documented? For example, withnum_samples= 10, it will roll over to a negative value if the average exceeds 214,748. This seems like a potentially surprising outcome.
Yes. I'll document this in the next version of the patch. Or should I use 64bit for the internal representation?
Quoted 16 lines
Quoted 15 lines
include/linux/average.h new file +11
-0+/** +* moving_average - Exponentially weighted moving average +* @avg: average structure +* @val: current value +* @samples: number of samples +* +* This implementation make use of a struct avg_val to prevent rounding +* errors. +*/ +static inline struct avg_val +moving_average(const struct avg_val avg, const int val, const intsamples) +{
include/linux/average.h new file +3
-0+struct avg_val ret; + ret.internal = avg.internal ? + (((avg.internal * (samples - 1)) +
Quoted 3 lines
Quoted 1 line
+ (val *
AVG_FACTOR)) / samples) :I'm not sure what the kernel standard is on this, but is it ok to have this potential div/0 in a general purpose function?
Samples should never be 0. But I can add a WARN_ON...
bruno
Quoted 33 lines · Bruno Randolf
Quoted 18 lines · On Wed October 13 2010 23:01:16 kevin granade wrote:
Quoted 17 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]>--
Is this the right place to add it? Who to CC:?
---
include/linux/average.h | 32 ++++++++++++++++++++++++++++++++1 files changed, 32 insertions(+), 0 deletions(-)create mode 100644
include/linux/average.hQuoted 13 lines
include/linux/average.h line 4
Quoted 10 lines
include/linux/average.h new file +4
-0@@ -0,0 +1,32 @@ +#ifndef _LINUX_AVERAGE_H +#define _LINUX_AVERAGE_H + +#define AVG_FACTOR 1000If this is going to be general use, wouldn't it be a good feature to make
AVG_FACTORadjustable?
Quoted 4 lines
Yes, could be, but how? Another argument to the function call? Actually
AVG_FACTORand 'samples' should stay constant for each struct, so we could also store them in the struct, but that would require an inititalization of the struct before we can use it.
That's true, I can't think of a way of adding this without significantly dirtying the interface. And to be honest, it isn't a, "I might be using this, so it'd be nice to have", but rather a general observation. I guess if someone needs a different decay rate at some point then they can worry about it.
Quoted 14 lines
Quoted 13 lines
include/linux/average.h line 9
Quoted 6 lines
include/linux/average.h new file +5
-0+ +struct avg_val { + int value; + int internal; +};This has a scaled up copy of the moving average, which reduces the available range for the average to MAX_INT/(AVG_FACTOR*num_samples) instead of +/-
MAX_INT, is that acceptable? Even if it is, shouldn't it be documented? For example, withnum_samples= 10, it will roll over to a negative value if the average exceeds 214,748. This seems like a potentially surprising outcome.
Quoted 2 lines
Yes. I'll document this in the next version of the patch. Or should I use 64bit for the internal representation?
If you don't expect the size or speed impact to be significant, it seems like just throwing a bigger number at the problem might be the better option. That will move the rollover to MAX_INT/AVG_FACTOR, unless you also make AVG_FACTOR 64bit, which will promote all of the multiplications to 64bit and provide full MAX_INT range for input and output.
Quoted 17 lines
Quoted 17 lines
Quoted 16 lines
include/linux/average.h new file +11
-0+/** +* moving_average - Exponentially weighted moving average +* @avg: average structure +* @val: current value +* @samples: number of samples +* +* This implementation make use of a struct avg_val to prevent rounding +* errors. +*/ +static inline struct avg_val +moving_average(const struct avg_val avg, const int val, const intsamples) +{
+ structavg_valret;
+ ret.internal = avg.internal ?
+ (((avg.internal * (samples - 1)) +
Quoted 8 lines
Quoted 3 lines
Quoted 1 line
+ (val *
AVG_FACTOR)) / samples) :I'm not sure what the kernel standard is on this, but is it ok to have this potential div/0 in a general purpose function?
Samples should never be 0. But I can add a
WARN_ON...bruno
I couldn't find anything that clearly indicated what the expected precaution is in this case. It probably isn't an issue now that I understand that samples is intended to remain constant. I initially thought samples would scale from 1 - n as you were initially "loading" samples into the structure, but now I understand that samples remains at n throughout the process.
Kevin Granade
Quoted 10 lines · On Fri October 15 2010 22:55:23 kevin granade wrote:
Quoted 9 lines
Quoted 6 lines
This has a scaled up copy of the moving average, which reduces the available range for the average to MAX_INT/(AVG_FACTOR*num_samples) instead of +/-
MAX_INT, is that acceptable? Even if it is, shouldn't it be documented? For example, withnum_samples= 10, it will roll over to a negative value if the average exceeds 214,748. This seems like a potentially surprising outcome.Yes. I'll document this in the next version of the patch. Or should I use 64bit for the internal representation?
Quoted 6 lines
If you don't expect the size or speed impact to be significant, it seems like just throwing a bigger number at the problem might be the better option. That will move the rollover to MAX_INT/AVG_FACTOR, unless you also make
AVG_FACTOR64bit, which will promote all of the multiplications to 64bit and provide fullMAX_INTrange for input and output.
Honestly, I don't know about the speed impact of using 64 bit vs. 32 bit. I do know however, that the averaging function needs to be called quite often, where I want to use it, so performance could be an issue. And in my case the values are low enough so rollover is not a problem - but obviously I want to make this generally useful.
Quoted 6 lines
I couldn't find anything that clearly indicated what the expected precaution is in this case. It probably isn't an issue now that I understand that samples is intended to remain constant. I initially thought samples would scale from 1 - n as you were initially "loading" samples into the structure, but now I understand that samples remains at n throughout the process.
I will work on the description.
Thanks,
Bruno