[RFC v2] average: rewrite for clearity

[RFC v2] average: rewrite for clearity

[Benjamin Beichler]

Move the former *_add function with its implicit initialization into a
separate function, when the user explicitly wants to init with the first
added value, although this creates issues, when 0 is a expected value for
the internal value.

Add a separate init function with value parameter to allow init with
distinct value, which was formerly done by the implicit init of old
*_add function.

Move the compile time checks into a separate macro, as they are used
multiple times and noise up the functions.

Signed-off-by: Benjamin Beichler <benjamin.beichler@uni-rostock.de>
---
 include/linux/average.h | 86 ++++++++++++++++++++++++-----------------
 1 file changed, 50 insertions(+), 36 deletions(-)

diff --git a/include/linux/average.h b/include/linux/average.h
index a1a8f09631ce..7149a9ee555a 100644
--- a/include/linux/average.h
+++ b/include/linux/average.h
@@ -25,47 +25,61 @@
  * that this parameter must be a power of two for efficiency.
  */
 
-#define DECLARE_EWMA(name, _precision, _weight_rcp)			\
-	struct ewma_##name {						\
-		unsigned long internal;					\
-	};								\
-	static inline void ewma_##name##_init(struct ewma_##name *e)	\
-	{								\
+#define EWMA_BUILD_TIME_CHECKS(_precision, _weight_rcp)			\
+	do {								\
 		BUILD_BUG_ON(!__builtin_constant_p(_precision));	\
 		BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp));	\
-		/*							\
-		 * Even if you want to feed it just 0/1 you should have	\
-		 * some bits for the non-fractional part...		\
-		 */							\
-		BUILD_BUG_ON((_precision) > 30);			\
-		BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp);		\
-		e->internal = 0;					\
-	}								\
-	static inline unsigned long					\
-	ewma_##name##_read(struct ewma_##name *e)			\
-	{								\
-		BUILD_BUG_ON(!__builtin_constant_p(_precision));	\
-		BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp));	\
-		BUILD_BUG_ON((_precision) > 30);			\
-		BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp);		\
-		return e->internal >> (_precision);			\
-	}								\
-	static inline void ewma_##name##_add(struct ewma_##name *e,	\
-					     unsigned long val)		\
-	{								\
-		unsigned long internal = READ_ONCE(e->internal);	\
-		unsigned long weight_rcp = ilog2(_weight_rcp);		\
-		unsigned long precision = _precision;			\
 									\
-		BUILD_BUG_ON(!__builtin_constant_p(_precision));	\
-		BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp));	\
 		BUILD_BUG_ON((_precision) > 30);			\
 		BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp);		\
-									\
-		WRITE_ONCE(e->internal, internal ?			\
-			(((internal << weight_rcp) - internal) +	\
-				(val << precision)) >> weight_rcp :	\
-			(val << precision));				\
+	} while (0)
+
+#define DECLARE_EWMA(name, _precision, _weight_rcp)				\
+	struct ewma_##name {							\
+		unsigned long internal;						\
+	};									\
+	static inline void ewma_##name##_init_val(struct ewma_##name *e,	\
+						  unsigned long init)		\
+	{									\
+		EWMA_BUILD_TIME_CHECKS(_precision, _weight_rcp)			\
+		e->internal = init << _precision;				\
+	}									\
+	static inline void ewma_##name##_init(struct ewma_##name *e)		\
+	{									\
+			ewma_##name##_init_val(e, 0);				\
+	}									\
+	static inline unsigned long						\
+	ewma_##name##_read(struct ewma_##name *e)				\
+	{									\
+		EWMA_BUILD_TIME_CHECKS(_precision, _weight_rcp)			\
+		return e->internal >> (_precision);				\
+	}									\
+	static inline void ewma_##name##_add(struct ewma_##name *e,		\
+					     unsigned long val)			\
+	{									\
+		unsigned long internal = READ_ONCE(e->internal);		\
+		unsigned long weight_rcp = ilog2(_weight_rcp);			\
+		unsigned long precision = _precision;				\
+										\
+		EWMA_BUILD_TIME_CHECKS(_precision, _weight_rcp)			\
+										\
+		WRITE_ONCE(e->internal,						\
+			(((internal << weight_rcp) - internal) +		\
+				(val << precision)) >> weight_rcp);		\
+	}									\
+	static inline void ewma_##name##_add_or_init(struct ewma_##name *e,	\
+					     unsigned long val)			\
+	{									\
+		unsigned long internal = READ_ONCE(e->internal);		\
+		unsigned long weight_rcp = ilog2(_weight_rcp);			\
+		unsigned long precision = _precision;				\
+										\
+		EWMA_BUILD_TIME_CHECKS(_precision, _weight_rcp)			\
+										\
+		WRITE_ONCE(e->internal, internal ?				\
+			(((internal << weight_rcp) - internal) +		\
+				(val << precision)) >> weight_rcp :		\
+			(val << precision));					\
 	}
 
 #endif /* _LINUX_AVERAGE_H */
