/*
- * Copyright 2012 Facebook, Inc.
+ * Copyright 2014 Facebook, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
#define FOLLY_STATS_BUCKETEDTIMESERIES_INL_H_
#include <glog/logging.h>
+#include <folly/Likely.h>
namespace folly {
template <typename VT, typename TT>
-BucketedTimeSeries<VT, TT>::BucketedTimeSeries(size_t numBuckets,
- TimeType duration)
+BucketedTimeSeries<VT, TT>::BucketedTimeSeries(size_t nBuckets,
+ TimeType maxDuration)
: firstTime_(1),
latestTime_(0),
- duration_(duration) {
+ duration_(maxDuration) {
// For tracking all-time data we only use total_, and don't need to bother
// with buckets_
if (!isAllTime()) {
- // Round numBuckets down to duration_.count().
+ // Round nBuckets down to duration_.count().
//
// There is no point in having more buckets than our timestamp
// granularity: otherwise we would have buckets that could never be used.
- if (numBuckets > duration_.count()) {
- numBuckets = duration_.count();
+ if (nBuckets > size_t(duration_.count())) {
+ nBuckets = duration_.count();
}
- buckets_.resize(numBuckets, Bucket());
+ buckets_.resize(nBuckets, Bucket());
}
}
template <typename VT, typename TT>
-void BucketedTimeSeries<VT, TT>::addValue(TimeType now, const ValueType& val) {
- addValueAggregated(now, val, 1);
+bool BucketedTimeSeries<VT, TT>::addValue(TimeType now, const ValueType& val) {
+ return addValueAggregated(now, val, 1);
}
template <typename VT, typename TT>
-void BucketedTimeSeries<VT, TT>::addValue(TimeType now,
+bool BucketedTimeSeries<VT, TT>::addValue(TimeType now,
const ValueType& val,
int64_t times) {
- addValueAggregated(now, val * times, times);
+ return addValueAggregated(now, val * times, times);
}
template <typename VT, typename TT>
-void BucketedTimeSeries<VT, TT>::addValueAggregated(TimeType now,
- const ValueType& sum,
+bool BucketedTimeSeries<VT, TT>::addValueAggregated(TimeType now,
+ const ValueType& total,
int64_t nsamples) {
- // Make sure time doesn't go backwards
- now = std::max(now, latestTime_);
-
if (isAllTime()) {
- if (empty()) {
+ if (UNLIKELY(empty())) {
+ firstTime_ = now;
+ latestTime_ = now;
+ } else if (now > latestTime_) {
+ latestTime_ = now;
+ } else if (now < firstTime_) {
firstTime_ = now;
}
- latestTime_ = now;
- total_.add(sum, nsamples);
- return;
+ total_.add(total, nsamples);
+ return true;
}
- // Update the buckets
- size_t curBucket = update(now);
- buckets_[curBucket].add(sum, nsamples);
+ size_t bucketIdx;
+ if (UNLIKELY(empty())) {
+ // First data point we've ever seen
+ firstTime_ = now;
+ latestTime_ = now;
+ bucketIdx = getBucketIdx(now);
+ } else if (now > latestTime_) {
+ // More recent time. Need to update the buckets.
+ bucketIdx = updateBuckets(now);
+ } else if (LIKELY(now == latestTime_)) {
+ // Current time.
+ bucketIdx = getBucketIdx(now);
+ } else {
+ // An earlier time in the past. We need to check if this time still falls
+ // within our window.
+ if (now < getEarliestTimeNonEmpty()) {
+ return false;
+ }
+ bucketIdx = getBucketIdx(now);
+ }
- // Update the aggregate sum/count
- total_.add(sum, nsamples);
+ total_.add(total, nsamples);
+ buckets_[bucketIdx].add(total, nsamples);
+ return true;
}
template <typename VT, typename TT>
return getBucketIdx(latestTime_);
}
+ return updateBuckets(now);
+}
+
+template <typename VT, typename TT>
+size_t BucketedTimeSeries<VT, TT>::updateBuckets(TimeType now) {
// We could cache nextBucketStart as a member variable, so we don't have to
// recompute it each time update() is called with a new timestamp value.
// This makes things faster when update() (or addValue()) is called once
template <typename VT, typename TT>
-TT BucketedTimeSeries<VT, TT>::elapsed() const {
+TT BucketedTimeSeries<VT, TT>::getEarliestTime() const {
if (empty()) {
return TimeType(0);
}
-
if (isAllTime()) {
- return latestTime_ - firstTime_ + TimeType(1);
+ return firstTime_;
}
+ // Compute the earliest time we can track
+ TimeType earliestTime = getEarliestTimeNonEmpty();
+
+ // We're never tracking data before firstTime_
+ earliestTime = std::max(earliestTime, firstTime_);
+
+ return earliestTime;
+}
+
+template <typename VT, typename TT>
+TT BucketedTimeSeries<VT, TT>::getEarliestTimeNonEmpty() const {
size_t currentBucket;
TimeType currentBucketStart;
TimeType nextBucketStart;
// Subtract 1 duration from the start of the next bucket to find the
// earliest possible data point we could be tracking.
- TimeType earliestTime = nextBucketStart - duration_;
+ return nextBucketStart - duration_;
+}
- // We're never tracking data before firstTime_
- earliestTime = std::max(earliestTime, firstTime_);
+template <typename VT, typename TT>
+TT BucketedTimeSeries<VT, TT>::elapsed() const {
+ if (empty()) {
+ return TimeType(0);
+ }
+
+ // Add 1 since [latestTime_, earliestTime] is an inclusive interval.
+ return latestTime_ - getEarliestTime() + TimeType(1);
+}
- return latestTime_ - earliestTime + TimeType(1);
+template <typename VT, typename TT>
+TT BucketedTimeSeries<VT, TT>::elapsed(TimeType start, TimeType end) const {
+ if (empty()) {
+ return TimeType(0);
+ }
+ start = std::max(start, getEarliestTime());
+ end = std::min(end, latestTime_ + TimeType(1));
+ end = std::max(start, end);
+ return end - start;
}
template <typename VT, typename TT>
VT BucketedTimeSeries<VT, TT>::sum(TimeType start, TimeType end) const {
- ValueType sum = ValueType();
+ ValueType total = ValueType();
forEachBucket(start, end, [&](const Bucket& bucket,
TimeType bucketStart,
TimeType nextBucketStart) -> bool {
- sum += this->rangeAdjust(bucketStart, nextBucketStart, start, end,
+ total += this->rangeAdjust(bucketStart, nextBucketStart, start, end,
bucket.sum);
return true;
});
- return sum;
+ return total;
}
template <typename VT, typename TT>
uint64_t BucketedTimeSeries<VT, TT>::count(TimeType start, TimeType end) const {
- uint64_t count = 0;
+ uint64_t sample_count = 0;
forEachBucket(start, end, [&](const Bucket& bucket,
TimeType bucketStart,
TimeType nextBucketStart) -> bool {
- count += this->rangeAdjust(bucketStart, nextBucketStart, start, end,
+ sample_count += this->rangeAdjust(bucketStart, nextBucketStart, start, end,
bucket.count);
return true;
});
- return count;
+ return sample_count;
}
template <typename VT, typename TT>
template <typename ReturnType>
ReturnType BucketedTimeSeries<VT, TT>::avg(TimeType start, TimeType end) const {
- ValueType sum = ValueType();
- uint64_t count = 0;
+ ValueType total = ValueType();
+ uint64_t sample_count = 0;
forEachBucket(start, end, [&](const Bucket& bucket,
TimeType bucketStart,
TimeType nextBucketStart) -> bool {
- sum += this->rangeAdjust(bucketStart, nextBucketStart, start, end,
+ total += this->rangeAdjust(bucketStart, nextBucketStart, start, end,
bucket.sum);
- count += this->rangeAdjust(bucketStart, nextBucketStart, start, end,
+ sample_count += this->rangeAdjust(bucketStart, nextBucketStart, start, end,
bucket.count);
return true;
});
- if (count == 0) {
+ if (sample_count == 0) {
return ReturnType(0);
}
- return detail::avgHelper<ReturnType>(sum, count);
+ return detail::avgHelper<ReturnType>(total, sample_count);
}
/*