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/Android.bp b/services/surfaceflinger/Android.bp
index 1007b3d..fb2cb0f 100644
--- a/services/surfaceflinger/Android.bp
+++ b/services/surfaceflinger/Android.bp
@@ -143,6 +143,7 @@
"Scheduler/LayerHistory.cpp",
"Scheduler/MessageQueue.cpp",
"Scheduler/Scheduler.cpp",
+ "Scheduler/SchedulerUtils.cpp",
"StartPropertySetThread.cpp",
"SurfaceFlinger.cpp",
"SurfaceInterceptor.cpp",
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
diff --git a/services/surfaceflinger/tests/unittests/Android.bp b/services/surfaceflinger/tests/unittests/Android.bp
index 58f1e9c..28f3ef2 100644
--- a/services/surfaceflinger/tests/unittests/Android.bp
+++ b/services/surfaceflinger/tests/unittests/Android.bp
@@ -31,6 +31,7 @@
"EventThreadTest.cpp",
"LayerHistoryTest.cpp",
"SchedulerTest.cpp",
+ "SchedulerUtilsTest.cpp",
"mock/DisplayHardware/MockComposer.cpp",
"mock/DisplayHardware/MockDisplaySurface.cpp",
"mock/DisplayHardware/MockPowerAdvisor.cpp",
diff --git a/services/surfaceflinger/tests/unittests/SchedulerTest.cpp b/services/surfaceflinger/tests/unittests/SchedulerTest.cpp
index e967742..d0cf1b7 100644
--- a/services/surfaceflinger/tests/unittests/SchedulerTest.cpp
+++ b/services/surfaceflinger/tests/unittests/SchedulerTest.cpp
@@ -59,8 +59,6 @@
SchedulerTest();
~SchedulerTest() override;
- int64_t calculateMedian(std::vector<int64_t>* v);
-
sp<Scheduler::ConnectionHandle> mConnectionHandle;
mock::DispSync* mPrimaryDispSync = new mock::DispSync();
mock::EventThread* mEventThread;
@@ -97,10 +95,6 @@
ALOGD("**** Tearing down after %s.%s\n", test_info->test_case_name(), test_info->name());
}
-int64_t SchedulerTest::calculateMedian(std::vector<int64_t>* v) {
- return mScheduler->calculateMedian(v);
-}
-
namespace {
/* ------------------------------------------------------------------------
* Test cases
@@ -190,38 +184,5 @@
EXPECT_CALL(*mEventThread, setPhaseOffset(10)).Times(1);
ASSERT_NO_FATAL_FAILURE(mScheduler->setPhaseOffset(mConnectionHandle, 10));
}
-
-TEST_F(SchedulerTest, calculateMedian) {
- std::vector<int64_t> testVector;
- // Calling the function on empty vector returns 0.
- EXPECT_EQ(0, calculateMedian(&testVector));
-
- testVector.push_back(33);
- EXPECT_EQ(33, calculateMedian(&testVector));
- testVector.push_back(33);
- testVector.push_back(33);
- EXPECT_EQ(33, calculateMedian(&testVector));
- testVector.push_back(42);
- EXPECT_EQ(33, calculateMedian(&testVector));
- testVector.push_back(33);
- EXPECT_EQ(33, calculateMedian(&testVector));
- testVector.push_back(42);
- EXPECT_EQ(33, calculateMedian(&testVector));
- testVector.push_back(42);
- EXPECT_EQ(33, calculateMedian(&testVector));
- testVector.push_back(42);
- EXPECT_EQ(42, calculateMedian(&testVector));
- testVector.push_back(60);
- EXPECT_EQ(42, calculateMedian(&testVector));
- testVector.push_back(60);
- EXPECT_EQ(42, calculateMedian(&testVector));
- testVector.push_back(33);
- EXPECT_EQ(42, calculateMedian(&testVector));
- testVector.push_back(33);
- EXPECT_EQ(42, calculateMedian(&testVector));
- testVector.push_back(33);
- EXPECT_EQ(33, calculateMedian(&testVector));
-}
-
} // namespace
} // namespace android
diff --git a/services/surfaceflinger/tests/unittests/SchedulerUtilsTest.cpp b/services/surfaceflinger/tests/unittests/SchedulerUtilsTest.cpp
new file mode 100644
index 0000000..5865579
--- /dev/null
+++ b/services/surfaceflinger/tests/unittests/SchedulerUtilsTest.cpp
@@ -0,0 +1,131 @@
+/*
+ * 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.
+ */
+
+#undef LOG_TAG
+#define LOG_TAG "SchedulerUnittests"
+
+#include <gmock/gmock.h>
+#include <gtest/gtest.h>
+
+#include <array>
+
+#include "Scheduler/SchedulerUtils.h"
+
+namespace android {
+namespace scheduler {
+
+class SchedulerUtilsTest : public testing::Test {
+public:
+ SchedulerUtilsTest() = default;
+ ~SchedulerUtilsTest() override = default;
+};
+
+namespace {
+TEST_F(SchedulerUtilsTest, calculate_mean) {
+ std::array<int64_t, 30> testArray{};
+ // Calling the function on empty array returns 0.
+ EXPECT_EQ(0, calculate_mean(testArray));
+
+ testArray[0] = 33;
+ EXPECT_EQ(1, calculate_mean(testArray));
+ testArray[1] = 33;
+ testArray[2] = 33;
+ EXPECT_EQ(3, calculate_mean(testArray));
+ testArray[3] = 42;
+ EXPECT_EQ(4, calculate_mean(testArray));
+ testArray[4] = 33;
+ EXPECT_EQ(5, calculate_mean(testArray));
+ testArray[5] = 42;
+ EXPECT_EQ(7, calculate_mean(testArray));
+ for (int i = 6; i < 30; i++) {
+ testArray[i] = 33;
+ }
+ EXPECT_EQ(33, calculate_mean(testArray));
+}
+
+TEST_F(SchedulerUtilsTest, calculate_median) {
+ std::vector<int64_t> testVector;
+ // Calling the function on empty vector returns 0.
+ EXPECT_EQ(0, calculate_median(&testVector));
+
+ testVector.push_back(33);
+ EXPECT_EQ(33, calculate_median(&testVector));
+ testVector.push_back(33);
+ testVector.push_back(33);
+ EXPECT_EQ(33, calculate_median(&testVector));
+ testVector.push_back(42);
+ EXPECT_EQ(33, calculate_median(&testVector));
+ testVector.push_back(33);
+ EXPECT_EQ(33, calculate_median(&testVector));
+ testVector.push_back(42);
+ EXPECT_EQ(33, calculate_median(&testVector));
+ testVector.push_back(42);
+ EXPECT_EQ(33, calculate_median(&testVector));
+ testVector.push_back(42);
+ EXPECT_EQ(42, calculate_median(&testVector));
+ testVector.push_back(60);
+ EXPECT_EQ(42, calculate_median(&testVector));
+ testVector.push_back(60);
+ EXPECT_EQ(42, calculate_median(&testVector));
+ testVector.push_back(33);
+ EXPECT_EQ(42, calculate_median(&testVector));
+ testVector.push_back(33);
+ EXPECT_EQ(42, calculate_median(&testVector));
+ testVector.push_back(33);
+ EXPECT_EQ(33, calculate_median(&testVector));
+}
+
+TEST_F(SchedulerUtilsTest, calculate_mode) {
+ std::vector<int64_t> testVector;
+ // Calling the function on empty vector returns 0.
+ EXPECT_EQ(0, calculate_mode(testVector));
+
+ testVector.push_back(33);
+ EXPECT_EQ(33, calculate_mode(testVector));
+ testVector.push_back(33);
+ testVector.push_back(33);
+ EXPECT_EQ(33, calculate_mode(testVector));
+ testVector.push_back(42);
+ EXPECT_EQ(33, calculate_mode(testVector));
+ testVector.push_back(33);
+ EXPECT_EQ(33, calculate_mode(testVector));
+ testVector.push_back(42);
+ EXPECT_EQ(33, calculate_mode(testVector));
+ testVector.push_back(42);
+ EXPECT_EQ(33, calculate_mode(testVector));
+ testVector.push_back(42);
+ EXPECT_EQ(33, calculate_mode(testVector));
+ testVector.push_back(60);
+ EXPECT_EQ(33, calculate_mode(testVector));
+ testVector.push_back(60);
+ EXPECT_EQ(33, calculate_mode(testVector));
+ testVector.push_back(33);
+ // 5 occurences of 33.
+ EXPECT_EQ(33, calculate_mode(testVector));
+ testVector.push_back(42);
+ // 5 occurences of 33, 5 occurences of 42. We choose the first one.
+ EXPECT_EQ(33, calculate_mode(testVector));
+ testVector.push_back(42);
+ // 5 occurences of 33, 6 occurences of 42.
+ EXPECT_EQ(42, calculate_mode(testVector));
+ testVector.push_back(42);
+ // 5 occurences of 33, 7 occurences of 42.
+ EXPECT_EQ(42, calculate_mode(testVector));
+}
+
+} // namespace
+} // namespace scheduler
+} // namespace android
\ No newline at end of file