Message-Id: <201010131110.21341.br1@einfach.org>
Date:	Wed, 13 Oct 2010 11:10:21 +0900
From:	Bruno Randolf <br1@...fach.org>
To:	Randy Dunlap <randy.dunlap@...cle.com>
Cc:	linux-kernel@...r.kernel.org, akpm <akpm@...ux-foundation.org>
Subject: Re: [PATCH] Add generic exponentially weighted moving average function

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

View attachment "moving-avg.c" of type "text/x-csrc" (1762 bytes)

Powered by blists - more mailing lists