-- 
2.25.1

Re: [RFC v2] average: rewrite for clearity

[Johannes Berg]

On Fri, 2023-04-21 at 13:46 +0000, Benjamin Beichler wrote:
> Move the former *_add function with its implicit initialization into a
> separate function, when the user explicitly wants to init with the first
> added value, although this creates issues, when 0 is a expected value for
> the internal value.
> 
> Add a separate init function with value parameter to allow init with
> distinct value, which was formerly done by the implicit init of old
> *_add function.
> 

Sure, this is what you said :-)

I still don't really think it's feasible. First, this breaks all the
users, because if you have e.g. virtio's DECLARE_EWMA(pkt_len, 0, 64)
then it will take a long time to get away from 0.

So then we could say we'll just fix them, but what value actually makes
sense to init with? You don't necessarily know, right? Initially biasing
towards the first value makes a lot more sense than initially biasing
towards zero, no? And then if you want to achieve that, now you have to
either use _add_or_init(), which is probably what people will do, but
that continues having the problem ...

I don't really see how this is a net improvement - we'd still have to
fix the individual users with it, e.g. maybe the mesh case that started
this investigation could bias towards success (init with 100) and then
use _add() rather than _add_or_init(), but then again we're back to
having to make individual choices with the users. I don't really see how
that's better than fixing it for real with the existing behaviour of
biasing towards the first value?

johannes

Re: [RFC v2] average: rewrite for clearity

[Benjamin Beichler]

Am 21.04.2023 um 16:37 schrieb Johannes Berg:
> ________________________________
>   Achtung! Externe E-Mail: Klicken Sie erst dann auf Links und Anhänge, nachdem Sie die Vertrauenswürdigkeit der Absenderadresse geprüft haben.
> ________________________________
>
> On Fri, 2023-04-21 at 13:46 +0000, Benjamin Beichler wrote:
>> Move the former *_add function with its implicit initialization into a
>> separate function, when the user explicitly wants to init with the first
>> added value, although this creates issues, when 0 is a expected value for
>> the internal value.
>>
>> Add a separate init function with value parameter to allow init with
>> distinct value, which was formerly done by the implicit init of old
>> *_add function.
>>
> Sure, this is what you said :-)
>
> I still don't really think it's feasible. First, this breaks all the
> users, because if you have e.g. virtio's DECLARE_EWMA(pkt_len, 0, 64)
> then it will take a long time to get away from 0.
>
> So then we could say we'll just fix them, but what value actually makes
> sense to init with? You don't necessarily know, right? Initially biasing
> towards the first value makes a lot more sense than initially biasing
> towards zero, no? And then if you want to achieve that, now you have to
> either use _add_or_init(), which is probably what people will do, but
> that continues having the problem ...

I left out the the individual fixes for users, but for the samples I
looked into, either start values were given, or they were semantically
extractable.

e.g. virtios pkt_len  ewma is clamped anyways, so using the clamp border
or in between will be safe.

Most others are signals-strengths, many of them also only for
statistics, where a slow convergence is okay in my opinion.

> I don't really see how this is a net improvement - we'd still have to
> fix the individual users with it, e.g. maybe the mesh case that started
> this investigation could bias towards success (init with 100) and then
> use _add() rather than _add_or_init(), but then again we're back to
> having to make individual choices with the users. I don't really see how
> that's better than fixing it for real with the existing behaviour of
> biasing towards the first value?

IMHO the net improvement is, that if you do not use the convenience
add_or_init function, it simply resembles the ewma filter of a math or
CS-textbook. The original problem was, that the ewma had a surprising
output in a special situation.

But while writing the commit, I recognized, that the current ewma
implementation is only for unsigned values, which means the problem
really only happens for many consecutive 0 values. I try to think over,
what this means for the proposal of Felix, but I'm not able to think
about unsigned C-arithmetics today :-D

If we use that fix, then we should have an additional compile time
check, that the precision has at least 2 or 4 bits, to really avoid the
problem, shouldn't we?

Benjamin

