Linux-Wireless Archive on lore.kernel.org
 help / color / Atom feed
* [PATCH 1/2] mac80211: minstrel: remove divisions in tx status path
@ 2019-09-29 15:46 Felix Fietkau
  2019-09-29 15:46 ` [PATCH 2/2] mac80211: minstrel_ht: replace rate stats ewma with a better moving average Felix Fietkau
  0 siblings, 1 reply; 10+ messages in thread
From: Felix Fietkau @ 2019-09-29 15:46 UTC (permalink / raw)
  To: linux-wireless; +Cc: johannes

Use a slightly different threshold for downgrading spatial streams to
make it easier to calculate without divisions.
Slightly reduces CPU overhead.

Signed-off-by: Felix Fietkau <nbd@nbd.name>
---
 net/mac80211/rc80211_minstrel.c    |  3 +--
 net/mac80211/rc80211_minstrel_ht.c | 10 ++++------
 2 files changed, 5 insertions(+), 8 deletions(-)

diff --git a/net/mac80211/rc80211_minstrel.c b/net/mac80211/rc80211_minstrel.c
index ee86c3333999..f73017e08111 100644
--- a/net/mac80211/rc80211_minstrel.c
+++ b/net/mac80211/rc80211_minstrel.c
@@ -289,8 +289,7 @@ minstrel_tx_status(void *priv, struct ieee80211_supported_band *sband,
 	if (mi->sample_deferred > 0)
 		mi->sample_deferred--;
 
-	if (time_after(jiffies, mi->last_stats_update +
-				(mp->update_interval * HZ) / 1000))
+	if (time_after(jiffies, mi->last_stats_update + mp->update_interval))
 		minstrel_update_stats(mp, mi);
 }
 
diff --git a/net/mac80211/rc80211_minstrel_ht.c b/net/mac80211/rc80211_minstrel_ht.c
index 0ef2633349b5..21c74b200269 100644
--- a/net/mac80211/rc80211_minstrel_ht.c
+++ b/net/mac80211/rc80211_minstrel_ht.c
@@ -970,23 +970,21 @@ minstrel_ht_tx_status(void *priv, struct ieee80211_supported_band *sband,
 		 */
 		rate = minstrel_get_ratestats(mi, mi->max_tp_rate[0]);
 		if (rate->attempts > 30 &&
-		    MINSTREL_FRAC(rate->success, rate->attempts) <
-		    MINSTREL_FRAC(20, 100)) {
+		    rate->success < rate->attempts / 4) {
 			minstrel_downgrade_rate(mi, &mi->max_tp_rate[0], true);
 			update = true;
 		}
 
 		rate2 = minstrel_get_ratestats(mi, mi->max_tp_rate[1]);
 		if (rate2->attempts > 30 &&
-		    MINSTREL_FRAC(rate2->success, rate2->attempts) <
-		    MINSTREL_FRAC(20, 100)) {
+		    rate2->success < rate2->attempts / 4) {
 			minstrel_downgrade_rate(mi, &mi->max_tp_rate[1], false);
 			update = true;
 		}
 	}
 
 	if (time_after(jiffies, mi->last_stats_update +
-				(mp->update_interval / 2 * HZ) / 1000)) {
+				mp->update_interval / 2)) {
 		update = true;
 		minstrel_ht_update_stats(mp, mi, true);
 	}
@@ -1666,7 +1664,7 @@ minstrel_ht_alloc(struct ieee80211_hw *hw, struct dentry *debugfsdir)
 		mp->has_mrr = true;
 
 	mp->hw = hw;
-	mp->update_interval = 100;
+	mp->update_interval = HZ / 10;
 
 #ifdef CONFIG_MAC80211_DEBUGFS
 	mp->fixed_rate_idx = (u32) -1;
-- 
2.17.0


^ permalink raw reply	[flat|nested] 10+ messages in thread

* [PATCH 2/2] mac80211: minstrel_ht: replace rate stats ewma with a better moving average
  2019-09-29 15:46 [PATCH 1/2] mac80211: minstrel: remove divisions in tx status path Felix Fietkau
@ 2019-09-29 15:46 ` Felix Fietkau
  2019-09-29 18:42   ` Toke Høiland-Jørgensen
                     ` (2 more replies)
  0 siblings, 3 replies; 10+ messages in thread
