| Message ID | 20230421134604.211128-1-benjamin.beichler@uni-rostock.de |
|---|---|
| State | New |
| Headers | show |
| Series | [RFC,v2] average: rewrite for clearity | expand |
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
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
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
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 */
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(-)