Akkumulierende Mean Berechnung in C++
Für die Berechnung einer Threadpool Idle Statistik muss jeder Worker-Thread den Zeitpunkt des Arbeitsbeginns und den Zeitpunkt des Arbeitsendes (= Beginn der Idle Phase) loggen. Die Differenz dieser Timestamps ergibt die Verarbeitungsdauer eines einzelnen Work-Items bzw. komplementär das jeweilige Idle Intervall. Für die Berechnung des Mittelwerts der Idle-Intervalle müssen die einzelnen Samples akkumuliert werden. In einer Server-Applikation kann eine permanente Akkumulation durch Aufsummierung problematisch werden, da je nach Größe der einzelnen Samplewerte und Laufzeit des Systems die Wertebereiche von 64 bit Variablen überschritten werden können. Dieses Problem lässt sich durch Mittelung über eine fixe Anzahl von Samplewerten umgehen.
Dazu wird zunächst eine fixed_size_queue Datenstruktur mit fester Maximalgröße eingeführt. Diese erbt sämtliche Funktionalität von std::queue und überschreibt lediglich die push() Funktion, um beim pushen in eine volle Queue ein altes Element zu droppen.
template<class T, class Sequence = std::deque<T> > class fixed_size_queue : public std::queue<T, Sequence> { public: typedef T value_type; typedef typename Sequence::size_type size_type; typedef typename Sequence::const_iterator const_iterator; explicit fixed_size_queue(size_type maxSize) : maxSize_(maxSize) {} void push(const value_type& value) { if(this->size() == maxSize_) this->pop(); std::queue<T, Sequence>::push(value); } const_iterator begin() const { return this->c.begin(); } const_iterator end() const { return this->c.end(); } protected: size_type maxSize_; };
Unter Verwendung dieser Klasse lässt sich nun ein Akkumulator definieren. Dieser wird im Konstruktor auf ein wählbares Sample-Integrationsintervall festgelegt. Nachdem Samples in die interne fixed_size_queue eingefügt wurden, kann über die Funktion value() der aktuelle Mittelwert abgerufen werden.
/** * @brief Sliding window sample accumulator for calculating the mean value * * Please note that SampleType can be any type or class that is convertible * to double. */ template < typename SampleType, template <class> class MeanCalculator = Average > class MeanAccumulator { public: typedef SampleType sample_type; typedef typename MeanCalculator<sample_type>::mean_type mean_type; MeanCalculator<sample_type> mean_calc_; public: explicit MeanAccumulator( typename fixed_size_queue<sample_type>::size_type maxSize) : samples_(maxSize) {} void operator()(sample_type sample) { samples_.push(sample); } const mean_type value() const { return mean_calc_(samples_); } protected: fixed_size_queue<sample_type> samples_; };
Um die Berechnung des Mittelwerts generisch zu halten, wurde eine Policy für dessen Berechnung eingeführt. Die Standard Policy wurde dabei auf Average festgelegt, das wie folgt definiert ist:
template<typename SampleType> class Average { public: typedef SampleType sample_type; typedef double mean_type; typedef fixed_size_queue<sample_type> queue_type; const mean_type operator()( const queue_type& samples) const { mean_type sum = 0.0; typename queue_type::const_iterator it = samples.begin(); for(; it != samples.end(); ++it) { // Divide each summand by size to reduce chances of overflow sum += static_cast<mean_type>(*it) / samples.size(); } return sum; } };
Bei der Berechnung des Mittelwerts wird jedes Sample auf den mean_type (double) konvertiert. Damit ist auch die Verwendung von Klassentypen als Sampletyp möglich, sofern diese einen operator double implementieren. Die Division durch die Anzahl der Samples erfolgt in jedem Summanden. Dies reduziert weiter die Wahrscheinlichkeit eines Overflows.