[PATCH] Add generic exponentially weighted moving average function

[PATCH] Add generic exponentially weighted moving average function

[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 <br1@einfach.org>

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

diff --git a/include/linux/average.h b/include/linux/average.h
new file mode 100644
index 0000000..2a00d3d
--- /dev/null
+++ b/include/linux/average.h
@@ -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 */

Re: [PATCH] Add generic exponentially weighted moving average function

[Randy Dunlap]

[-- Attachment #1: Type: text/plain, Size: 2872 bytes --]

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 <br1@einfach.org>

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:

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


> --
> Is this the right place to add it? Who to CC:?

Try Andrew. (added)

> 
> ---
>  include/linux/average.h |   32 ++++++++++++++++++++++++++++++++
>  1 files changed, 32 insertions(+), 0 deletions(-)
>  create mode 100644 include/linux/average.h
> 
> diff --git a/include/linux/average.h b/include/linux/average.h
> new file mode 100644
> index 0000000..2a00d3d
> --- /dev/null
> +++ b/include/linux/average.h
> @@ -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 */
> 
> --


---
~Randy
*** Remember to use Documentation/SubmitChecklist when testing your code ***

[-- Attachment #2: moving-avg.c --]
[-- Type: text/plain, Size: 1424 bytes --]

#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_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 */


#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;
}

Re: [PATCH] Add generic exponentially weighted moving average function

[Bruno Randolf]

[-- Attachment #1: Type: Text/Plain, Size: 4361 bytes --]

Hello Randy!

Thank you for taking the time to look at this!

On Wed October 13 2010 09:33:52 Randy Dunlap wrote:
> 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 <br1@einfach.org>
> 
> 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.

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

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

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

[-- Attachment #2: moving-avg.c --]
[-- Type: text/x-csrc, Size: 1761 bytes --]

#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_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 = 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;
}

Re: [PATCH] Add generic exponentially weighted moving average function

[kevin granade]

On Wed, Oct 6, 2010 at 4:32 AM, Bruno Randolf <br1@einfach.org> 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 <br1@einfach.org>
>
> --
> 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
>
> diff --git a/include/linux/average.h b/include/linux/average.h
> new file mode 100644
> index 0000000..2a00d3d
> --- /dev/null
> +++ b/include/linux/average.h
> @@ -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?

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

>
> +
> +/**
> + * 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) :

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

>
> +               (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 majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH] Add generic exponentially weighted moving average function

[Randy Dunlap]

On 10/12/10 19:10, Bruno Randolf wrote:
> Hello Randy!
> 
> Thank you for taking the time to look at this!
> 
> On Wed October 13 2010 09:33:52 Randy Dunlap wrote:
>> 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 <br1@einfach.org>
>>
>> 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.

> 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.
> 
>> 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.
> 
>> 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'.

OK, now I see how it's used.

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

> Thank you for your feedback!


-- 
~Randy
*** Remember to use Documentation/SubmitChecklist when testing your code ***

Re: [PATCH] Add generic exponentially weighted moving average function

[Bruno Randolf]

On Wed October 13 2010 23:01:16 kevin granade wrote:
> On Wed, Oct 6, 2010 at 4:32 AM, Bruno Randolf <br1@einfach.org> 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 <br1@einfach.org>
> > 
> > --
> > 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
> > 
> > diff --git a/include/linux/average.h b/include/linux/average.h
> > new file mode 100644
> > index 0000000..2a00d3d
> > --- /dev/null
> > +++ b/include/linux/average.h
> > @@ -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?

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.

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

Yes. I'll document this in the next version of the patch. Or should I use 
64bit for the internal representation?

> > +/**
> > + * 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) :
> 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

Re: [PATCH] Add generic exponentially weighted moving average function

[Ben Pfaff]

Randy Dunlap <randy.dunlap@oracle.com> writes:

> 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
-- 
Ben Pfaff 
http://benpfaff.org

Re: [PATCH] Add generic exponentially weighted moving average function

[kevin granade]

On Wed, Oct 13, 2010 at 8:19 PM, Bruno Randolf <br1@einfach.org> wrote:
> On Wed October 13 2010 23:01:16 kevin granade wrote:
>> On Wed, Oct 6, 2010 at 4:32 AM, Bruno Randolf <br1@einfach.org> 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 <br1@einfach.org>
>> >
>> > --
>> > 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
>> >
>> > diff --git a/include/linux/average.h b/include/linux/average.h
>> > new file mode 100644
>> > index 0000000..2a00d3d
>> > --- /dev/null
>> > +++ b/include/linux/average.h
>> > @@ -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?
>
> 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.

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.

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

>
>> > +/**
>> > + * 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) :
>> 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

Re: [PATCH] Add generic exponentially weighted moving average function

[Randy Dunlap]

On 10/14/10 20:40, Ben Pfaff wrote:
> Randy Dunlap <randy.dunlap@oracle.com> writes:
> 
>> 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

Thanks, nice writeup.

-- 
~Randy
*** Remember to use Documentation/SubmitChecklist when testing your code ***

Re: [PATCH] Add generic exponentially weighted moving average function

[Bruno Randolf]

On Fri October 15 2010 22:55:23 kevin granade wrote:
> >> 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.
> > 
> > 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.

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.

> 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