2013-04-17 11:47:38

by Karl Beldan

[permalink] [raw]
Subject: [PATCH] mac80211: optimize minstrel_ewma

From: Karl Beldan <[email protected]>

Use powers of two in ewma of minstrel.
This changes :
- EWMA_DIV from 100 to 2^7
- EWMA_LEVEL from 75 (/EWMA_DIV=100) to 2^6 + 2^5 (/EWMA_DIV=128)

Note that this changes EWMA_DIV - EWMA_LEVEL from 25 to 2^5 and keeps
EWMA_LEVEL / EWMA_DIV == 0.75.

Signed-off-by: Karl Beldan <[email protected]>
---
Here's a quick benchmark with gcc -O2 -std=c99: {

#ifndef ORIG
#define EWMA_LEVEL 75
#define EWMA_DIV 100
#else
#define EWMA_LEVEL 96
#define EWMA_DIV 128
#endif
static inline int minstrel_ewma(int old, int new, int weight)
{
return (new * (EWMA_DIV - weight) + old * weight) / EWMA_DIV;
}
int main()
{
volatile int a, b, c;
for (int i = 0; i < 1 << 30; i++)
c = minstrel_ewma(a, b, EWMA_LEVEL);
return 0;
}

On an i5:
before: real 0m2.426s
after: real 0m1.495s
1.495 / 2.426 = 0.6

On a mv-feroceon:
before: real 0m20.231s
after: real 0m18.193s
18.193 / 20.231 = 0.9
}

net/mac80211/rc80211_minstrel.h | 5 +++--
1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/net/mac80211/rc80211_minstrel.h b/net/mac80211/rc80211_minstrel.h
index 8e5a222..f4301f4 100644
--- a/net/mac80211/rc80211_minstrel.h
+++ b/net/mac80211/rc80211_minstrel.h
@@ -9,7 +9,8 @@
#ifndef __RC_MINSTREL_H
#define __RC_MINSTREL_H

-#define EWMA_LEVEL 75 /* ewma weighting factor [%] */
+#define EWMA_LEVEL 96 /* ewma weighting factor [/EWMA_DIV] */
+#define EWMA_DIV 128
#define SAMPLE_COLUMNS 10 /* number of columns in sample table */


@@ -27,7 +28,7 @@
static inline int
minstrel_ewma(int old, int new, int weight)
{
- return (new * (100 - weight) + old * weight) / 100;
+ return (new * (EWMA_DIV - weight) + old * weight) / EWMA_DIV;
}


--
1.8.2



2013-04-17 14:31:56

by Felix Fietkau

[permalink] [raw]
Subject: Re: [PATCH] mac80211: optimize minstrel_ewma

On 2013-04-17 1:43 PM, Karl Beldan wrote:
> From: Karl Beldan <[email protected]>
>
> Use powers of two in ewma of minstrel.
> This changes :
> - EWMA_DIV from 100 to 2^7
> - EWMA_LEVEL from 75 (/EWMA_DIV=100) to 2^6 + 2^5 (/EWMA_DIV=128)
>
> Note that this changes EWMA_DIV - EWMA_LEVEL from 25 to 2^5 and keeps
> EWMA_LEVEL / EWMA_DIV == 0.75.
>
> Signed-off-by: Karl Beldan <[email protected]>
Acked-by: Felix Fietkau <[email protected]>