Re: [RFC v2] average: rewrite for clearity

[Johannes Berg]

On Fri, 2023-04-21 at 17:16 +0200, Benjamin Beichler wrote:
> > 
> > So then we could say we'll just fix them, but what value actually makes
> > sense to init with? You don't necessarily know, right? Initially biasing
> > towards the first value makes a lot more sense than initially biasing
> > towards zero, no? And then if you want to achieve that, now you have to
> > either use _add_or_init(), which is probably what people will do, but
> > that continues having the problem ...
> 
> I left out the the individual fixes for users, but for the samples I 
> looked into, either start values were given, or they were semantically 
> extractable.
> 
> e.g. virtios pkt_len  ewma is clamped anyways, so using the clamp border 
> or in between will be safe.
> 
> Most others are signals-strengths, many of them also only for 
> statistics, where a slow convergence is okay in my opinion.

Yeah I guess that's the thing, we can accept slower convergence in many
cases, and "safe" start values mean that mostly. But why accept it when
we don't have to?

> IMHO the net improvement is, that if you do not use the convenience 
> add_or_init function, it simply resembles the ewma filter of a math or 
> CS-textbook. 

Not sure I see that as a good argument. The practical engineering side
tends to always be more complex than the theory, and that's not really
unexpected. We can comment why it's different :-)

> The original problem was, that the ewma had a surprising 
> output in a special situation.

Right, but that's an implementation issue, because we thought 0 ==
uninit was clever, without realizing the corner case.

> But while writing the commit, I recognized, that the current ewma 
> implementation is only for unsigned values, which means the problem 
> really only happens for many consecutive 0 values. I try to think over, 
> what this means for the proposal of Felix, but I'm not able to think 
> about unsigned C-arithmetics today :-D

Not much really, I think? It eases thinking about it though :)

> If we use that fix, then we should have an additional compile time 
> check, that the precision has at least 2 or 4 bits, to really avoid the 
> problem, shouldn't we?

Yes. I think 1 bit is enough, but yes, it can't be 0 bits.

johannes

Re: [RFC v2] average: rewrite for clearity

[Benjamin Beichler]

Am 24.04.2023 um 17:55 schrieb Johannes Berg:
> ________________________________
>   Achtung! Externe E-Mail: Klicken Sie erst dann auf Links und Anhänge, nachdem Sie die Vertrauenswürdigkeit der Absenderadresse geprüft haben.
> ________________________________
>
> On Fri, 2023-04-21 at 17:16 +0200, Benjamin Beichler wrote:
>> IMHO the net improvement is, that if you do not use the convenience
>> add_or_init function, it simply resembles the ewma filter of a math or
>> CS-textbook.
> Not sure I see that as a good argument. The practical engineering side
> tends to always be more complex than the theory, and that's not really
> unexpected. We can comment why it's different :-)
In my opinion, the behavior was without good reason unexpected, but I
think I found a solution, that we are all happy with. See v3.
>
>> The original problem was, that the ewma had a surprising
>> output in a special situation.
> Right, but that's an implementation issue, because we thought 0 ==
> uninit was clever, without realizing the corner case.
>
>> But while writing the commit, I recognized, that the current ewma
>> implementation is only for unsigned values, which means the problem
>> really only happens for many consecutive 0 values. I try to think over,
>> what this means for the proposal of Felix, but I'm not able to think
>> about unsigned C-arithmetics today :-D
> Not much really, I think? It eases thinking about it though :)
>
>> If we use that fix, then we should have an additional compile time
>> check, that the precision has at least 2 or 4 bits, to really avoid the
>> problem, shouldn't we?
> Yes. I think 1 bit is enough, but yes, it can't be 0 bits.

I have wrapped my head around it again, and just send a new version
(which I may split in two patches for the final round). I played around
with the fixed point arithmetic and came to the conclusion, that
ULONG_MAX is a better candidate for initial state, since for valid EWMA
configurations, i.e. a weight_rcp bigger than 1, ULONG_MAX is never
reached. Actually, a precision (or fraction) bigger than 0 seems to be
not needed. However, this means maybe some unexpected oscillation at the
lower bits, so we may enforce it by another compile time check, but
actually I' not really concerned about that :-D

In contrast, I recognized, that if val is too big for the
weight_rcp/precision combination, it can overflow the internal state and
result into much lower values and unexpected jumps of the state.
Currently, I just added a WARN_ONCE for this. For all current users,
this problem should never happen, but a separate clamping of the input
val is maybe too much, and could also be easily implemented by the user
of the function.

Benjamin