From: Felix Fietkau @ 2019-09-29 15:46 UTC (permalink / raw)
  To: linux-wireless; +Cc: johannes

Rate success probability usually fluctuates a lot under normal conditions.
With a simple EWMA, noise and fluctuation can be reduced by increasing the
window length, but that comes at the cost of introducing lag on sudden
changes.

This change replaces the EWMA implementation with a moving average that's
designed to significantly reduce lag while keeping a bigger window size
by being better at filtering out noise.

It is only slightly more expensive than the simple EWMA and still avoids
divisions in its calculation.

The algorithm is adapted from an implementation intended for a completely
different field (stock market trading), where the tradeoff of lag vs
noise filtering is equally important. It is based on the "smoothing filter"
from http://www.stockspotter.com/files/PredictiveIndicators.pdf.

I have adapted it to fixed-point math with some constants so that it uses
only addition, bit shifts and multiplication

To better make use of the filtering and bigger window size, the update
interval time is cut in half.

For testing, the algorithm can be reverted to the older one via debugfs

Signed-off-by: Felix Fietkau <nbd@nbd.name>
---
 net/mac80211/rc80211_minstrel.c    | 13 ++++---
 net/mac80211/rc80211_minstrel.h    | 57 +++++++++++++++++++++++++++++-
 net/mac80211/rc80211_minstrel_ht.c | 15 ++++++--
 3 files changed, 77 insertions(+), 8 deletions(-)

diff --git a/net/mac80211/rc80211_minstrel.c b/net/mac80211/rc80211_minstrel.c
index f73017e08111..d9b7bc7fdb33 100644
--- a/net/mac80211/rc80211_minstrel.c
+++ b/net/mac80211/rc80211_minstrel.c
@@ -157,14 +157,18 @@ minstrel_update_rates(struct minstrel_priv *mp, struct minstrel_sta_info *mi)
 * Recalculate statistics and counters of a given rate
 */
 void
