Stores long-term histogram, outlier information
Moves analysis and storage from NBLog to
PerformanceAnalysis. Applies peak analysis to
outlier information to detect changes in the
distribution of outlier frequency.
Adds cleanup, documentation, FIXME comments for
upcoming changes.
Test: dumpsys media.log
Change-Id: Iea393dac62959aef754ae2a9b4afe2556c1f3ecb
diff --git a/media/libnbaio/PerformanceAnalysis.cpp b/media/libnbaio/PerformanceAnalysis.cpp
index 84b7635..fa8f47e 100644
--- a/media/libnbaio/PerformanceAnalysis.cpp
+++ b/media/libnbaio/PerformanceAnalysis.cpp
@@ -45,8 +45,21 @@
namespace android {
-PerformanceAnalysis::PerformanceAnalysis() : findGlitch(false) {
- kPeriodMsCPU = static_cast<int>(PerformanceAnalysis::kPeriodMs * kRatio);
+PerformanceAnalysis::PerformanceAnalysis() {
+ // These variables will be (FIXME) learned from the data
+ kPeriodMs = 4; // typical buffer period (mode)
+ // average number of Ms spent processing buffer
+ kPeriodMsCPU = static_cast<int>(kPeriodMs * kRatio);
+}
+
+// converts a time series into a map. key: buffer period length. value: count
+static std::map<int, int> buildBuckets(const std::vector<int64_t> &samples) {
+ // TODO allow buckets of variable resolution
+ std::map<int, int> buckets;
+ for (size_t i = 1; i < samples.size(); ++i) {
+ ++buckets[deltaMs(samples[i - 1], samples[i])];
+ }
+ return buckets;
}
static int widthOf(int x) {
@@ -58,76 +71,164 @@
return width;
}
+// Takes a single buffer period timestamp entry with author information and stores it
+// in a temporary series of timestamps. Once the series is full, the data is analyzed,
+// stored, and emptied.
+// TODO: decide whether author or file location information is more important to store
+// for now, only stores author (thread)
+void PerformanceAnalysis::logTsEntry(int author, int64_t ts) {
+ // TODO might want to filter excessively high outliers, which are usually caused
+ // by the thread being inactive.
+ // Store time series data for each reader in order to bucket it once there
+ // is enough data. Then, write to recentHists as a histogram.
+ mTimeStampSeries[author].push_back(ts);
+ // if length of the time series has reached kShortHistSize samples, do 1) and 2):
+ if (mTimeStampSeries[author].size() >= kShortHistSize) {
+ // 1) analyze the series to store all outliers and their exact timestamps:
+ storeOutlierData(mTimeStampSeries[author]);
+ // 2) detect peaks in the outlier series
+ detectPeaks();
+ // 3) compute its histogram, append this to mRecentHists and erase the time series
+ // FIXME: need to store the timestamp of the beginning of each histogram
+ // FIXME: Restore LOG_HIST_FLUSH to separate histograms at every end-of-stream event
+ // A histogram should not span data between audio off/on timespans
+ mRecentHists.emplace_back(author,
+ buildBuckets(mTimeStampSeries[author]));
+ // do not let mRecentHists exceed capacity
+ // ALOGD("mRecentHists size: %d", static_cast<int>(mRecentHists.size()));
+ if (mRecentHists.size() >= kRecentHistsCapacity) {
+ // ALOGD("popped back mRecentHists");
+ mRecentHists.pop_front();
+ }
+ mTimeStampSeries[author].clear();
+ }
+}
+
+// Given a series of outlier intervals (mOutlier data),
+// looks for changes in distribution (peaks), which can be either positive or negative.
+// The function sets the mean to the starting value and sigma to 0, and updates
+// them as long as no peak is detected. When a value is more than 'threshold'
+// standard deviations from the mean, a peak is detected and the mean and sigma
+// are set to the peak value and 0.
+void PerformanceAnalysis::detectPeaks() {
+ if (mOutlierData.empty()) {
+ ALOGD("peak detector called on empty array");
+ return;
+ }
+
+ // compute mean of the distribution. Used to check whether a value is large
+ const double kTypicalDiff = std::accumulate(
+ mOutlierData.begin(), mOutlierData.end(), 0,
+ [](auto &a, auto &b){return a + b.first;}) / mOutlierData.size();
+ // ALOGD("typicalDiff %f", kTypicalDiff);
+
+ // iterator at the beginning of a sequence, or updated to the most recent peak
+ std::deque<std::pair<uint64_t, uint64_t>>::iterator start = mOutlierData.begin();
+ // the mean and standard deviation are updated every time a peak is detected
+ // initialize first time. The mean from the previous sequence is stored
+ // for the next sequence. Here, they are initialized for the first time.
+ if (mPeakDetectorMean < 0) {
+ mPeakDetectorMean = static_cast<double>(start->first);
+ mPeakDetectorSd = 0;
+ }
+ auto sqr = [](auto x){ return x * x; };
+ for (auto it = mOutlierData.begin(); it != mOutlierData.end(); ++it) {
+ // no surprise occurred:
+ // the new element is a small number of standard deviations from the mean
+ if ((fabs(it->first - mPeakDetectorMean) < kStddevThreshold * mPeakDetectorSd) ||
+ // or: right after peak has been detected, the delta is smaller than average
+ (mPeakDetectorSd == 0 && fabs(it->first - mPeakDetectorMean) < kTypicalDiff)) {
+ // update the mean and sd:
+ // count number of elements (distance between start interator and current)
+ const int kN = std::distance(start, it) + 1;
+ // usual formulas for mean and sd
+ mPeakDetectorMean = std::accumulate(start, it + 1, 0.0,
+ [](auto &a, auto &b){return a + b.first;}) / kN;
+ mPeakDetectorSd = sqrt(std::accumulate(start, it + 1, 0.0,
+ [=](auto &a, auto &b){ return a + sqr(b.first - mPeakDetectorMean);})) /
+ ((kN > 1)? kN - 1 : kN); // kN - 1: mean is correlated with variance
+ // ALOGD("value, mean, sd: %f, %f, %f", static_cast<double>(it->first), mean, sd);
+ }
+ // surprising value: store peak timestamp and reset mean, sd, and start iterator
+ else {
+ mPeakTimestamps.emplace_back(it->second);
+ // TODO: remove pop_front once a circular buffer is in place
+ if (mPeakTimestamps.size() >= kShortHistSize) {
+ ALOGD("popped back mPeakTimestamps");
+ mPeakTimestamps.pop_front();
+ }
+ mPeakDetectorMean = static_cast<double>(it->first);
+ mPeakDetectorSd = 0;
+ start = it;
+ }
+ }
+ //for (const auto &it : mPeakTimestamps) {
+ // ALOGE("mPeakTimestamps %f", static_cast<double>(it));
+ //}
+ return;
+}
+
+// Called by LogTsEntry. The input is a vector of timestamps.
+// Finds outliers and writes to mOutlierdata.
+// Each value in mOutlierdata consists of: <outlier timestamp, time elapsed since previous outlier>.
+// e.g. timestamps (ms) 1, 4, 5, 16, 18, 28 will produce pairs (4, 5), (13, 18).
+// This function is applied to the time series before it is converted into a histogram.
+void PerformanceAnalysis::storeOutlierData(const std::vector<int64_t> ×tamps) {
+ if (timestamps.size() < 1) {
+ ALOGE("storeOutlierData called on empty vector");
+ return;
+ }
+ // first pass: need to initialize
+ if (mElapsed == 0) {
+ mPrevNs = timestamps[0];
+ }
+ for (const auto &ts: timestamps) {
+ const uint64_t diffMs = static_cast<uint64_t>(deltaMs(mPrevNs, ts));
+ if (diffMs >= static_cast<uint64_t>(kOutlierMs)) {
+ mOutlierData.emplace_back(mElapsed, static_cast<uint64_t>(mPrevNs));
+ // Remove oldest value if the vector is full
+ // TODO: remove pop_front once circular buffer is in place
+ // FIXME: change kShortHistSize to some other constant. Make sure it is large
+ // enough that data will never be lost before being written to a long-term FIFO
+ if (mOutlierData.size() >= kShortHistSize) {
+ ALOGD("popped back mOutlierData");
+ mOutlierData.pop_front();
+ }
+ mElapsed = 0;
+ }
+ mElapsed += diffMs;
+ mPrevNs = ts;
+ }
+}
+
+
// FIXME: delete this temporary test code, recycled for various new functions
void PerformanceAnalysis::testFunction() {
// produces values (4: 5000000), (13: 18000000)
// ns timestamps of buffer periods
const std::vector<int64_t>kTempTestData = {1000000, 4000000, 5000000,
16000000, 18000000, 28000000};
- const int kTestAuthor = 1;
- PerformanceAnalysis::storeOutlierData(kTestAuthor, kTempTestData);
+ PerformanceAnalysis::storeOutlierData(kTempTestData);
for (const auto &outlier: mOutlierData) {
ALOGE("PerformanceAnalysis test %lld: %lld",
static_cast<long long>(outlier.first), static_cast<long long>(outlier.second));
}
+ detectPeaks();
}
-// Each pair consists of: <outlier timestamp, time elapsed since previous outlier>.
-// The timestamp of the beginning of the outlier is recorded.
-// The elapsed time is from the timestamp of the previous outlier
-// e.g. timestamps (ms) 1, 4, 5, 16, 18, 28 will produce pairs (4, 5), (13, 18).
-// This function is applied to the time series before it is converted into a histogram.
-void PerformanceAnalysis::storeOutlierData(
- int author, const std::vector<int64_t> ×tamps) {
- if (timestamps.size() < 1) {
- ALOGE("storeOutlierData called on empty vector");
- return;
- }
- author++; // temp to avoid unused error until this value is
- // either TODO: used or discarded from the arglist
- author--;
- uint64_t elapsed = 0;
- int64_t prev = timestamps.at(0);
- for (const auto &ts: timestamps) {
- const uint64_t diff = static_cast<uint64_t>(deltaMs(prev, ts));
- if (diff >= static_cast<uint64_t>(kOutlierMs)) {
- mOutlierData.emplace_back(elapsed, static_cast<uint64_t>(prev));
- elapsed = 0;
- }
- elapsed += diff;
- prev = ts;
- }
- // ALOGE("storeOutlierData: result length %zu", outlierData.size());
- // for (const auto &outlier: OutlierData) {
- // ALOGE("PerformanceAnalysis test %lld: %lld",
- // static_cast<long long>(outlier.first), static_cast<long long>(outlier.second));
- //}
-}
-
-// TODO: implement peak detector
-/*
- static void peakDetector() {
- return;
- } */
-
-// TODO put this function in separate file. Make it return a std::string instead of modifying body
-// TODO create a subclass of Reader for this and related work
+// TODO Make it return a std::string instead of modifying body --> is this still relevant?
// FIXME: as can be seen when printing the values, the outlier timestamps typically occur
// in the first histogram 35 to 38 indices from the end (most often 35).
-// TODO: build histogram buckets earlier and discard timestamps to save memory
// TODO consider changing all ints to uint32_t or uint64_t
-void PerformanceAnalysis::reportPerformance(String8 *body,
- const std::deque<std::pair
- <int, short_histogram>> &shortHists,
- int maxHeight) {
- if (shortHists.size() < 1) {
+void PerformanceAnalysis::reportPerformance(String8 *body, int maxHeight) {
+ if (mRecentHists.size() < 1) {
+ ALOGD("reportPerformance: mRecentHists is empty");
return;
}
- // this is temporary code, which only prints out one histogram
- // of all data stored in buffer. The data is not erased, only overwritten.
+ ALOGD("reportPerformance: hists size %d", static_cast<int>(mRecentHists.size()));
// TODO: more elaborate data analysis
std::map<int, int> buckets;
- for (const auto &shortHist: shortHists) {
+ for (const auto &shortHist: mRecentHists) {
for (const auto &countPair : shortHist.second) {
buckets[countPair.first] += countPair.second;
}
@@ -222,14 +323,4 @@
return;
}
-bool PerformanceAnalysis::isFindGlitch() const
-{
- return findGlitch;
-}
-
-void PerformanceAnalysis::setFindGlitch(bool s)
-{
- findGlitch = s;
-}
-
} // namespace android