/src/openvswitch/lib/mov-avg.h

Source (jump to first uncovered line)
/*
 * 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 */

Line	Count	Source (jump to first uncovered line)
1		/*
2		* Copyright (c) 2021 NVIDIA Corporation.
3		*
4		* Licensed under the Apache License, Version 2.0 (the "License");
5		* you may not use this file except in compliance with the License.
6		* You may obtain a copy of the License at:
7		*
8		* http://www.apache.org/licenses/LICENSE-2.0
9		*
10		* Unless required by applicable law or agreed to in writing, software
11		* distributed under the License is distributed on an "AS IS" BASIS,
12		* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13		* See the License for the specific language governing permissions and
14		* limitations under the License.
15		*/
16
17		#ifndef _MOV_AVG_H
18		#define _MOV_AVG_H 1
19
20		#include <math.h>
21
22		/* Moving average helpers. */
23
24		/* Cumulative Moving Average.
25		*
26		* Computes the arithmetic mean over a whole series of value.
27		* Online equivalent of sum(V) / len(V).
28		*
29		* As all values have equal weight, this average will
30		* be slow to show recent changes in the series.
31		*
32		*/
33
34		struct mov_avg_cma {
35		unsigned long long int count;
36		double mean;
37		double sum_dsquared;
38		};
39
40		#define MOV_AVG_CMA_INITIALIZER \
41	0	{ .count = 0, .mean = .0, .sum_dsquared = .0 }
42
43		static inline void
44		mov_avg_cma_init(struct mov_avg_cma *cma)
45	0	{
46	0	*cma = (struct mov_avg_cma) MOV_AVG_CMA_INITIALIZER;
47	0	}
48
49		static inline void
50		mov_avg_cma_update(struct mov_avg_cma *cma, double new_val)
51	0	{
52	0	double new_mean;
53
54	0	cma->count++;
55	0	new_mean = cma->mean + (new_val - cma->mean) / cma->count;
56
57	0	cma->sum_dsquared += (new_val - new_mean) * (new_val - cma->mean);
58	0	cma->mean = new_mean;
59	0	}
60
61		static inline double
62		mov_avg_cma(struct mov_avg_cma *cma)
63	0	{
64	0	return cma->mean;
65	0	}
66
67		static inline double
68		mov_avg_cma_std_dev(struct mov_avg_cma *cma)
69	0	{
70	0	double variance = 0.0;
71
72	0	if (cma->count > 1) {
73	0	variance = cma->sum_dsquared / (cma->count - 1);
74	0	}
75
76	0	return sqrt(variance);
77	0	}
78
79		/* Exponential Moving Average.
80		*
81		* Each value in the series has an exponentially decreasing weight,
82		* the older they get the less weight they have.
83		*
84		* The smoothing factor 'alpha' must be within 0 < alpha < 1.
85		* The closer this factor to zero, the more equal the weight between
86		* recent and older values. As it approaches one, the more recent values
87		* will have more weight.
88		*
89		* The EMA can be thought of as an estimator for the next value when measures
90		* are dependent. In this case, it can make sense to consider the mean square
91		* error of the prediction. An 'alpha' minimizing this error would be the
92		* better choice to improve the estimation.
93		*
94		* A common way to choose 'alpha' is to use the following formula:
95		*
96		* a = 2 / (N + 1)
97		*
98		* With this 'alpha', the EMA will have the same 'center of mass' as an
99		* equivalent N-values Simple Moving Average.
100		*
101		* When using this factor, the N last values of the EMA will have a sum weight
102		* converging toward 0.8647, meaning that those values will account for 86% of
103		* the average[1].
104		*
105		* [1] https://en.wikipedia.org/wiki/Moving_average#Exponential_moving_average
106		*/
107
108		struct mov_avg_ema {
109		double alpha; /* 'Smoothing' factor. */
110		double mean;
111		double variance;
112		bool initialized;
113		};
114
115		/* Choose alpha explicitly. */
116	0	#define MOV_AVG_EMA_INITIALIZER_ALPHA(a) { \
117	0	.initialized = false, \
118	0	.alpha = (a), .variance = 0.0, .mean = 0.0 \
119	0	}
120
121		/* Choose alpha to consider 'N' past periods as 86% of the EMA. */
122		#define MOV_AVG_EMA_INITIALIZER(n_elem) \
123	0	MOV_AVG_EMA_INITIALIZER_ALPHA(2.0 / ((double)(n_elem) + 1.0))
124
125		static inline void
126		mov_avg_ema_init_alpha(struct mov_avg_ema *ema,
127		double alpha)
128	0	{
129	0	*ema = (struct mov_avg_ema) MOV_AVG_EMA_INITIALIZER_ALPHA(alpha);
130	0	}
131
132		static inline void
133		mov_avg_ema_init(struct mov_avg_ema *ema,
134		unsigned long long int n_elem)
135	0	{
136	0	*ema = (struct mov_avg_ema) MOV_AVG_EMA_INITIALIZER(n_elem);
137	0	}
138
139		static inline void
140		mov_avg_ema_update(struct mov_avg_ema *ema, double new_val)
141	0	{
142	0	const double alpha = ema->alpha;
143	0	double alpha_diff;
144	0	double diff;
145
146	0	if (!ema->initialized) {
147	0	ema->initialized = true;
148	0	ema->mean = new_val;
149	0	return;
150	0	}
151
152	0	diff = new_val - ema->mean;
153	0	alpha_diff = alpha * diff;
154
155	0	ema->variance = (1.0 - alpha) * (ema->variance + alpha_diff * diff);
156	0	ema->mean = ema->mean + alpha_diff;
157	0	}
158
159		static inline double
160		mov_avg_ema(struct mov_avg_ema *ema)
161	0	{
162	0	return ema->mean;
163	0	}
164
165		static inline double
166		mov_avg_ema_std_dev(struct mov_avg_ema *ema)
167	0	{
168	0	return sqrt(ema->variance);
169	0	}
170
171		#endif /* _MOV_AVG_H */

Coverage Report

Created: 2025-07-01 06:50