From 1f16af01f4cfba0472805a620bcdf3d325acb0d8 Mon Sep 17 00:00:00 2001 From: Pierre Testart Date: Tue, 17 Jan 2023 14:09:06 +0100 Subject: cmGlobalNinjaGenerator: Optimize target depends closure Rewrite AppendTargetDependsClosure method to only cache local target outputs, not including outputs from dependencies. Caching all recursive target outputs causes much time to be spent merging sets that have many elements in common (from targets that are included through multiple dependency paths). It is faster to always iterate over all dependencies instead. --- Source/cmGlobalNinjaGenerator.cxx | 116 ++++++++++++++++++++++---------------- Source/cmGlobalNinjaGenerator.h | 8 +-- 2 files changed, 68 insertions(+), 56 deletions(-) diff --git a/Source/cmGlobalNinjaGenerator.cxx b/Source/cmGlobalNinjaGenerator.cxx index c24b1e3..a1eadb9 100644 --- a/Source/cmGlobalNinjaGenerator.cxx +++ b/Source/cmGlobalNinjaGenerator.cxx @@ -8,6 +8,7 @@ #include #include #include +#include #include #include @@ -584,7 +585,7 @@ void cmGlobalNinjaGenerator::Generate() } for (auto& it : this->Configs) { - it.second.TargetDependsClosures.clear(); + it.second.TargetDependsClosureLocalOutputs.clear(); } this->InitOutputPathPrefix(); @@ -1360,70 +1361,85 @@ void cmGlobalNinjaGenerator::AppendTargetDependsClosure( cmGeneratorTarget const* target, cmNinjaDeps& outputs, const std::string& config, const std::string& fileConfig, bool genexOutput) { - cmNinjaOuts outs; - this->AppendTargetDependsClosure(target, outs, config, fileConfig, - genexOutput, true); - cm::append(outputs, outs); -} + struct Entry + { + Entry(cmGeneratorTarget const* target_, std::string config_, + std::string fileConfig_) + : target(target_) + , config(std::move(config_)) + , fileConfig(std::move(fileConfig_)) + { + } -void cmGlobalNinjaGenerator::AppendTargetDependsClosure( - cmGeneratorTarget const* target, cmNinjaOuts& outputs, - const std::string& config, const std::string& fileConfig, bool genexOutput, - bool omit_self) -{ + bool operator<(Entry const& other) const + { + return std::tie(target, config, fileConfig) < + std::tie(other.target, other.config, other.fileConfig); + } - // try to locate the target in the cache - ByConfig::TargetDependsClosureKey key{ - target, - config, - genexOutput, + cmGeneratorTarget const* target; + std::string config; + std::string fileConfig; }; - auto find = this->Configs[fileConfig].TargetDependsClosures.lower_bound(key); - - if (find == this->Configs[fileConfig].TargetDependsClosures.end() || - find->first != key) { - // We now calculate the closure outputs by inspecting the dependent - // targets recursively. - // For that we have to distinguish between a local result set that is only - // relevant for filling the cache entries properly isolated and a global - // result set that is relevant for the result of the top level call to - // AppendTargetDependsClosure. - cmNinjaOuts this_outs; // this will be the new cache entry - - for (auto const& dep_target : this->GetTargetDirectDepends(target)) { + + cmNinjaOuts outputSet; + std::vector stack; + stack.emplace_back(target, config, fileConfig); + std::set seen = { stack.back() }; + + do { + Entry entry = std::move(stack.back()); + stack.pop_back(); + + // generate the outputs of the target itself, if applicable + if (entry.target != target) { + // try to locate the target in the cache + ByConfig::TargetDependsClosureKey localCacheKey{ + entry.target, + entry.config, + genexOutput, + }; + auto& configs = this->Configs[entry.fileConfig]; + auto lb = + configs.TargetDependsClosureLocalOutputs.lower_bound(localCacheKey); + + if (lb == configs.TargetDependsClosureLocalOutputs.end() || + lb->first != localCacheKey) { + cmNinjaDeps outs; + this->AppendTargetOutputs(entry.target, outs, entry.config, + DependOnTargetArtifact); + configs.TargetDependsClosureLocalOutputs.emplace_hint( + lb, localCacheKey, outs); + for (auto& value : outs) { + outputSet.emplace(std::move(value)); + } + } else { + outputSet.insert(lb->second.begin(), lb->second.end()); + } + } + + // push next dependencies + for (const auto& dep_target : this->GetTargetDirectDepends(entry.target)) { if (!dep_target->IsInBuildSystem()) { continue; } - if (!this->IsSingleConfigUtility(target) && + if (!this->IsSingleConfigUtility(entry.target) && !this->IsSingleConfigUtility(dep_target) && this->EnableCrossConfigBuild() && !dep_target.IsCross() && !genexOutput) { continue; } - if (dep_target.IsCross()) { - this->AppendTargetDependsClosure(dep_target, this_outs, fileConfig, - fileConfig, genexOutput, false); - } else { - this->AppendTargetDependsClosure(dep_target, this_outs, config, - fileConfig, genexOutput, false); + auto emplaceRes = seen.emplace( + dep_target, dep_target.IsCross() ? entry.fileConfig : entry.config, + entry.fileConfig); + if (emplaceRes.second) { + stack.emplace_back(*emplaceRes.first); } } - find = this->Configs[fileConfig].TargetDependsClosures.emplace_hint( - find, key, std::move(this_outs)); - } - - // now fill the outputs of the final result from the newly generated cache - // entry - outputs.insert(find->second.begin(), find->second.end()); - - // finally generate the outputs of the target itself, if applicable - cmNinjaDeps outs; - if (!omit_self) { - this->AppendTargetOutputs(target, outs, config, DependOnTargetArtifact); - } - outputs.insert(outs.begin(), outs.end()); + } while (!stack.empty()); + cm::append(outputs, outputSet); } void cmGlobalNinjaGenerator::AddTargetAlias(const std::string& alias, diff --git a/Source/cmGlobalNinjaGenerator.h b/Source/cmGlobalNinjaGenerator.h index 775e792..2b6d1cd 100644 --- a/Source/cmGlobalNinjaGenerator.h +++ b/Source/cmGlobalNinjaGenerator.h @@ -354,11 +354,6 @@ public: const std::string& config, const std::string& fileConfig, bool genexOutput); - void AppendTargetDependsClosure(cmGeneratorTarget const* target, - cmNinjaOuts& outputs, - const std::string& config, - const std::string& fileConfig, - bool genexOutput, bool omit_self); void AppendDirectoryForConfig(const std::string& prefix, const std::string& config, @@ -615,7 +610,8 @@ private: bool GenexOutput; }; - std::map TargetDependsClosures; + std::map + TargetDependsClosureLocalOutputs; TargetAliasMap TargetAliases; -- cgit v0.12