Viewing file:  SpeedMeter.h (8.52 KB) -rw-r--r--
Select action/file-type:
 (+) |  (+) |  (+) | Code (+) | Session (+) |  (+) | SDB (+) |  (+) |  (+) |  (+) |  (+) |  (+) |
/*
* Phusion Passenger - https://www.phusionpassenger.com/
* Copyright (c) 2014-2018 Phusion Holding B.V.
*
* "Passenger", "Phusion Passenger" and "Union Station" are registered
* trademarks of Phusion Holding B.V.
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in
* all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
* THE SOFTWARE.
*/
#ifndef _PASSENGER_SPEED_METER_H_
#define _PASSENGER_SPEED_METER_H_
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <limits>
#include <SystemTools/SystemTime.h>
namespace Passenger {
/**
* Utility class which, when periodically fed with quantities, measures the
* rate of change in the most recent time period. It does this by storing
* samples of the most recent quantities, calculating a weighted average of
* the differences between each sample, and extrapolating that over a time
* period.
*
* For example,
*
* * When periodically given the number of miles a car has driven so far,
* the average speed of the most recent 10 minutes can be calculated.
* * When periodically given the number of processes the OS has created
* so far, the average fork rate (per minute) of the most recent minute
* can be calculated.
*
* SpeedMeter is designed to use as little memory as possible, and designed
* so that samples can be taken at erratic intervals. This is why it limits
* the number of samples that can be stored in memory, and why it puts time
* limits on the samples.
*
*
* ## Template parameters
*
* ### `maxSamples`
*
* `maxSamples` dictates the sample buffer size: the maximum number of samples
* to hold in memory. Defaults to 8.
*
* The more samples you have, the more historical data influences the results.
* If you have few samples then recent data have the most impact on the results.
*
* ### `minAge`
*
* A new sample is only accepted if at least `minAge` microseconds
* have passed since the last sample. This is to ensure that the sample
* buffer contains enough historical data so that results are not skewed by
* adding samples too quickly. A full sample buffer is guaranteed to cover
* the last `minAge * maxSamples` microseconds.
*
* Defaults to 1 second (1 000 000 usec).
*
* To see why this is useful, consider when `maxSamples` is 5 and `minAge` is 0.
* If you measure the number of processes 5 times with 10 ms in between,
* then it's unlikely that the OS has spawned any processes in that 50 ms time
* interval. However you've now filled the sample buffer with only data from
* those 5 recent measurements, so SpeedMeter thinks the rate of change is 0.
* If you set `minAge` to, say, 5 seconds, then the sample buffer will be updated
* at most once every 5 seconds, guaranteeing that it can retain historical data
* for the last 25 seconds.
*
* `minAge * maxSamples` should be larger than `window`.
*
* ### `maxAge`
*
* When calculating the result, samples older than `maxAge` usec ago are ignored.
* This value should be larger than `window`. Defaults to 1 minute (60 000 000
* usec).
*
* ### `window`
*
* When calculating the result, this value dictates the time interval over which
* the rate of change should be calculated. Defaults to 1 second (1 000 000 usec),
* meaning that by default the result describes the speed per second.
*
*
* ## Interpreting the parameters
*
* Given parameters, the behavior of SpeedMeter can be interpreted as follows:
*
* All samples that have been collected in the last `minAge * maxSamples` usecs
* (or the last `maxAge` usecs, if samples have been collected slowly), are used for
* calculating the speed per `window` usecs.
*
* Thus, given the default parameter values, we can say:
*
* All samples that have been collected in the last 8 seconds (the last 1 minute,
* if samples have been collected slowly), are used for calculating the speed
* per second.
*/
template<
typename ValueType = double,
unsigned int maxSamples = 8,
unsigned int minAge = 1000000,
unsigned int maxAge = 60 * 1000000,
unsigned int window = 1000000
>
class SpeedMeter {
private:
struct Sample {
unsigned long long timestamp;
ValueType val;
Sample()
: timestamp(0),
val(0)
{ }
};
unsigned short start, count;
Sample samples[maxSamples];
static int mod(int a, int b) {
int r = a % b;
return r < 0 ? r + b : r;
}
const Sample &getSample(int index) const {
return samples[mod(start + index, maxSamples)];
}
const Sample &getLastSample() const {
return getSample(count - 1);
}
unsigned long long getTimeThreshold() const {
const unsigned long long currentTime = SystemTime::getUsec();
if (currentTime > maxAge) {
return currentTime - maxAge;
} else {
return 0;
}
}
void resetOnClockSkew(unsigned long long timestamp) {
if (getLastSample().timestamp > timestamp) {
for (unsigned int i = 0; i < maxSamples; i++) {
samples[i] = Sample();
}
}
}
public:
SpeedMeter()
: start(0),
count(0)
{ }
bool addSample(ValueType val, unsigned long long timestamp = 0) {
if (timestamp == 0) {
timestamp = SystemTime::getUsec();
}
const Sample &lastSample = getLastSample();
resetOnClockSkew(timestamp);
if (lastSample.timestamp <= timestamp - minAge) {
Sample &nextSample = samples[(start + count) % maxSamples];
nextSample.timestamp = timestamp;
nextSample.val = val;
if (count == maxSamples) {
start = (start + 1) % maxSamples;
} else {
count++;
}
return true;
} else {
return false;
}
}
/** Number of items in the sample buffer. */
unsigned int size() const {
return count;
}
/** Current speed over the configured window. Returns unknownSpeed() if less than 2
* samples have been collected so far.
*/
double currentSpeed() const {
const unsigned long long timeThreshold = getTimeThreshold();
int begin = 0, i;
unsigned long long interval;
double avgWeight = 0, sum = 0;
// Ignore samples that are too old.
while (begin < (int) count - 1
&& getSample(begin).timestamp <= timeThreshold)
{
begin++;
}
// Given the deltas of each sample and the next sample,
// calculate the weighted average of all those deltas,
// with time interval of each delta as the weight,
// and calculate the average weight.
for (i = begin; i < (int) count - 1; i++) {
const Sample &cur = getSample(i);
const Sample &next = getSample(i + 1);
ValueType delta = next.val - cur.val;
unsigned long long weight = next.timestamp - cur.timestamp;
sum += (double) delta * weight;
avgWeight += weight;
}
avgWeight /= std::max(1, (int) count - 1 - begin);
interval = getSample((int) count - 1).timestamp - getSample(begin).timestamp;
if (interval > 0) {
// sum / interval is the speed per average delta interval,
// so we extrapolate that over the entire window interval.
return (sum / interval) * (window / avgWeight);
} else {
return unknownSpeed();
}
}
static ValueType unknownSpeed() {
return numeric_limits<ValueType>::max();
}
#if 0
void debug() const {
const unsigned long long timeThreshold = getTimeThreshold();
printf("---- begin debug ----\n");
printf("timeThreshold: %llu\n", timeThreshold);
for (int i = 0; i < (int) maxSamples; i++) {
const Sample &sample = samples[i];
printf("elem %u, sample %u: timestamp = %llu, val = %.0f%s%s%s\n",
i,
mod(i - start, maxSamples),
sample.timestamp,
(double) sample.val,
(sample.timestamp <= timeThreshold) ? " X" : "",
(i == start) ? " <-- start" : "",
(count > 0 && i == mod((int) start + count - 1, maxSamples)) ? " <-- last" : "");
}
printf("---- end debug ----\n");
}
#endif
};
} // namespace Passenger
#endif /* _PASSENGER_SPEED_METER_H_ */
|