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

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

[Andrew Morton]

On Tue, 19 Oct 2010 17:36:35 +0900
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>
> 

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.

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

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

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

[Andrew Morton]

On Tue, 19 Oct 2010 15:37:56 -0700
Andrew Morton <akpm@linux-foundation.org> wrote:

> On Tue, 19 Oct 2010 17:36:35 +0900
> 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>
> > 
> 
> 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..

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

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

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

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 majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

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

[Bruno Randolf]

On Wed October 20 2010 07:54:06 Andrew Morton wrote:
> I looked at the code..

Thank you for your review!

> > > +#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().

OK. I thought I'd get away without it ;) but you convinced me it's better to 
have a moving_average_init().

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

> > > +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);
> > > +}
> 
> 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.

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?

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

Yes. So I'll make a moving_average_init(scaling_factor, weight).

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

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.

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

Ok. No problem.
 
> 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.

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

Will do that and resend an improved version shortly.

Thanks,
Bruno

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>