services/surfaceflinger/CompositionEngine/src/planner/Predictor.cpp - third_party/android/platform/frameworks/native - Git at Google

 /*
  * Copyright 2021 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.
  */

 // #define LOG_NDEBUG 0

 #undef LOG_TAG
 #define LOG_TAG "Planner"

 #include <compositionengine/impl/planner/Predictor.h>

 namespace android::compositionengine::impl::planner {

 std::optional<LayerStack::ApproximateMatch> LayerStack::getApproximateMatch(
         const std::vector<const LayerState*>& other) const {
     // Differing numbers of layers are never an approximate match
     if (mLayers.size() != other.size()) {
         return std::nullopt;
     }

     std::optional<ApproximateMatch> approximateMatch = {};
     for (size_t i = 0; i < mLayers.size(); ++i) {
         // Skip identical layers
         if (mLayers[i].getHash() == other[i]->getHash()) {
             continue;
         }

         // Skip layers where both are client-composited, since that doesn't change the
         // composition plan
         if (mLayers[i].getCompositionType() == hal::Composition::CLIENT &&
             other[i]->getCompositionType() == hal::Composition::CLIENT) {
             continue;
         }

         // If layers differ in composition type, their stacks are too different
         if (mLayers[i].getCompositionType() != other[i]->getCompositionType()) {
             return std::nullopt;
         }

         // If layers are not identical, but we already detected a prior approximate match for a
         // previous layer, the LayerStacks differ by too much, so return nothing
         if (approximateMatch) {
             return std::nullopt;
         }

         Flags<LayerStateField> differingFields = mLayers[i].getDifferingFields(*other[i]);

         // If we don't find an approximate match on this layer, then the LayerStacks differ
         // by too much, so return nothing
         const int differingFieldCount = __builtin_popcount(differingFields.get());
         if (differingFieldCount <= kMaxDifferingFields) {
             approximateMatch = ApproximateMatch{
                     .differingIndex = i,
                     .differingFields = differingFields,
             };
         } else {
             return std::nullopt;
         }
     }

     if (approximateMatch) {
         return approximateMatch;
     }

     // If we make it through the layer-by-layer comparison without an approximate match,
     // it means that all layers were either identical or had client-composited layers in common,
     // which don't affect the composition strategy, so return a successful result with
     // no differences.
     return ApproximateMatch{
             .differingIndex = 0,
             .differingFields = {},
     };
 }

 std::optional<Plan> Plan::fromString(const std::string& string) {
     Plan plan;
     for (char c : string) {
         switch (c) {
             case 'C':
                 plan.addLayerType(hal::Composition::CLIENT);
                 continue;
             case 'U':
                 plan.addLayerType(hal::Composition::CURSOR);
                 continue;
             case 'D':
                 plan.addLayerType(hal::Composition::DEVICE);
                 continue;
             case 'I':
                 plan.addLayerType(hal::Composition::INVALID);
                 continue;
             case 'B':
                 plan.addLayerType(hal::Composition::SIDEBAND);
                 continue;
             case 'S':
                 plan.addLayerType(hal::Composition::SOLID_COLOR);
                 continue;
             default:
                 return std::nullopt;
         }
     }
     return plan;
 }

 std::string to_string(const Plan& plan) {
     std::string result;
     for (auto type : plan.mLayerTypes) {
         switch (type) {
             case hal::Composition::CLIENT:
                 result.append("C");
                 break;
             case hal::Composition::CURSOR:
                 result.append("U");
                 break;
             case hal::Composition::DEVICE:
                 result.append("D");
                 break;
             case hal::Composition::INVALID:
                 result.append("I");
                 break;
             case hal::Composition::SIDEBAND:
                 result.append("B");
                 break;
             case hal::Composition::SOLID_COLOR:
                 result.append("S");
                 break;
         }
     }
     return result;
 }

 void Prediction::dump(std::string& result) const {
     result.append(to_string(mPlan));
     result.append(" [Exact ");
     mExactStats.dump(result);
     result.append("] [Approximate ");
     mApproximateStats.dump(result);
     result.append("]");
 }

 std::optional<Predictor::PredictedPlan> Predictor::getPredictedPlan(
         const std::vector<const LayerState*>& layers, NonBufferHash hash) const {
     // First check for an exact match
     if (std::optional<Plan> exactMatch = getExactMatch(hash); exactMatch) {
         ALOGV("[%s] Found an exact match for %zx", __func__, hash);
         return PredictedPlan{.hash = hash, .plan = *exactMatch, .type = Prediction::Type::Exact};
     }

     // If only a hash was passed in for a layer stack with a cached set, don't perform
     // approximate matches and return early
     if (layers.empty()) {
         ALOGV("[%s] Only hash was passed, but no exact match was found", __func__);
         return std::nullopt;
     }

     // Then check for approximate matches
     if (std::optional<NonBufferHash> approximateMatch = getApproximateMatch(layers);
         approximateMatch) {
         ALOGV("[%s] Found an approximate match for %zx", __func__, *approximateMatch);
         const Prediction& prediction = getPrediction(*approximateMatch);
         return PredictedPlan{.hash = *approximateMatch,
                              .plan = prediction.getPlan(),
                              .type = Prediction::Type::Approximate};
     }

     return std::nullopt;
 }

 void Predictor::recordResult(std::optional<PredictedPlan> predictedPlan,
                              NonBufferHash flattenedHash,
                              const std::vector<const LayerState*>& layers, bool hasSkippedLayers,
                              Plan result) {
     if (predictedPlan) {
         recordPredictedResult(*predictedPlan, layers, std::move(result));
         return;
     }

     ++mMissCount;

     if (!hasSkippedLayers && findSimilarPrediction(layers, result)) {
         return;
     }

     ALOGV("[%s] Adding novel candidate %zx", __func__, flattenedHash);
     mCandidates.emplace_front(flattenedHash, Prediction(layers, result));
     if (mCandidates.size() > MAX_CANDIDATES) {
         mCandidates.pop_back();
     }
 }

 void Predictor::dump(std::string& result) const {
     result.append("Predictor state:\n");

     const size_t hitCount = mExactHitCount + mApproximateHitCount;
     const size_t totalAttempts = hitCount + mMissCount;
     base::StringAppendF(&result, "Global non-skipped hit rate: %.2f%% (%zd/%zd)\n",
                         100.0f * hitCount / totalAttempts, hitCount, totalAttempts);
     base::StringAppendF(&result, "  Exact hits: %zd\n", mExactHitCount);
     base::StringAppendF(&result, "  Approximate hits: %zd\n", mApproximateHitCount);
     base::StringAppendF(&result, "  Misses: %zd\n\n", mMissCount);

     dumpPredictionsByFrequency(result);
 }

 void Predictor::compareLayerStacks(NonBufferHash leftHash, NonBufferHash rightHash,
                                    std::string& result) const {
     const auto& [leftPredictionEntry, rightPredictionEntry] =
             std::make_tuple(mPredictions.find(leftHash), mPredictions.find(rightHash));
     if (leftPredictionEntry == mPredictions.end()) {
         base::StringAppendF(&result, "No prediction found for %zx\n", leftHash);
         return;
     }
     if (rightPredictionEntry == mPredictions.end()) {
         base::StringAppendF(&result, "No prediction found for %zx\n", rightHash);
         return;
     }

     base::StringAppendF(&result,
                         "Comparing           %-16zx                                %-16zx\n",
                         leftHash, rightHash);

     const auto& [leftPrediction, rightPrediction] =
             std::make_tuple(leftPredictionEntry->second, rightPredictionEntry->second);
     const auto& [leftStack, rightStack] = std::make_tuple(leftPrediction.getExampleLayerStack(),
                                                           rightPrediction.getExampleLayerStack());
     leftStack.compare(rightStack, result);
 }

 void Predictor::describeLayerStack(NonBufferHash hash, std::string& result) const {
     base::StringAppendF(&result, "Describing %zx:\n\n", hash);

     if (const auto predictionsEntry = mPredictions.find(hash);
         predictionsEntry != mPredictions.cend()) {
         const auto& [hash, prediction] = *predictionsEntry;

         prediction.getExampleLayerStack().dump(result);

         result.append("Prediction: ");
         prediction.dump(result);
         result.append("\n");
     } else {
         result.append("No predictions found\n");
     }
 }

 void Predictor::listSimilarStacks(Plan plan, std::string& result) const {
     base::StringAppendF(&result, "Similar stacks for plan %s:\n", to_string(plan).c_str());

     if (const auto similarStacksEntry = mSimilarStacks.find(plan);
         similarStacksEntry != mSimilarStacks.end()) {
         const auto& [_, similarStacks] = *similarStacksEntry;
         for (NonBufferHash hash : similarStacks) {
             base::StringAppendF(&result, "\nPrediction hash %zx:\n", hash);
             const Prediction& prediction = mPredictions.at(hash);
             prediction.getExampleLayerStack().dumpLayerNames(result);
         }
     } else {
         result.append("No similar stacks found\n");
     }
 }

 const Prediction& Predictor::getPrediction(NonBufferHash hash) const {
     if (const auto predictionEntry = mPredictions.find(hash);
         predictionEntry != mPredictions.end()) {
         const auto& [_, prediction] = *predictionEntry;
         return prediction;
     } else {
         const auto candidateEntry = getCandidateEntryByHash(hash);
         ALOGE_IF(candidateEntry == mCandidates.cend(),
                  "Hash should have been found in either predictions or candidates");
         const auto& [_, prediction] = *candidateEntry;
         return prediction;
     }
 }

 Prediction& Predictor::getPrediction(NonBufferHash hash) {
     return const_cast<Prediction&>(const_cast<const Predictor*>(this)->getPrediction(hash));
 }

 std::optional<Plan> Predictor::getExactMatch(NonBufferHash hash) const {
     const Prediction* match = nullptr;
     if (const auto predictionEntry = mPredictions.find(hash);
         predictionEntry != mPredictions.end()) {
         const auto& [hash, prediction] = *predictionEntry;
         match = &prediction;
     } else if (const auto candidateEntry = getCandidateEntryByHash(hash);
                candidateEntry != mCandidates.cend()) {
         match = &(candidateEntry->prediction);
     }

     if (match == nullptr) {
         return std::nullopt;
     }

     if (match->getMissCount(Prediction::Type::Exact) != 0) {
         ALOGV("[%s] Skipping exact match for %zx because of prior miss", __func__, hash);
         return std::nullopt;
     }

     return match->getPlan();
 }

 std::optional<NonBufferHash> Predictor::getApproximateMatch(
         const std::vector<const LayerState*>& layers) const {
     const auto approximateStackMatches = [&](const ApproximateStack& approximateStack) {
         const auto& exampleStack = mPredictions.at(approximateStack.hash).getExampleLayerStack();
         if (const auto approximateMatchOpt = exampleStack.getApproximateMatch(layers);
             approximateMatchOpt) {
             return *approximateMatchOpt == approximateStack.match;
         }
         return false;
     };

     const auto candidateMatches = [&](const PromotionCandidate& candidate) {
         ALOGV("[getApproximateMatch] checking against %zx", candidate.hash);
         return candidate.prediction.getExampleLayerStack().getApproximateMatch(layers) !=
                 std::nullopt;
     };

     const Prediction* match = nullptr;
     NonBufferHash hash;
     if (const auto approximateStackIter =
                 std::find_if(mApproximateStacks.cbegin(), mApproximateStacks.cend(),
                              approximateStackMatches);
         approximateStackIter != mApproximateStacks.cend()) {
         match = &mPredictions.at(approximateStackIter->hash);
         hash = approximateStackIter->hash;
     } else if (const auto candidateEntry =
                        std::find_if(mCandidates.cbegin(), mCandidates.cend(), candidateMatches);
                candidateEntry != mCandidates.cend()) {
         match = &(candidateEntry->prediction);
         hash = candidateEntry->hash;
     }

     if (match == nullptr) {
         return std::nullopt;
     }

     if (match->getMissCount(Prediction::Type::Approximate) != 0) {
         ALOGV("[%s] Skipping approximate match for %zx because of prior miss", __func__, hash);
         return std::nullopt;
     }

     return hash;
 }

 void Predictor::promoteIfCandidate(NonBufferHash predictionHash) {
     // Return if the candidate has already been promoted
     if (mPredictions.count(predictionHash) != 0) {
         return;
     }

     ALOGV("[%s] Promoting %zx from candidate to prediction", __func__, predictionHash);

     auto candidateEntry = getCandidateEntryByHash(predictionHash);
     ALOGE_IF(candidateEntry == mCandidates.end(), "Expected to find candidate");

     mSimilarStacks[candidateEntry->prediction.getPlan()].push_back(predictionHash);
     mPredictions.emplace(predictionHash, std::move(candidateEntry->prediction));
     mCandidates.erase(candidateEntry);
 }

 void Predictor::recordPredictedResult(PredictedPlan predictedPlan,
                                       const std::vector<const LayerState*>& layers, Plan result) {
     Prediction& prediction = getPrediction(predictedPlan.hash);
     if (prediction.getPlan() != result) {
         ALOGV("[%s] %s prediction missed, expected %s, found %s", __func__,
               to_string(predictedPlan.type).c_str(), to_string(prediction.getPlan()).c_str(),
               to_string(result).c_str());
         prediction.recordMiss(predictedPlan.type);
         ++mMissCount;
         return;
     }

     switch (predictedPlan.type) {
         case Prediction::Type::Approximate:
             ++mApproximateHitCount;
             break;
         case Prediction::Type::Exact:
             ++mExactHitCount;
             break;
         default:
             break;
     }

     ALOGV("[%s] %s prediction hit", __func__, to_string(predictedPlan.type).c_str());
     ALOGV("[%s] Plan: %s", __func__, to_string(result).c_str());
     prediction.recordHit(predictedPlan.type);

     const auto stackMatchesHash = [hash = predictedPlan.hash](const ApproximateStack& stack) {
         return stack.hash == hash;
     };

     if (predictedPlan.type == Prediction::Type::Approximate) {
         // If this approximate match is not already in the list of approximate stacks, add it
         if (std::find_if(mApproximateStacks.cbegin(), mApproximateStacks.cend(),
                          stackMatchesHash) == mApproximateStacks.cend()) {
             ALOGV("[%s] Adding approximate match to list", __func__);
             const auto approximateMatchOpt =
                     prediction.getExampleLayerStack().getApproximateMatch(layers);
             ALOGE_IF(!approximateMatchOpt, "Expected an approximate match");
             mApproximateStacks.emplace_back(predictedPlan.hash, *approximateMatchOpt);
         }
     }

     promoteIfCandidate(predictedPlan.hash);
 }

 bool Predictor::findSimilarPrediction(const std::vector<const LayerState*>& layers, Plan result) {
     const auto stacksEntry = mSimilarStacks.find(result);
     if (stacksEntry == mSimilarStacks.end()) {
         return false;
     }

     std::optional<ApproximateStack> bestMatch;
     const auto& [plan, similarStacks] = *stacksEntry;
     for (NonBufferHash hash : similarStacks) {
         const Prediction& prediction = mPredictions.at(hash);
         auto approximateMatch = prediction.getExampleLayerStack().getApproximateMatch(layers);
         if (!approximateMatch) {
             continue;
         }

         const int differingFieldCount = __builtin_popcount(approximateMatch->differingFields.get());
         if (!bestMatch ||
             differingFieldCount < __builtin_popcount(bestMatch->match.differingFields.get())) {
             bestMatch = {hash, *approximateMatch};
         }
     }

     if (!bestMatch) {
         return false;
     }

     ALOGV("[%s] Adding %zx to approximate stacks", __func__, bestMatch->hash);

     mApproximateStacks.emplace_back(*bestMatch);
     return true;
 }

 void Predictor::dumpPredictionsByFrequency(std::string& result) const {
     struct HashFrequency {
         HashFrequency(NonBufferHash hash, size_t totalAttempts)
               : hash(hash), totalAttempts(totalAttempts) {}

         NonBufferHash hash;
         size_t totalAttempts;
     };

     std::vector<HashFrequency> hashFrequencies;
     for (const auto& [hash, prediction] : mPredictions) {
         hashFrequencies.emplace_back(hash,
                                      prediction.getHitCount(Prediction::Type::Total) +
                                              prediction.getMissCount(Prediction::Type::Total));
     }

     std::sort(hashFrequencies.begin(), hashFrequencies.end(),
               [](const HashFrequency& lhs, const HashFrequency& rhs) {
                   return lhs.totalAttempts > rhs.totalAttempts;
               });

     result.append("Predictions:\n");
     for (const auto& [hash, totalAttempts] : hashFrequencies) {
         base::StringAppendF(&result, "  %016zx ", hash);
         mPredictions.at(hash).dump(result);
         result.append("\n");
     }
 }

 } // namespace android::compositionengine::impl::planner
	/*
	* Copyright 2021 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.
	*/

	// #define LOG_NDEBUG 0

	#undef LOG_TAG
	#define LOG_TAG "Planner"

	#include <compositionengine/impl/planner/Predictor.h>

	namespace android::compositionengine::impl::planner {

	std::optional<LayerStack::ApproximateMatch> LayerStack::getApproximateMatch(
	const std::vector<const LayerState*>& other) const {
	// Differing numbers of layers are never an approximate match
	if (mLayers.size() != other.size()) {
	return std::nullopt;
	}

	std::optional<ApproximateMatch> approximateMatch = {};
	for (size_t i = 0; i < mLayers.size(); ++i) {
	// Skip identical layers
	if (mLayers[i].getHash() == other[i]->getHash()) {
	continue;
	}

	// Skip layers where both are client-composited, since that doesn't change the
	// composition plan
	if (mLayers[i].getCompositionType() == hal::Composition::CLIENT &&
	other[i]->getCompositionType() == hal::Composition::CLIENT) {
	continue;
	}

	// If layers differ in composition type, their stacks are too different
	if (mLayers[i].getCompositionType() != other[i]->getCompositionType()) {
	return std::nullopt;
	}

	// If layers are not identical, but we already detected a prior approximate match for a
	// previous layer, the LayerStacks differ by too much, so return nothing
	if (approximateMatch) {
	return std::nullopt;
	}

	Flags<LayerStateField> differingFields = mLayers[i].getDifferingFields(*other[i]);

	// If we don't find an approximate match on this layer, then the LayerStacks differ
	// by too much, so return nothing
	const int differingFieldCount = __builtin_popcount(differingFields.get());
	if (differingFieldCount <= kMaxDifferingFields) {
	approximateMatch = ApproximateMatch{
	.differingIndex = i,
	.differingFields = differingFields,
	};
	} else {
	return std::nullopt;
	}
	}

	if (approximateMatch) {
	return approximateMatch;
	}

	// If we make it through the layer-by-layer comparison without an approximate match,
	// it means that all layers were either identical or had client-composited layers in common,
	// which don't affect the composition strategy, so return a successful result with
	// no differences.
	return ApproximateMatch{
	.differingIndex = 0,
	.differingFields = {},
	};
	}

	std::optional<Plan> Plan::fromString(const std::string& string) {
	Plan plan;
	for (char c : string) {
	switch (c) {
	case 'C':
	plan.addLayerType(hal::Composition::CLIENT);
	continue;
	case 'U':
	plan.addLayerType(hal::Composition::CURSOR);
	continue;
	case 'D':
	plan.addLayerType(hal::Composition::DEVICE);
	continue;
	case 'I':
	plan.addLayerType(hal::Composition::INVALID);
	continue;
	case 'B':
	plan.addLayerType(hal::Composition::SIDEBAND);
	continue;
	case 'S':
	plan.addLayerType(hal::Composition::SOLID_COLOR);
	continue;
	default:
	return std::nullopt;
	}
	}
	return plan;
	}

	std::string to_string(const Plan& plan) {
	std::string result;
	for (auto type : plan.mLayerTypes) {
	switch (type) {
	case hal::Composition::CLIENT:
	result.append("C");
	break;
	case hal::Composition::CURSOR:
	result.append("U");
	break;
	case hal::Composition::DEVICE:
	result.append("D");
	break;
	case hal::Composition::INVALID:
	result.append("I");
	break;
	case hal::Composition::SIDEBAND:
	result.append("B");
	break;
	case hal::Composition::SOLID_COLOR:
	result.append("S");
	break;
	}
	}
	return result;
	}

	void Prediction::dump(std::string& result) const {
	result.append(to_string(mPlan));
	result.append(" [Exact ");
	mExactStats.dump(result);
	result.append("] [Approximate ");
	mApproximateStats.dump(result);
	result.append("]");
	}

	std::optional<Predictor::PredictedPlan> Predictor::getPredictedPlan(
	const std::vector<const LayerState*>& layers, NonBufferHash hash) const {
	// First check for an exact match
	if (std::optional<Plan> exactMatch = getExactMatch(hash); exactMatch) {
	ALOGV("[%s] Found an exact match for %zx", __func__, hash);
	return PredictedPlan{.hash = hash, .plan = *exactMatch, .type = Prediction::Type::Exact};
	}

	// If only a hash was passed in for a layer stack with a cached set, don't perform
	// approximate matches and return early
	if (layers.empty()) {
	ALOGV("[%s] Only hash was passed, but no exact match was found", __func__);
	return std::nullopt;
	}

	// Then check for approximate matches
	if (std::optional<NonBufferHash> approximateMatch = getApproximateMatch(layers);
	approximateMatch) {
	ALOGV("[%s] Found an approximate match for %zx", __func__, *approximateMatch);
	const Prediction& prediction = getPrediction(*approximateMatch);
	return PredictedPlan{.hash = *approximateMatch,
	.plan = prediction.getPlan(),
	.type = Prediction::Type::Approximate};
	}

	return std::nullopt;
	}

	void Predictor::recordResult(std::optional<PredictedPlan> predictedPlan,
	NonBufferHash flattenedHash,
	const std::vector<const LayerState*>& layers, bool hasSkippedLayers,
	Plan result) {
	if (predictedPlan) {
	recordPredictedResult(*predictedPlan, layers, std::move(result));
	return;
	}

	++mMissCount;

	if (!hasSkippedLayers && findSimilarPrediction(layers, result)) {
	return;
	}

	ALOGV("[%s] Adding novel candidate %zx", __func__, flattenedHash);
	mCandidates.emplace_front(flattenedHash, Prediction(layers, result));
	if (mCandidates.size() > MAX_CANDIDATES) {
	mCandidates.pop_back();
	}
	}

	void Predictor::dump(std::string& result) const {
	result.append("Predictor state:\n");

	const size_t hitCount = mExactHitCount + mApproximateHitCount;
	const size_t totalAttempts = hitCount + mMissCount;
	base::StringAppendF(&result, "Global non-skipped hit rate: %.2f%% (%zd/%zd)\n",
	100.0f * hitCount / totalAttempts, hitCount, totalAttempts);
	base::StringAppendF(&result, " Exact hits: %zd\n", mExactHitCount);
	base::StringAppendF(&result, " Approximate hits: %zd\n", mApproximateHitCount);
	base::StringAppendF(&result, " Misses: %zd\n\n", mMissCount);

	dumpPredictionsByFrequency(result);
	}

	void Predictor::compareLayerStacks(NonBufferHash leftHash, NonBufferHash rightHash,
	std::string& result) const {
	const auto& [leftPredictionEntry, rightPredictionEntry] =
	std::make_tuple(mPredictions.find(leftHash), mPredictions.find(rightHash));
	if (leftPredictionEntry == mPredictions.end()) {
	base::StringAppendF(&result, "No prediction found for %zx\n", leftHash);
	return;
	}
	if (rightPredictionEntry == mPredictions.end()) {
	base::StringAppendF(&result, "No prediction found for %zx\n", rightHash);
	return;
	}

	base::StringAppendF(&result,
	"Comparing %-16zx %-16zx\n",
	leftHash, rightHash);

	const auto& [leftPrediction, rightPrediction] =
	std::make_tuple(leftPredictionEntry->second, rightPredictionEntry->second);
	const auto& [leftStack, rightStack] = std::make_tuple(leftPrediction.getExampleLayerStack(),
	rightPrediction.getExampleLayerStack());
	leftStack.compare(rightStack, result);
	}

	void Predictor::describeLayerStack(NonBufferHash hash, std::string& result) const {
	base::StringAppendF(&result, "Describing %zx:\n\n", hash);

	if (const auto predictionsEntry = mPredictions.find(hash);
	predictionsEntry != mPredictions.cend()) {
	const auto& [hash, prediction] = *predictionsEntry;

	prediction.getExampleLayerStack().dump(result);

	result.append("Prediction: ");
	prediction.dump(result);
	result.append("\n");
	} else {
	result.append("No predictions found\n");
	}
	}

	void Predictor::listSimilarStacks(Plan plan, std::string& result) const {
	base::StringAppendF(&result, "Similar stacks for plan %s:\n", to_string(plan).c_str());

	if (const auto similarStacksEntry = mSimilarStacks.find(plan);
	similarStacksEntry != mSimilarStacks.end()) {
	const auto& [_, similarStacks] = *similarStacksEntry;
	for (NonBufferHash hash : similarStacks) {
	base::StringAppendF(&result, "\nPrediction hash %zx:\n", hash);
	const Prediction& prediction = mPredictions.at(hash);
	prediction.getExampleLayerStack().dumpLayerNames(result);
	}
	} else {
	result.append("No similar stacks found\n");
	}
	}

	const Prediction& Predictor::getPrediction(NonBufferHash hash) const {
	if (const auto predictionEntry = mPredictions.find(hash);
	predictionEntry != mPredictions.end()) {
	const auto& [_, prediction] = *predictionEntry;
	return prediction;
	} else {
	const auto candidateEntry = getCandidateEntryByHash(hash);
	ALOGE_IF(candidateEntry == mCandidates.cend(),
	"Hash should have been found in either predictions or candidates");
	const auto& [_, prediction] = *candidateEntry;
	return prediction;
	}
	}

	Prediction& Predictor::getPrediction(NonBufferHash hash) {
	return const_cast<Prediction&>(const_cast<const Predictor*>(this)->getPrediction(hash));
	}

	std::optional<Plan> Predictor::getExactMatch(NonBufferHash hash) const {
	const Prediction* match = nullptr;
	if (const auto predictionEntry = mPredictions.find(hash);
	predictionEntry != mPredictions.end()) {
	const auto& [hash, prediction] = *predictionEntry;
	match = &prediction;
	} else if (const auto candidateEntry = getCandidateEntryByHash(hash);
	candidateEntry != mCandidates.cend()) {
	match = &(candidateEntry->prediction);
	}

	if (match == nullptr) {
	return std::nullopt;
	}

	if (match->getMissCount(Prediction::Type::Exact) != 0) {
	ALOGV("[%s] Skipping exact match for %zx because of prior miss", __func__, hash);
	return std::nullopt;
	}

	return match->getPlan();
	}

	std::optional<NonBufferHash> Predictor::getApproximateMatch(
	const std::vector<const LayerState*>& layers) const {
	const auto approximateStackMatches = [&](const ApproximateStack& approximateStack) {
	const auto& exampleStack = mPredictions.at(approximateStack.hash).getExampleLayerStack();
	if (const auto approximateMatchOpt = exampleStack.getApproximateMatch(layers);
	approximateMatchOpt) {
	return *approximateMatchOpt == approximateStack.match;
	}
	return false;
	};

	const auto candidateMatches = [&](const PromotionCandidate& candidate) {
	ALOGV("[getApproximateMatch] checking against %zx", candidate.hash);
	return candidate.prediction.getExampleLayerStack().getApproximateMatch(layers) !=
	std::nullopt;
	};

	const Prediction* match = nullptr;
	NonBufferHash hash;
	if (const auto approximateStackIter =
	std::find_if(mApproximateStacks.cbegin(), mApproximateStacks.cend(),
	approximateStackMatches);
	approximateStackIter != mApproximateStacks.cend()) {
	match = &mPredictions.at(approximateStackIter->hash);
	hash = approximateStackIter->hash;
	} else if (const auto candidateEntry =
	std::find_if(mCandidates.cbegin(), mCandidates.cend(), candidateMatches);
	candidateEntry != mCandidates.cend()) {
	match = &(candidateEntry->prediction);
	hash = candidateEntry->hash;
	}

	if (match == nullptr) {
	return std::nullopt;
	}

	if (match->getMissCount(Prediction::Type::Approximate) != 0) {
	ALOGV("[%s] Skipping approximate match for %zx because of prior miss", __func__, hash);
	return std::nullopt;
	}

	return hash;
	}

	void Predictor::promoteIfCandidate(NonBufferHash predictionHash) {
	// Return if the candidate has already been promoted
	if (mPredictions.count(predictionHash) != 0) {
	return;
	}

	ALOGV("[%s] Promoting %zx from candidate to prediction", __func__, predictionHash);

	auto candidateEntry = getCandidateEntryByHash(predictionHash);
	ALOGE_IF(candidateEntry == mCandidates.end(), "Expected to find candidate");

	mSimilarStacks[candidateEntry->prediction.getPlan()].push_back(predictionHash);
	mPredictions.emplace(predictionHash, std::move(candidateEntry->prediction));
	mCandidates.erase(candidateEntry);
	}

	void Predictor::recordPredictedResult(PredictedPlan predictedPlan,
	const std::vector<const LayerState*>& layers, Plan result) {
	Prediction& prediction = getPrediction(predictedPlan.hash);
	if (prediction.getPlan() != result) {
	ALOGV("[%s] %s prediction missed, expected %s, found %s", __func__,
	to_string(predictedPlan.type).c_str(), to_string(prediction.getPlan()).c_str(),
	to_string(result).c_str());
	prediction.recordMiss(predictedPlan.type);
	++mMissCount;
	return;
	}

	switch (predictedPlan.type) {
	case Prediction::Type::Approximate:
	++mApproximateHitCount;
	break;
	case Prediction::Type::Exact:
	++mExactHitCount;
	break;
	default:
	break;
	}

	ALOGV("[%s] %s prediction hit", __func__, to_string(predictedPlan.type).c_str());
	ALOGV("[%s] Plan: %s", __func__, to_string(result).c_str());
	prediction.recordHit(predictedPlan.type);

	const auto stackMatchesHash = [hash = predictedPlan.hash](const ApproximateStack& stack) {
	return stack.hash == hash;
	};

	if (predictedPlan.type == Prediction::Type::Approximate) {
	// If this approximate match is not already in the list of approximate stacks, add it
	if (std::find_if(mApproximateStacks.cbegin(), mApproximateStacks.cend(),
	stackMatchesHash) == mApproximateStacks.cend()) {
	ALOGV("[%s] Adding approximate match to list", __func__);
	const auto approximateMatchOpt =
	prediction.getExampleLayerStack().getApproximateMatch(layers);
	ALOGE_IF(!approximateMatchOpt, "Expected an approximate match");
	mApproximateStacks.emplace_back(predictedPlan.hash, *approximateMatchOpt);
	}
	}

	promoteIfCandidate(predictedPlan.hash);
	}

	bool Predictor::findSimilarPrediction(const std::vector<const LayerState*>& layers, Plan result) {
	const auto stacksEntry = mSimilarStacks.find(result);
	if (stacksEntry == mSimilarStacks.end()) {
	return false;
	}

	std::optional<ApproximateStack> bestMatch;
	const auto& [plan, similarStacks] = *stacksEntry;
	for (NonBufferHash hash : similarStacks) {
	const Prediction& prediction = mPredictions.at(hash);
	auto approximateMatch = prediction.getExampleLayerStack().getApproximateMatch(layers);
	if (!approximateMatch) {
	continue;
	}

	const int differingFieldCount = __builtin_popcount(approximateMatch->differingFields.get());
	if (!bestMatch \|\|
	differingFieldCount < __builtin_popcount(bestMatch->match.differingFields.get())) {
	bestMatch = {hash, *approximateMatch};
	}
	}

	if (!bestMatch) {
	return false;
	}

	ALOGV("[%s] Adding %zx to approximate stacks", __func__, bestMatch->hash);

	mApproximateStacks.emplace_back(*bestMatch);
	return true;
	}

	void Predictor::dumpPredictionsByFrequency(std::string& result) const {
	struct HashFrequency {
	HashFrequency(NonBufferHash hash, size_t totalAttempts)
	: hash(hash), totalAttempts(totalAttempts) {}

	NonBufferHash hash;
	size_t totalAttempts;
	};

	std::vector<HashFrequency> hashFrequencies;
	for (const auto& [hash, prediction] : mPredictions) {
	hashFrequencies.emplace_back(hash,
	prediction.getHitCount(Prediction::Type::Total) +
	prediction.getMissCount(Prediction::Type::Total));
	}

	std::sort(hashFrequencies.begin(), hashFrequencies.end(),
	[](const HashFrequency& lhs, const HashFrequency& rhs) {
	return lhs.totalAttempts > rhs.totalAttempts;
	});

	result.append("Predictions:\n");
	for (const auto& [hash, totalAttempts] : hashFrequencies) {
	base::StringAppendF(&result, " %016zx ", hash);
	mPredictions.at(hash).dump(result);
	result.append("\n");
	}
	}

	} // namespace android::compositionengine::impl::planner