-minstrel_calc_rate_stats(struct minstrel_rate_stats *mrs)
+minstrel_calc_rate_stats(struct minstrel_priv *mp,
+			 struct minstrel_rate_stats *mrs)
 {
 	unsigned int cur_prob;
 
 	if (unlikely(mrs->attempts > 0)) {
 		mrs->sample_skipped = 0;
 		cur_prob = MINSTREL_FRAC(mrs->success, mrs->attempts);
-		if (unlikely(!mrs->att_hist)) {
+		if (mp->new_avg) {
+			mrs->prob_ewma = minstrel_filter_avg_add(&mrs->avg,
+								 cur_prob);
+		} else if (unlikely(!mrs->att_hist)) {
 			mrs->prob_ewma = cur_prob;
 		} else {
 			/*update exponential weighted moving avarage */
@@ -200,7 +204,7 @@ minstrel_update_stats(struct minstrel_priv *mp, struct minstrel_sta_info *mi)
 		struct minstrel_rate_stats *tmp_mrs = &mi->r[tmp_prob_rate].stats;
 
 		/* Update statistics of success probability per rate */
-		minstrel_calc_rate_stats(mrs);
+		minstrel_calc_rate_stats(mp, mrs);
 
 		/* Sample less often below the 10% chance of success.
 		 * Sample less often above the 95% chance of success. */
@@ -289,7 +293,8 @@ minstrel_tx_status(void *priv, struct ieee80211_supported_band *sband,
 	if (mi->sample_deferred > 0)
 		mi->sample_deferred--;
 
-	if (time_after(jiffies, mi->last_stats_update + mp->update_interval))
+	if (time_after(jiffies, mi->last_stats_update +
+				mp->update_interval / (mp->new_avg ? 2 : 1)))
 		minstrel_update_stats(mp, mi);
 }
 
diff --git a/net/mac80211/rc80211_minstrel.h b/net/mac80211/rc80211_minstrel.h
index 51d8b2c846e7..360134848520 100644
--- a/net/mac80211/rc80211_minstrel.h
+++ b/net/mac80211/rc80211_minstrel.h
@@ -18,6 +18,19 @@
 /* number of highest throughput rates to consider*/
 #define MAX_THR_RATES 4
 
+/*
+ * Coefficients for moving average with noise filter (period=16),
+ * scaled by 10 bits
+ *
+ * a1 = exp(-pi * sqrt(2) / period)
+ * coeff2 = 2 * a1 * cos(sqrt(2) * 2 * pi / period)
+ * coeff3 = -sqr(a1)
+ * coeff1 = 1 - coeff2 - coeff3
+ */
+#define MINSTREL_AVG_COEFF1		0x00000495
+#define MINSTREL_AVG_COEFF2		0x00001499
+#define MINSTREL_AVG_COEFF3		-0x0000092e
+
 /*
  * Perform EWMA (Exponentially Weighted Moving Average) calculation
  */
@@ -32,6 +45,44 @@ minstrel_ewma(int old, int new, int weight)
 	return old + incr;
 }
 
+struct minstrel_avg_ctx {
+	s32 in_1;
+	s32 out_1;
+	s32 out_2;
+};
+
+static inline int minstrel_filter_avg_add(struct minstrel_avg_ctx *ctx, s32 in)
+{
+	s32 in_1 = ctx->in_1;
+	s32 out_1 = ctx->out_1;
+	s32 out_2 = ctx->out_2;
+	s32 val;
+
+	if (!in)
+		in += 1;
+
+	ctx->in_1 = in;
+	if (!in_1) {
+		val = out_1 = in;
+		goto out;
+	}
+
+	val = (MINSTREL_AVG_COEFF1 * (in + in_1) / 2) >> MINSTREL_SCALE;
+	val += (MINSTREL_AVG_COEFF2 * out_1) >> MINSTREL_SCALE;
+	val += (MINSTREL_AVG_COEFF3 * out_2) >> MINSTREL_SCALE;
+
+	if (val > 1 << MINSTREL_SCALE)
+		val = 1 << MINSTREL_SCALE;
+	if (val < 0)
+		val = 1;
+
+out:
+	ctx->out_2 = out_1;
+	ctx->out_1 = val;
+
+	return val;
+}
+
 struct minstrel_rate_stats {
 	/* current / last sampling period attempts/success counters */
 	u16 attempts, last_attempts;
@@ -40,6 +91,8 @@ struct minstrel_rate_stats {
 	/* total attempts/success counters */
 	u32 att_hist, succ_hist;
 
+	struct minstrel_avg_ctx avg;
+
 	/* prob_ewma - exponential weighted moving average of prob */
 	u16 prob_ewma;
 
@@ -95,6 +148,7 @@ struct minstrel_sta_info {
 struct minstrel_priv {
 	struct ieee80211_hw *hw;
 	bool has_mrr;
+	bool new_avg;
 	u32 sample_switch;
 	unsigned int cw_min;
 	unsigned int cw_max;
@@ -126,7 +180,8 @@ extern const struct rate_control_ops mac80211_minstrel;
 void minstrel_add_sta_debugfs(void *priv, void *priv_sta, struct dentry *dir);
 
 /* Recalculate success probabilities and counters for a given rate using EWMA */
-void minstrel_calc_rate_stats(struct minstrel_rate_stats *mrs);
+void minstrel_calc_rate_stats(struct minstrel_priv *mp,
+			      struct minstrel_rate_stats *mrs);
 int minstrel_get_tp_avg(struct minstrel_rate *mr, int prob_ewma);
 
 /* debugfs */
diff --git a/net/mac80211/rc80211_minstrel_ht.c b/net/mac80211/rc80211_minstrel_ht.c
index 21c74b200269..96c81392e617 100644
--- a/net/mac80211/rc80211_minstrel_ht.c
+++ b/net/mac80211/rc80211_minstrel_ht.c
@@ -737,7 +737,7 @@ minstrel_ht_update_stats(struct minstrel_priv *mp, struct minstrel_ht_sta *mi,
 
 			mrs = &mg->rates[i];
 			mrs->retry_updated = false;
-			minstrel_calc_rate_stats(mrs);
+			minstrel_calc_rate_stats(mp, mrs);
 			cur_prob = mrs->prob_ewma;
 
 			if (minstrel_ht_get_tp_avg(mi, group, i, cur_prob) == 0)
@@ -773,6 +773,8 @@ minstrel_ht_update_stats(struct minstrel_priv *mp, struct minstrel_ht_sta *mi,
 
 	/* try to sample all available rates during each interval */
 	mi->sample_count *= 8;
+	if (mp->new_avg)
+		mi->sample_count /= 2;
 
 	if (sample)
 		minstrel_ht_rate_sample_switch(mp, mi);
@@ -889,6 +891,7 @@ minstrel_ht_tx_status(void *priv, struct ieee80211_supported_band *sband,
 	struct ieee80211_tx_rate *ar = info->status.rates;
 	struct minstrel_rate_stats *rate, *rate2, *rate_sample = NULL;
 	struct minstrel_priv *mp = priv;
+	u32 update_interval = mp->update_interval / 2;
 	bool last, update = false;
 	bool sample_status = false;
 	int i;
@@ -943,6 +946,10 @@ minstrel_ht_tx_status(void *priv, struct ieee80211_supported_band *sband,
 
 	switch (mi->sample_mode) {
 	case MINSTREL_SAMPLE_IDLE:
+		if (mp->new_avg &&
+		    (mp->hw->max_rates > 1 ||
+		     mi->total_packets_cur < SAMPLE_SWITCH_THR))
+			update_interval /= 2;
 		break;
 
 	case MINSTREL_SAMPLE_ACTIVE:
@@ -983,8 +990,7 @@ minstrel_ht_tx_status(void *priv, struct ieee80211_supported_band *sband,
 		}
 	}
 
-	if (time_after(jiffies, mi->last_stats_update +
-				mp->update_interval / 2)) {
+	if (time_after(jiffies, mi->last_stats_update + update_interval)) {
 		update = true;
 		minstrel_ht_update_stats(mp, mi, true);
 	}
@@ -1665,6 +1671,7 @@ minstrel_ht_alloc(struct ieee80211_hw *hw, struct dentry *debugfsdir)
 
 	mp->hw = hw;
 	mp->update_interval = HZ / 10;
+	mp->new_avg = true;
 
 #ifdef CONFIG_MAC80211_DEBUGFS
 	mp->fixed_rate_idx = (u32) -1;
@@ -1672,6 +1679,8 @@ minstrel_ht_alloc(struct ieee80211_hw *hw, struct dentry *debugfsdir)
 			   &mp->fixed_rate_idx);
 	debugfs_create_u32("sample_switch", S_IRUGO | S_IWUSR, debugfsdir,
 			   &mp->sample_switch);
+	debugfs_create_bool("new_avg", S_IRUGO | S_IWUSR, debugfsdir,
+			   &mp->new_avg);
 #endif
 
 	minstrel_ht_init_cck_rates(mp);
-- 
2.17.0


^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: [PATCH 2/2] mac80211: minstrel_ht: replace rate stats ewma with a better moving average
  2019-09-29 15:46 ` [PATCH 2/2] mac80211: minstrel_ht: replace rate stats ewma with a better moving average Felix Fietkau
@ 2019-09-29 18:42   ` Toke Høiland-Jørgensen
  2019-09-29 19:18     ` Felix Fietkau
  2019-10-01 10:17   ` Johannes Berg
  2019-10-08  9:18   ` Koen Vandeputte
  2 siblings, 1 reply; 10+ messages in thread
From: Toke Høiland-Jørgensen @ 2019-09-29 18:42 UTC (permalink / raw)
  To: Felix Fietkau, linux-wireless; +Cc: johannes

Felix Fietkau <nbd@nbd.name> writes:

> Rate success probability usually fluctuates a lot under normal conditions.
> With a simple EWMA, noise and fluctuation can be reduced by increasing the
> window length, but that comes at the cost of introducing lag on sudden
> changes.
>
> This change replaces the EWMA implementation with a moving average that's
> designed to significantly reduce lag while keeping a bigger window size
> by being better at filtering out noise.
>
> It is only slightly more expensive than the simple EWMA and still avoids
> divisions in its calculation.
>
> The algorithm is adapted from an implementation intended for a completely
> different field (stock market trading), where the tradeoff of lag vs
> noise filtering is equally important. It is based on the "smoothing filter"
> from http://www.stockspotter.com/files/PredictiveIndicators.pdf.
>
> I have adapted it to fixed-point math with some constants so that it uses
> only addition, bit shifts and multiplication
>
> To better make use of the filtering and bigger window size, the update
> interval time is cut in half.
>
> For testing, the algorithm can be reverted to the older one via
> debugfs

This looks interesting! Do you have any performance numbers from your
own testing to share? :)

-Toke


^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: [PATCH 2/2] mac80211: minstrel_ht: replace rate stats ewma with a better moving average
  2019-09-29 18:42   ` Toke Høiland-Jørgensen
@ 2019-09-29 19:18     ` Felix Fietkau
  2019-09-29 19:46       ` Toke Høiland-Jørgensen
  0 siblings, 1 reply; 10+ messages in thread
From: Felix Fietkau @ 2019-09-29 19:18 UTC (permalink / raw)
  To: Toke Høiland-Jørgensen, linux-wireless; +Cc: johannes

On 2019-09-29 20:42, Toke Høiland-Jørgensen wrote:
> Felix Fietkau <nbd@nbd.name> writes:
> 
>> Rate success probability usually fluctuates a lot under normal conditions.
>> With a simple EWMA, noise and fluctuation can be reduced by increasing the
>> window length, but that comes at the cost of introducing lag on sudden
>> changes.
>>
>> This change replaces the EWMA implementation with a moving average that's
>> designed to significantly reduce lag while keeping a bigger window size
>> by being better at filtering out noise.
>>
>> It is only slightly more expensive than the simple EWMA and still avoids
>> divisions in its calculation.
>>
>> The algorithm is adapted from an implementation intended for a completely
>> different field (stock market trading), where the tradeoff of lag vs
>> noise filtering is equally important. It is based on the "smoothing filter"
>> from http://www.stockspotter.com/files/PredictiveIndicators.pdf.
>>
>> I have adapted it to fixed-point math with some constants so that it uses
>> only addition, bit shifts and multiplication
>>
>> To better make use of the filtering and bigger window size, the update
>> interval time is cut in half.
>>
>> For testing, the algorithm can be reverted to the older one via
>> debugfs
> 
> This looks interesting! Do you have any performance numbers from your
> own testing to share? :)
To show the difference, I also generated some random data, ran it
through minstrel's EWMA and the new code and made a plot:
http://nbd.name/ewma-filter-plot.png

The real world test that I did was using mt76x2:
I ran 3 iperf TCP streams from an AP to a station in a cable setup with
an attenuator.
I switched from 70 dB attenuation to 40 dB and measured the time it
takes for TCP throughput to stabilize at a higher rate.
Without my changes it takes about 5-6 seconds, with my changes it's only
2-3 seconds.

- Felix

^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: [PATCH 2/2] mac80211: minstrel_ht: replace rate stats ewma with a better moving average
  2019-09-29 19:18     ` Felix Fietkau
@ 2019-09-29 19:46       ` Toke Høiland-Jørgensen
  0 siblings, 0 replies; 10+ messages in thread
From: Toke Høiland-Jørgensen @ 2019-09-29 19:46 UTC (permalink / raw)
  To: Felix Fietkau, linux-wireless; +Cc: johannes

Felix Fietkau <nbd@nbd.name> writes:

> On 2019-09-29 20:42, Toke Høiland-Jørgensen wrote:
>> Felix Fietkau <nbd@nbd.name> writes:
>> 
>>> Rate success probability usually fluctuates a lot under normal conditions.
>>> With a simple EWMA, noise and fluctuation can be reduced by increasing the
>>> window length, but that comes at the cost of introducing lag on sudden
>>> changes.
>>>
>>> This change replaces the EWMA implementation with a moving average that's
>>> designed to significantly reduce lag while keeping a bigger window size
>>> by being better at filtering out noise.
>>>
>>> It is only slightly more expensive than the simple EWMA and still avoids
>>> divisions in its calculation.
>>>
>>> The algorithm is adapted from an implementation intended for a completely
>>> different field (stock market trading), where the tradeoff of lag vs
>>> noise filtering is equally important. It is based on the "smoothing filter"
>>> from http://www.stockspotter.com/files/PredictiveIndicators.pdf.
>>>
>>> I have adapted it to fixed-point math with some constants so that it uses
>>> only addition, bit shifts and multiplication
>>>
>>> To better make use of the filtering and bigger window size, the update
>>> interval time is cut in half.
>>>
>>> For testing, the algorithm can be reverted to the older one via
>>> debugfs
>> 
>> This looks interesting! Do you have any performance numbers from your
>> own testing to share? :)
> To show the difference, I also generated some random data, ran it
> through minstrel's EWMA and the new code and made a plot:
> http://nbd.name/ewma-filter-plot.png

Oh, wow, yeah, that looks way more responsive...

> The real world test that I did was using mt76x2:
> I ran 3 iperf TCP streams from an AP to a station in a cable setup with
> an attenuator.
> I switched from 70 dB attenuation to 40 dB and measured the time it
> takes for TCP throughput to stabilize at a higher rate.
> Without my changes it takes about 5-6 seconds, with my changes it's only
> 2-3 seconds.

Very cool. Thanks!

-Toke


^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: [PATCH 2/2] mac80211: minstrel_ht: replace rate stats ewma with a better moving average
  2019-09-29 15:46 ` [PATCH 2/2] mac80211: minstrel_ht: replace rate stats ewma with a better moving average Felix Fietkau
  2019-09-29 18:42   ` Toke Høiland-Jørgensen
@ 2019-10-01 10:17   ` Johannes Berg
  2019-10-01 10:52     ` Felix Fietkau
  2019-10-08  9:18   ` Koen Vandeputte
  2 siblings, 1 reply; 10+ messages in thread
From: Johannes Berg @ 2019-10-01 10:17 UTC (permalink / raw)
  To: Felix Fietkau, linux-wireless


> This change replaces the EWMA implementation with a moving average that's
> designed to significantly reduce lag while keeping a bigger window size
> by being better at filtering out noise.
> 
> It is only slightly more expensive than the simple EWMA and still avoids
> divisions in its calculation.
> 
> The algorithm is adapted from an implementation intended for a completely
> different field (stock market trading), where the tradeoff of lag vs
> noise filtering is equally important. It is based on the "smoothing filter"
> from http://www.stockspotter.com/files/PredictiveIndicators.pdf.
> 
> I have adapted it to fixed-point math with some constants so that it uses
> only addition, bit shifts and multiplication
> 

Would it be worth pulling that out into similar helpers to EWMA in
average.h, perhaps even in the same file?

You need to keep a bit more state, but essentially the same API should
work since EWMA already declares the "struct ewma_something" once you
use the DECLARE_EWMA().

johannes


^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: [PATCH 2/2] mac80211: minstrel_ht: replace rate stats ewma with a better moving average
  2019-10-01 10:17   ` Johannes Berg
@ 2019-10-01 10:52     ` Felix Fietkau
  2019-10-01 11:06       ` Johannes Berg
  0 siblings, 1 reply; 10+ messages in thread
From: Felix Fietkau @ 2019-10-01 10:52 UTC (permalink / raw)
  To: Johannes Berg, linux-wireless

On 2019-10-01 12:17, Johannes Berg wrote:
> 
>> This change replaces the EWMA implementation with a moving average that's
>> designed to significantly reduce lag while keeping a bigger window size
>> by being better at filtering out noise.
>> 
>> It is only slightly more expensive than the simple EWMA and still avoids
>> divisions in its calculation.
>> 
>> The algorithm is adapted from an implementation intended for a completely
>> different field (stock market trading), where the tradeoff of lag vs
>> noise filtering is equally important. It is based on the "smoothing filter"
>> from http://www.stockspotter.com/files/PredictiveIndicators.pdf.
>> 
>> I have adapted it to fixed-point math with some constants so that it uses
>> only addition, bit shifts and multiplication
>> 
> 
> Would it be worth pulling that out into similar helpers to EWMA in
> average.h, perhaps even in the same file?
> 
> You need to keep a bit more state, but essentially the same API should
> work since EWMA already declares the "struct ewma_something" once you
> use the DECLARE_EWMA().
Might be useful, yes. The main issue here is that the period / window
size has to be hardcoded through the coefficient values, unless we find
a way to do floating point math, including exp() and cos() at compile
time, including conversion to fixed point.

- Felix

^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: [PATCH 2/2] mac80211: minstrel_ht: replace rate stats ewma with a better moving average
  2019-10-01 10:52     ` Felix Fietkau
@ 2019-10-01 11:06       ` Johannes Berg
  2019-10-01 11:11         ` Johannes Berg
  0 siblings, 1 reply; 10+ messages in thread
From: Johannes Berg @ 2019-10-01 11:06 UTC (permalink / raw)
  To: Felix Fietkau, linux-wireless

On Tue, 2019-10-01 at 12:52 +0200, Felix Fietkau wrote:
> 
> Might be useful, yes. The main issue here is that the period / window
> size has to be hardcoded through the coefficient values, unless we find
> a way to do floating point math, including exp() and cos() at compile
> time, including conversion to fixed point.

Works fine for me?

#include <math.h>
#include <stdio.h>
#include <stdlib.h>

#define E(x) ((int)(exp(x) * (1<<20)))
#define C(x) ((int)(cos(x) * (1<<20)))

int main()
{
        int e2 = E(2);
        int c2 = C(2);

        printf("e2: %d\n", e2);
        printf("whole: %d frac: %d\n", e2 >> 20, e2 & ((1 << 20) - 1));
        printf("c2: %d\n", c2);
        printf("sign: %s whole: %d frac: %d\n", c2 < 0 ? "-" : "", abs(c2) >> 20, abs(c2) & ((1 << 20) - 1));
}

objdump -dr test:
[...]
0000000000401040 <main>:
  401040:	48 83 ec 08          	sub    $0x8,%rsp
  401044:	be 92 39 76 00       	mov    $0x763992,%esi		// exp(2) * (1<<20)
  401049:	bf 10 20 40 00       	mov    $0x402010,%edi
  40104e:	31 c0                	xor    %eax,%eax
  401050:	e8 db ff ff ff       	callq  401030 <printf@plt>
  401055:	ba 92 39 06 00       	mov    $0x63992,%edx
  40105a:	be 07 00 00 00       	mov    $0x7,%esi
  40105f:	31 c0                	xor    %eax,%eax
  401061:	bf 2b 20 40 00       	mov    $0x40202b,%edi
  401066:	e8 c5 ff ff ff       	callq  401030 <printf@plt>
  40106b:	be 77 57 f9 ff       	mov    $0xfff95777,%esi
  401070:	bf 18 20 40 00       	mov    $0x402018,%edi
  401075:	31 c0                	xor    %eax,%eax
  401077:	e8 b4 ff ff ff       	callq  401030 <printf@plt>
  40107c:	b9 89 a8 06 00       	mov    $0x6a889,%ecx		// cos(2) * (1<<20)
  401081:	31 d2                	xor    %edx,%edx
  401083:	31 c0                	xor    %eax,%eax
  401085:	be 20 20 40 00       	mov    $0x402020,%esi
  40108a:	bf 22 20 40 00       	mov    $0x402022,%edi
  40108f:	e8 9c ff ff ff       	callq  401030 <printf@plt>
[...]

johannes


^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: [PATCH 2/2] mac80211: minstrel_ht: replace rate stats ewma with a better moving average
  2019-10-01 11:06       ` Johannes Berg
@ 2019-10-01 11:11         ` Johannes Berg
  0 siblings, 0 replies; 10+ messages in thread
From: Johannes Berg @ 2019-10-01 11:11 UTC (permalink / raw)
  To: Felix Fietkau, linux-wireless

On Tue, 2019-10-01 at 13:06 +0200, Johannes Berg wrote:
> On Tue, 2019-10-01 at 12:52 +0200, Felix Fietkau wrote:
> > Might be useful, yes. The main issue here is that the period / window
> > size has to be hardcoded through the coefficient values, unless we find
> > a way to do floating point math, including exp() and cos() at compile
> > time, including conversion to fixed point.
> 
> Works fine for me?
> 
[snip]

I guess really the question is - how do we ensure that happened and fail
if it didn't?

johannes


^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: [PATCH 2/2] mac80211: minstrel_ht: replace rate stats ewma with a better moving average
  2019-09-29 15:46 ` [PATCH 2/2] mac80211: minstrel_ht: replace rate stats ewma with a better moving average Felix Fietkau
  2019-09-29 18:42   ` Toke Høiland-Jørgensen
  2019-10-01 10:17   ` Johannes Berg
@ 2019-10-08  9:18   ` Koen Vandeputte
  2 siblings, 0 replies; 10+ messages in thread
From: Koen Vandeputte @ 2019-10-08  9:18 UTC (permalink / raw)
  To: Felix Fietkau, linux-wireless; +Cc: johannes

Tested on dozens of devices interconnected offshore in IBSS (static and 
moving)

Works as advertised and reduces slight drops noticed on vessel movement.

Tested-by: Koen Vandeputte <koen.vandeputte@ncentric.com>


^ permalink raw reply	[flat|nested] 10+ messages in thread

end of thread, back to index

Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-09-29 15:46 [PATCH 1/2] mac80211: minstrel: remove divisions in tx status path Felix Fietkau
2019-09-29 15:46 ` [PATCH 2/2] mac80211: minstrel_ht: replace rate stats ewma with a better moving average Felix Fietkau
2019-09-29 18:42   ` Toke Høiland-Jørgensen
2019-09-29 19:18     ` Felix Fietkau
2019-09-29 19:46       ` Toke Høiland-Jørgensen
2019-10-01 10:17   ` Johannes Berg
2019-10-01 10:52     ` Felix Fietkau
2019-10-01 11:06       ` Johannes Berg
2019-10-01 11:11         ` Johannes Berg
2019-10-08  9:18   ` Koen Vandeputte

Linux-Wireless Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/linux-wireless/0 linux-wireless/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 linux-wireless linux-wireless/ https://lore.kernel.org/linux-wireless \
		linux-wireless@vger.kernel.org linux-wireless@archiver.kernel.org
	public-inbox-index linux-wireless

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.linux-wireless


AGPL code for this site: git clone https://public-inbox.org/ public-inbox