1 /* 2 * Copyright 2021 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #pragma once 18 19 #include <compositionengine/impl/planner/LayerState.h> 20 21 namespace android::compositionengine::impl::planner { 22 23 class LayerStack { 24 public: LayerStack(const std::vector<const LayerState * > & layers)25 LayerStack(const std::vector<const LayerState*>& layers) : mLayers(copyLayers(layers)) {} 26 27 // Describes an approximate match between two layer stacks 28 struct ApproximateMatch { 29 bool operator==(const ApproximateMatch& other) const { 30 return differingIndex == other.differingIndex && 31 differingFields == other.differingFields; 32 } 33 34 // The index of the single differing layer between the two stacks. 35 // This implies that only one layer is allowed to differ in an approximate match. 36 size_t differingIndex; 37 // Set of fields that differ for the differing layer in the approximate match. 38 Flags<LayerStateField> differingFields; 39 }; 40 41 // Returns an approximate match when comparing this layer stack with the provided list of 42 // layers, for the purposes of scoring how closely the two layer stacks will match composition 43 // strategies. 44 // 45 // If the two layer stacks are identical, then an approximate match is still returned, but the 46 // differing fields will be empty to represent an exact match. 47 // 48 // If the two layer stacks differ by too much, then an empty optional is returned. 49 std::optional<ApproximateMatch> getApproximateMatch( 50 const std::vector<const LayerState*>& other) const; 51 compare(const LayerStack & other,std::string & result)52 void compare(const LayerStack& other, std::string& result) const { 53 if (mLayers.size() != other.mLayers.size()) { 54 base::StringAppendF(&result, "Cannot compare stacks of different sizes (%zd vs. %zd)\n", 55 mLayers.size(), other.mLayers.size()); 56 return; 57 } 58 59 for (size_t l = 0; l < mLayers.size(); ++l) { 60 const auto& thisLayer = mLayers[l]; 61 const auto& otherLayer = other.mLayers[l]; 62 base::StringAppendF(&result, "\n+ - - - - - - - - - Layer %d [%s]\n", thisLayer.getId(), 63 thisLayer.getName().c_str()); 64 auto comparisonOpt = thisLayer.compare(otherLayer); 65 base::StringAppendF(&result, 66 " %s + - - - - - - - - - - - - - - - - - - - - - - - " 67 "- Layer %d [%s]\n", 68 comparisonOpt ? " " : "Identical", otherLayer.getId(), 69 otherLayer.getName().c_str()); 70 if (comparisonOpt) { 71 result.append(*comparisonOpt); 72 } 73 } 74 } 75 dump(std::string & result)76 void dump(std::string& result) const { 77 for (const LayerState& layer : mLayers) { 78 base::StringAppendF(&result, "+ - - - - - - - - - Layer %d [%s]\n", layer.getId(), 79 layer.getName().c_str()); 80 layer.dump(result); 81 } 82 } 83 84 void dumpLayerNames(std::string& result, const std::string& prefix = " ") const { 85 for (const LayerState& layer : mLayers) { 86 result.append(prefix); 87 result.append(layer.getName()); 88 result.append("\n"); 89 } 90 } 91 92 private: copyLayers(const std::vector<const LayerState * > & layers)93 std::vector<const LayerState> copyLayers(const std::vector<const LayerState*>& layers) { 94 std::vector<const LayerState> copiedLayers; 95 copiedLayers.reserve(layers.size()); 96 std::transform(layers.cbegin(), layers.cend(), std::back_inserter(copiedLayers), 97 [](const LayerState* layerState) { return *layerState; }); 98 return copiedLayers; 99 } 100 101 std::vector<const LayerState> mLayers; 102 103 // TODO(b/180976743): Tune kMaxDifferingFields 104 constexpr static int kMaxDifferingFields = 6; 105 }; 106 107 class Plan { 108 public: 109 static std::optional<Plan> fromString(const std::string&); 110 reset()111 void reset() { mLayerTypes.clear(); } addLayerType(hardware::graphics::composer::hal::Composition type)112 void addLayerType(hardware::graphics::composer::hal::Composition type) { 113 mLayerTypes.emplace_back(type); 114 } 115 116 friend std::string to_string(const Plan& plan); 117 118 friend bool operator==(const Plan& lhs, const Plan& rhs) { 119 return lhs.mLayerTypes == rhs.mLayerTypes; 120 } 121 friend bool operator!=(const Plan& lhs, const Plan& rhs) { return !(lhs == rhs); } 122 123 friend std::ostream& operator<<(std::ostream& os, const Plan& plan) { 124 return os << to_string(plan); 125 } 126 127 private: 128 std::vector<hardware::graphics::composer::hal::Composition> mLayerTypes; 129 }; 130 131 } // namespace android::compositionengine::impl::planner 132 133 namespace std { 134 template <> 135 struct hash<android::compositionengine::impl::planner::Plan> { 136 size_t operator()(const android::compositionengine::impl::planner::Plan& plan) const { 137 return std::hash<std::string>{}(to_string(plan)); 138 } 139 }; 140 } // namespace std 141 142 namespace android::compositionengine::impl::planner { 143 144 class Prediction { 145 public: 146 enum class Type { 147 Exact, 148 Approximate, 149 Total, 150 }; 151 152 friend std::string to_string(Type type) { 153 using namespace std::string_literals; 154 155 switch (type) { 156 case Type::Exact: 157 return "Exact"; 158 case Type::Approximate: 159 return "Approximate"; 160 case Type::Total: 161 return "Total"; 162 } 163 } 164 165 friend std::ostream& operator<<(std::ostream& os, const Type& type) { 166 return os << to_string(type); 167 } 168 169 Prediction(const std::vector<const LayerState*>& layers, Plan plan) 170 : mExampleLayerStack(layers), mPlan(std::move(plan)) {} 171 172 const LayerStack& getExampleLayerStack() const { return mExampleLayerStack; } 173 const Plan& getPlan() const { return mPlan; } 174 175 size_t getHitCount(Type type) const { 176 if (type == Type::Total) { 177 return getHitCount(Type::Exact) + getHitCount(Type::Approximate); 178 } 179 return getStatsForType(type).hitCount; 180 } 181 182 size_t getMissCount(Type type) const { 183 if (type == Type::Total) { 184 return getMissCount(Type::Exact) + getMissCount(Type::Approximate); 185 } 186 return getStatsForType(type).missCount; 187 } 188 189 void recordHit(Type type) { ++getStatsForType(type).hitCount; } 190 191 void recordMiss(Type type) { ++getStatsForType(type).missCount; } 192 193 void dump(std::string&) const; 194 195 private: 196 struct Stats { 197 void dump(std::string& result) const { 198 const size_t totalAttempts = hitCount + missCount; 199 base::StringAppendF(&result, "%.2f%% (%zd/%zd)", 100.0f * hitCount / totalAttempts, 200 hitCount, totalAttempts); 201 } 202 203 size_t hitCount = 0; 204 size_t missCount = 0; 205 }; 206 207 const Stats& getStatsForType(Type type) const { 208 return (type == Type::Exact) ? mExactStats : mApproximateStats; 209 } 210 211 Stats& getStatsForType(Type type) { 212 return const_cast<Stats&>(const_cast<const Prediction*>(this)->getStatsForType(type)); 213 } 214 215 LayerStack mExampleLayerStack; 216 Plan mPlan; 217 218 Stats mExactStats; 219 Stats mApproximateStats; 220 }; 221 222 class Predictor { 223 public: 224 struct PredictedPlan { 225 NonBufferHash hash; 226 Plan plan; 227 Prediction::Type type; 228 229 friend bool operator==(const PredictedPlan& lhs, const PredictedPlan& rhs) { 230 return lhs.hash == rhs.hash && lhs.plan == rhs.plan && lhs.type == rhs.type; 231 } 232 }; 233 234 // Retrieves the predicted plan based on a layer stack alongside its hash. 235 // 236 // If the exact layer stack has previously been seen by the predictor, then report the plan used 237 // for that layer stack. 238 // 239 // Otherwise, try to match to the best approximate stack to retireve the most likely plan. 240 std::optional<PredictedPlan> getPredictedPlan(const std::vector<const LayerState*>& layers, 241 NonBufferHash hash) const; 242 243 // Records a comparison between the predicted plan and the resulting plan, alongside the layer 244 // stack we used. 245 // 246 // This method is intended to help with scoring how effective the prediction engine is. 247 void recordResult(std::optional<PredictedPlan> predictedPlan, NonBufferHash flattenedHash, 248 const std::vector<const LayerState*>&, bool hasSkippedLayers, Plan result); 249 250 void dump(std::string&) const; 251 252 void compareLayerStacks(NonBufferHash leftHash, NonBufferHash rightHash, std::string&) const; 253 void describeLayerStack(NonBufferHash, std::string&) const; 254 void listSimilarStacks(Plan, std::string&) const; 255 256 private: 257 // Retrieves a prediction from either the main prediction list or from the candidate list 258 const Prediction& getPrediction(NonBufferHash) const; 259 Prediction& getPrediction(NonBufferHash); 260 261 std::optional<Plan> getExactMatch(NonBufferHash) const; 262 std::optional<NonBufferHash> getApproximateMatch( 263 const std::vector<const LayerState*>& layers) const; 264 265 void promoteIfCandidate(NonBufferHash); 266 void recordPredictedResult(PredictedPlan, const std::vector<const LayerState*>& layers, 267 Plan result); 268 bool findSimilarPrediction(const std::vector<const LayerState*>& layers, Plan result); 269 270 void dumpPredictionsByFrequency(std::string&) const; 271 272 struct PromotionCandidate { 273 PromotionCandidate(NonBufferHash hash, Prediction&& prediction) 274 : hash(hash), prediction(std::move(prediction)) {} 275 276 NonBufferHash hash; 277 Prediction prediction; 278 }; 279 280 static constexpr const size_t MAX_CANDIDATES = 4; 281 std::deque<PromotionCandidate> mCandidates; 282 decltype(mCandidates)::const_iterator getCandidateEntryByHash(NonBufferHash hash) const { 283 const auto candidateMatches = [&](const PromotionCandidate& candidate) { 284 return candidate.hash == hash; 285 }; 286 287 return std::find_if(mCandidates.cbegin(), mCandidates.cend(), candidateMatches); 288 } 289 290 std::unordered_map<NonBufferHash, Prediction> mPredictions; 291 std::unordered_map<Plan, std::vector<NonBufferHash>> mSimilarStacks; 292 293 struct ApproximateStack { 294 ApproximateStack(NonBufferHash hash, LayerStack::ApproximateMatch match) 295 : hash(hash), match(match) {} 296 297 bool operator==(const ApproximateStack& other) const { 298 return hash == other.hash && match == other.match; 299 } 300 301 NonBufferHash hash; 302 LayerStack::ApproximateMatch match; 303 }; 304 305 std::vector<ApproximateStack> mApproximateStacks; 306 307 mutable size_t mExactHitCount = 0; 308 mutable size_t mApproximateHitCount = 0; 309 mutable size_t mMissCount = 0; 310 }; 311 312 // Defining PrintTo helps with Google Tests. 313 inline void PrintTo(Predictor::PredictedPlan plan, ::std::ostream* os) { 314 *os << "PredictedPlan {"; 315 *os << "\n .hash = " << plan.hash; 316 *os << "\n .plan = " << plan.plan; 317 *os << "\n .type = " << plan.type; 318 *os << "\n}"; 319 } 320 321 } // namespace android::compositionengine::impl::planner 322