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.

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 <cstdio>
 #include <functional>
 #include <sstream>
+#include <tuple>
 #include <utility>
 
 #include <cm/iterator>
@@ -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<Entry> stack;
+  stack.emplace_back(target, config, fileConfig);
+  std::set<Entry> 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<TargetDependsClosureKey, cmNinjaOuts> TargetDependsClosures;
+    std::map<TargetDependsClosureKey, cmNinjaDeps>
+      TargetDependsClosureLocalOutputs;
 
     TargetAliasMap TargetAliases;