SF: Adding statistical mode
- Adding statistical mode for timestamp intervals.
- Moving math calculations into util class, and adding a unit test.
See go/surface-flinger-scheduler for more info and systrace links.
Test: SF tests pass. Adding new test class.
Bug: 113612090
Change-Id: I3c3a73e3d8719e47326d8a48d27683037b7beb47
diff --git a/services/surfaceflinger/Scheduler/LayerHistory.cpp b/services/surfaceflinger/Scheduler/LayerHistory.cpp
index 1f47949..d5ccbe1 100644
--- a/services/surfaceflinger/Scheduler/LayerHistory.cpp
+++ b/services/surfaceflinger/Scheduler/LayerHistory.cpp
@@ -26,6 +26,8 @@
#include <utils/Timers.h>
#include <utils/Trace.h>
+#include "SchedulerUtils.h"
+
namespace android {
LayerHistory::LayerHistory() {}
@@ -38,7 +40,7 @@
void LayerHistory::incrementCounter() {
mCounter++;
- mCounter = mCounter % ARRAY_SIZE;
+ mCounter = mCounter % scheduler::ARRAY_SIZE;
// Clear all the previous data from the history. This is a ring buffer, so we are
// reusing memory.
mElements[mCounter].clear();
@@ -47,7 +49,8 @@
const std::unordered_map<std::string, nsecs_t>& LayerHistory::get(size_t index) const {
// For the purposes of the layer history, the index = 0 always needs to start at the
// current counter, and then decrement to access the layers in correct historical order.
- return mElements.at((ARRAY_SIZE + (mCounter - (index % ARRAY_SIZE))) % ARRAY_SIZE);
+ return mElements.at((scheduler::ARRAY_SIZE + (mCounter - (index % scheduler::ARRAY_SIZE))) %
+ scheduler::ARRAY_SIZE);
}
} // namespace android
\ No newline at end of file
diff --git a/services/surfaceflinger/Scheduler/LayerHistory.h b/services/surfaceflinger/Scheduler/LayerHistory.h
index 76c1352..c6fab07 100644
--- a/services/surfaceflinger/Scheduler/LayerHistory.h
+++ b/services/surfaceflinger/Scheduler/LayerHistory.h
@@ -25,6 +25,8 @@
#include <utils/Timers.h>
+#include "SchedulerUtils.h"
+
namespace android {
/*
@@ -52,12 +54,11 @@
const std::unordered_map<std::string, nsecs_t>& get(size_t index) const;
// Returns the total size of the ring buffer. The value is always the same regardless
// of how many slots we filled in.
- static constexpr size_t getSize() { return ARRAY_SIZE; }
+ static constexpr size_t getSize() { return scheduler::ARRAY_SIZE; }
private:
size_t mCounter = 0;
- static constexpr size_t ARRAY_SIZE = 30;
- std::array<std::unordered_map<std::string, nsecs_t>, ARRAY_SIZE> mElements;
+ std::array<std::unordered_map<std::string, nsecs_t>, scheduler::ARRAY_SIZE> mElements;
};
} // namespace android
\ No newline at end of file
diff --git a/services/surfaceflinger/Scheduler/Scheduler.cpp b/services/surfaceflinger/Scheduler/Scheduler.cpp
index 4d3ae33..4457f72 100644
--- a/services/surfaceflinger/Scheduler/Scheduler.cpp
+++ b/services/surfaceflinger/Scheduler/Scheduler.cpp
@@ -18,6 +18,7 @@
#include "Scheduler.h"
+#include <algorithm>
#include <cinttypes>
#include <cstdint>
#include <memory>
@@ -38,6 +39,7 @@
#include "EventControlThread.h"
#include "EventThread.h"
#include "InjectVSyncSource.h"
+#include "SchedulerUtils.h"
namespace android {
@@ -222,11 +224,6 @@
mLayerHistory.incrementCounter();
}
-nsecs_t Scheduler::calculateAverage() const {
- nsecs_t sum = std::accumulate(mTimeDifferences.begin(), mTimeDifferences.end(), 0);
- return (sum / ARRAY_SIZE);
-}
-
void Scheduler::updateFrameSkipping(const int64_t skipCount) {
ATRACE_INT("FrameSkipCount", skipCount);
if (mSkipCount != skipCount) {
@@ -243,6 +240,7 @@
// Traverse through the layer history, and determine the differences in present times.
nsecs_t newestPresentTime = framePresentTime;
+ std::string differencesText = "";
for (int i = 1; i < mLayerHistory.getSize(); i++) {
std::unordered_map<std::string, nsecs_t> layers = mLayerHistory.get(i);
for (auto layer : layers) {
@@ -250,39 +248,31 @@
continue;
}
int64_t differenceMs = (newestPresentTime - layer.second) / 1000000;
- ALOGD("%d Layer %s: %" PRId64, i, layerName.c_str(), differenceMs);
// Dismiss noise.
if (differenceMs > 10 && differenceMs < 60) {
differencesMs.push_back(differenceMs);
}
+ IF_ALOGV() { differencesText += (std::to_string(differenceMs) + " "); }
newestPresentTime = layer.second;
}
}
- // Average is a good indicator for when 24fps videos are playing, because the frames come in
- // 33, and 49 ms intervals with occasional 41ms.
- int64_t average =
- std::accumulate(differencesMs.begin(), differencesMs.end(), 0) / differencesMs.size();
- const auto tag = "TimestampAvg_" + layerName;
- ATRACE_INT(tag.c_str(), average);
+ ALOGV("Layer %s timestamp intervals: %s", layerName.c_str(), differencesText.c_str());
- // Mode and median are good indicators for 30 and 60 fps videos, because the majority of frames
- // come in 16, or 33 ms intervals.
- // TODO(b/113612090): Calculate mode. Median is good for now, since we want a given interval to
- // repeat at least ARRAY_SIZE/2 + 1 times.
- if (differencesMs.size() > 0) {
+ if (!differencesMs.empty()) {
+ // Mean/Average is a good indicator for when 24fps videos are playing, because the frames
+ // come in 33, and 49 ms intervals with occasional 41ms.
+ const int64_t meanMs = scheduler::calculate_mean(differencesMs);
+ const auto tagMean = "TimestampMean_" + layerName;
+ ATRACE_INT(tagMean.c_str(), meanMs);
+
+ // Mode and median are good indicators for 30 and 60 fps videos, because the majority of
+ // frames come in 16, or 33 ms intervals.
const auto tagMedian = "TimestampMedian_" + layerName;
- ATRACE_INT(tagMedian.c_str(), calculateMedian(&differencesMs));
- }
-}
+ ATRACE_INT(tagMedian.c_str(), scheduler::calculate_median(&differencesMs));
-int64_t Scheduler::calculateMedian(std::vector<int64_t>* v) {
- if (!v || v->size() == 0) {
- return 0;
+ const auto tagMode = "TimestampMode_" + layerName;
+ ATRACE_INT(tagMode.c_str(), scheduler::calculate_mode(differencesMs));
}
-
- size_t n = v->size() / 2;
- nth_element(v->begin(), v->begin() + n, v->end());
- return v->at(n);
}
void Scheduler::determineTimestampAverage(bool isAutoTimestamp, const nsecs_t framePresentTime) {
@@ -302,23 +292,21 @@
}
ATRACE_INT("TimestampDiff", differenceMs);
- mTimeDifferences[mCounter % ARRAY_SIZE] = differenceMs;
+ mTimeDifferences[mCounter % scheduler::ARRAY_SIZE] = differenceMs;
mCounter++;
- nsecs_t average = calculateAverage();
- ATRACE_INT("TimestampAverage", average);
+ int64_t mean = scheduler::calculate_mean(mTimeDifferences);
+ ATRACE_INT("AutoTimestampMean", mean);
// TODO(b/113612090): This are current numbers from trial and error while running videos
// from YouTube at 24, 30, and 60 fps.
- if (average > 14 && average < 18) {
+ if (mean > 14 && mean < 18) {
ATRACE_INT("FPS", 60);
- } else if (average > 31 && average < 34) {
+ } else if (mean > 31 && mean < 34) {
ATRACE_INT("FPS", 30);
- updateFrameSkipping(1);
return;
- } else if (average > 39 && average < 42) {
+ } else if (mean > 39 && mean < 42) {
ATRACE_INT("FPS", 24);
}
- updateFrameSkipping(0);
}
} // namespace android
diff --git a/services/surfaceflinger/Scheduler/Scheduler.h b/services/surfaceflinger/Scheduler/Scheduler.h
index adfc071..764ad00 100644
--- a/services/surfaceflinger/Scheduler/Scheduler.h
+++ b/services/surfaceflinger/Scheduler/Scheduler.h
@@ -27,6 +27,7 @@
#include "EventThread.h"
#include "InjectVSyncSource.h"
#include "LayerHistory.h"
+#include "SchedulerUtils.h"
namespace android {
@@ -111,8 +112,6 @@
void incrementFrameCounter();
protected:
- friend class SchedulerTest;
-
virtual std::unique_ptr<EventThread> makeEventThread(
const std::string& connectionName, DispSync* dispSync, int64_t phaseOffsetNs,
impl::EventThread::ResyncWithRateLimitCallback resyncCallback,
@@ -124,9 +123,6 @@
// Collects the statistical mean (average) and median between timestamp
// intervals for each frame for each layer.
void determineLayerTimestampStats(const std::string layerName, const nsecs_t framePresentTime);
- // Calculates the statistical median in the vector. Return 0 if the vector is empty. The
- // function modifies the vector contents.
- int64_t calculateMedian(std::vector<int64_t>* v);
// Collects the average difference between timestamps for each frame regardless
// of which layer the timestamp came from.
void determineTimestampAverage(bool isAutoTimestamp, const nsecs_t framePresentTime);
@@ -163,8 +159,7 @@
// simulate 30Hz rendering, we skip every other frame, and this variable is set
// to 1.
int64_t mSkipCount = 0;
- static constexpr size_t ARRAY_SIZE = 30;
- std::array<int64_t, ARRAY_SIZE> mTimeDifferences;
+ std::array<int64_t, scheduler::ARRAY_SIZE> mTimeDifferences{};
size_t mCounter = 0;
LayerHistory mLayerHistory;
diff --git a/services/surfaceflinger/Scheduler/SchedulerUtils.cpp b/services/surfaceflinger/Scheduler/SchedulerUtils.cpp
new file mode 100644
index 0000000..191022d
--- /dev/null
+++ b/services/surfaceflinger/Scheduler/SchedulerUtils.cpp
@@ -0,0 +1,56 @@
+/*
+ * Copyright 2018 The Android Open Source Project
+ *
+ * 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.
+ */
+
+#include "SchedulerUtils.h"
+
+#include <cinttypes>
+#include <numeric>
+#include <unordered_map>
+#include <vector>
+
+namespace android {
+namespace scheduler {
+
+int64_t calculate_median(std::vector<int64_t>* v) {
+ if (!v || v->empty()) {
+ return 0;
+ }
+
+ size_t n = v->size() / 2;
+ nth_element(v->begin(), v->begin() + n, v->end());
+ return v->at(n);
+}
+
+int64_t calculate_mode(const std::vector<int64_t>& v) {
+ if (v.empty()) {
+ return 0;
+ }
+
+ // Create a map with all the counts for the indivicual values in the vector.
+ std::unordered_map<int64_t, int64_t> counts;
+ for (int64_t value : v) {
+ counts[value]++;
+ }
+
+ // Sort the map, and return the number with the highest count. If two numbers have
+ // the same count, first one is returned.
+ using ValueType = const decltype(counts)::value_type&;
+ const auto compareCounts = [](ValueType l, ValueType r) { return l.second <= r.second; };
+ return std::max_element(counts.begin(), counts.end(), compareCounts)->first;
+}
+
+} // namespace scheduler
+} // namespace android
diff --git a/services/surfaceflinger/Scheduler/SchedulerUtils.h b/services/surfaceflinger/Scheduler/SchedulerUtils.h
new file mode 100644
index 0000000..17c57db
--- /dev/null
+++ b/services/surfaceflinger/Scheduler/SchedulerUtils.h
@@ -0,0 +1,46 @@
+/*
+ * Copyright 2018 The Android Open Source Project
+ *
+ * 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.
+ */
+
+#pragma once
+
+#include <cinttypes>
+#include <numeric>
+#include <vector>
+
+namespace android {
+namespace scheduler {
+// This number is used to set the size of the arrays in scheduler that hold information
+// about layers.
+static constexpr size_t ARRAY_SIZE = 30;
+
+// Calculates the statistical mean (average) in the data structure (array, vector). The
+// function does not modify the contents of the array.
+template <typename T>
+auto calculate_mean(const T& v) {
+ using V = typename T::value_type;
+ V sum = std::accumulate(v.begin(), v.end(), 0);
+ return sum / static_cast<V>(v.size());
+}
+
+// Calculates the statistical median in the vector. Return 0 if the vector is empty. The
+// function modifies the vector contents.
+int64_t calculate_median(std::vector<int64_t>* v);
+
+// Calculates the statistical mode in the vector. Return 0 if the vector is empty.
+int64_t calculate_mode(const std::vector<int64_t>& v);
+
+} // namespace scheduler
+} // namespace android
\ No newline at end of file