Add a new module offering a helper to compute the Cumulative Moving Average (CMA) and the Exponential Moving Average (EMA) of a series of values.
Use the new helpers to add latency metrics in dpif-netdev. Signed-off-by: Gaetan Rivet <gr...@u256.net> Reviewed-by: Eli Britstein <el...@nvidia.com> Reviewed-by: Maxime Coquelin <maxime.coque...@redhat.com> --- lib/automake.mk | 1 + lib/mov-avg.h | 171 ++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 172 insertions(+) create mode 100644 lib/mov-avg.h diff --git a/lib/automake.mk b/lib/automake.mk index 46f869a33..804c8da6f 100644 --- a/lib/automake.mk +++ b/lib/automake.mk @@ -179,6 +179,7 @@ lib_libopenvswitch_la_SOURCES = \ lib/memory.c \ lib/memory.h \ lib/meta-flow.c \ + lib/mov-avg.h \ lib/multipath.c \ lib/multipath.h \ lib/namemap.c \ diff --git a/lib/mov-avg.h b/lib/mov-avg.h new file mode 100644 index 000000000..36a6ceb76 --- /dev/null +++ b/lib/mov-avg.h @@ -0,0 +1,171 @@ +/* + * Copyright (c) 2021 NVIDIA Corporation. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef _MOV_AVG_H +#define _MOV_AVG_H 1 + +#include <math.h> + +/* Moving average helpers. */ + +/* Cumulative Moving Average. + * + * Computes the arithmetic mean over a whole series of value. + * Online equivalent of sum(V) / len(V). + * + * As all values have equal weight, this average will + * be slow to show recent changes in the series. + * + */ + +struct mov_avg_cma { + unsigned long long int count; + double mean; + double sum_dsquared; +}; + +#define MOV_AVG_CMA_INITIALIZER \ + { .count = 0, .mean = .0, .sum_dsquared = .0 } + +static inline void +mov_avg_cma_init(struct mov_avg_cma *cma) +{ + *cma = (struct mov_avg_cma) MOV_AVG_CMA_INITIALIZER; +} + +static inline void +mov_avg_cma_update(struct mov_avg_cma *cma, double new_val) +{ + double new_mean; + + cma->count++; + new_mean = cma->mean + (new_val - cma->mean) / cma->count; + + cma->sum_dsquared += (new_val - new_mean) * (new_val - cma->mean); + cma->mean = new_mean; +} + +static inline double +mov_avg_cma(struct mov_avg_cma *cma) +{ + return cma->mean; +} + +static inline double +mov_avg_cma_std_dev(struct mov_avg_cma *cma) +{ + double variance = 0.0; + + if (cma->count > 1) { + variance = cma->sum_dsquared / (cma->count - 1); + } + + return sqrt(variance); +} + +/* Exponential Moving Average. + * + * Each value in the series has an exponentially decreasing weight, + * the older they get the less weight they have. + * + * The smoothing factor 'alpha' must be within 0 < alpha < 1. + * The closer this factor to zero, the more equal the weight between + * recent and older values. As it approaches one, the more recent values + * will have more weight. + * + * The EMA can be thought of as an estimator for the next value when measures + * are dependent. In this case, it can make sense to consider the mean square + * error of the prediction. An 'alpha' minimizing this error would be the + * better choice to improve the estimation. + * + * A common way to choose 'alpha' is to use the following formula: + * + * a = 2 / (N + 1) + * + * With this 'alpha', the EMA will have the same 'center of mass' as an + * equivalent N-values Simple Moving Average. + * + * When using this factor, the N last values of the EMA will have a sum weight + * converging toward 0.8647, meaning that those values will account for 86% of + * the average[1]. + * + * [1] https://en.wikipedia.org/wiki/Moving_average#Exponential_moving_average + */ + +struct mov_avg_ema { + double alpha; /* 'Smoothing' factor. */ + double mean; + double variance; + bool initialized; +}; + +/* Choose alpha explicitly. */ +#define MOV_AVG_EMA_INITIALIZER_ALPHA(a) { \ + .initialized = false, \ + .alpha = (a), .variance = 0.0, .mean = 0.0 \ +} + +/* Choose alpha to consider 'N' past periods as 86% of the EMA. */ +#define MOV_AVG_EMA_INITIALIZER(n_elem) \ + MOV_AVG_EMA_INITIALIZER_ALPHA(2.0 / ((double)(n_elem) + 1.0)) + +static inline void +mov_avg_ema_init_alpha(struct mov_avg_ema *ema, + double alpha) +{ + *ema = (struct mov_avg_ema) MOV_AVG_EMA_INITIALIZER_ALPHA(alpha); +} + +static inline void +mov_avg_ema_init(struct mov_avg_ema *ema, + unsigned long long int n_elem) +{ + *ema = (struct mov_avg_ema) MOV_AVG_EMA_INITIALIZER(n_elem); +} + +static inline void +mov_avg_ema_update(struct mov_avg_ema *ema, double new_val) +{ + const double alpha = ema->alpha; + double alpha_diff; + double diff; + + if (!ema->initialized) { + ema->initialized = true; + ema->mean = new_val; + return; + } + + diff = new_val - ema->mean; + alpha_diff = alpha * diff; + + ema->variance = (1.0 - alpha) * (ema->variance + alpha_diff * diff); + ema->mean = ema->mean + alpha_diff; +} + +static inline double +mov_avg_ema(struct mov_avg_ema *ema) +{ + return ema->mean; +} + +static inline double +mov_avg_ema_std_dev(struct mov_avg_ema *ema) +{ + return sqrt(ema->variance); +} + +#endif /* _MOV_AVG_H */ -- 2.31.1 _______________________________________________ dev mailing list d...@openvswitch.org https://mail.openvswitch.org/mailman/listinfo/ovs-dev