Merge topic 'ninja-performance'

7374cb85 Ninja: Cache ConvertToNinjaPath results to avoid repeat work
ed19e813 Ninja: Improve performance with deeply-dependent custom targets

Acked-by: Kitware Robot <kwrobot@kitware.com>
Merge-request: !1217

3 files changed, 59 insertions, 32 deletions

diff --git a/Source/cmGlobalNinjaGenerator.cxx b/Source/cmGlobalNinjaGenerator.cxx
index eee63c9..3e9e995 100644
--- a/Source/cmGlobalNinjaGenerator.cxx
+++ b/Source/cmGlobalNinjaGenerator.cxx
@@ -861,18 +861,24 @@ static void EnsureTrailingSlash(std::string& path)
 #endif
 }
 
-std::string cmGlobalNinjaGenerator::ConvertToNinjaPath(
+std::string const& cmGlobalNinjaGenerator::ConvertToNinjaPath(
   const std::string& path) const
 {
+  auto const f = ConvertToNinjaPathCache.find(path);
+  if (f != ConvertToNinjaPathCache.end()) {
+    return f->second;
+  }
+
   cmLocalNinjaGenerator* ng =
     static_cast<cmLocalNinjaGenerator*>(this->LocalGenerators[0]);
-  std::string convPath = ng->ConvertToRelativePath(
-    this->LocalGenerators[0]->GetState()->GetBinaryDirectory(), path);
+  const char* bin_dir = ng->GetState()->GetBinaryDirectory();
+  std::string convPath = ng->ConvertToRelativePath(bin_dir, path);
   convPath = this->NinjaOutputPath(convPath);
 #ifdef _WIN32
   std::replace(convPath.begin(), convPath.end(), '/', '\\');
 #endif
-  return convPath;
+  return ConvertToNinjaPathCache.emplace(path, std::move(convPath))
+    .first->second;
 }
 
 void cmGlobalNinjaGenerator::AddCXXCompileCommand(
@@ -1037,35 +1043,51 @@ void cmGlobalNinjaGenerator::AppendTargetDepends(
 void cmGlobalNinjaGenerator::AppendTargetDependsClosure(
   cmGeneratorTarget const* target, cmNinjaDeps& outputs)
 {
-  TargetDependsClosureMap::iterator i =
-    this->TargetDependsClosures.find(target);
-  if (i == this->TargetDependsClosures.end()) {
-    TargetDependsClosureMap::value_type e(
-      target, std::set<cmGeneratorTarget const*>());
-    i = this->TargetDependsClosures.insert(e).first;
-    this->ComputeTargetDependsClosure(target, i->second);
-  }
-  std::set<cmGeneratorTarget const*> const& targets = i->second;
-  cmNinjaDeps outs;
-  for (auto tgt : targets) {
-    this->AppendTargetOutputs(tgt, outs);
-  }
-  std::sort(outs.begin(), outs.end());
+  cmNinjaOuts outs;
+  this->AppendTargetDependsClosure(target, outs, true);
+
   outputs.insert(outputs.end(), outs.begin(), outs.end());
 }
 
-void cmGlobalNinjaGenerator::ComputeTargetDependsClosure(
-  cmGeneratorTarget const* target, std::set<cmGeneratorTarget const*>& depends)
+void cmGlobalNinjaGenerator::AppendTargetDependsClosure(
+  cmGeneratorTarget const* target, cmNinjaOuts& outputs, bool omit_self)
 {
-  cmTargetDependSet const& targetDeps = this->GetTargetDirectDepends(target);
-  for (auto targetDep : targetDeps) {
-    if (targetDep->GetType() == cmStateEnums::INTERFACE_LIBRARY) {
-      continue;
-    }
-    if (depends.insert(targetDep).second) {
-      this->ComputeTargetDependsClosure(targetDep, depends);
+
+  // try to locate the target in the cache
+  auto find = this->TargetDependsClosures.lower_bound(target);
+
+  if (find == this->TargetDependsClosures.end() || find->first != target) {
+    // 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.
+    auto const& targetDeps = this->GetTargetDirectDepends(target);
+    cmNinjaOuts this_outs; // this will be the new cache entry
+
+    for (auto const& dep_target : targetDeps) {
+      if (dep_target->GetType() == cmStateEnums::INTERFACE_LIBRARY) {
+        continue;
+      }
+
+      // Collect the dependent targets for _this_ target
+      this->AppendTargetDependsClosure(dep_target, this_outs, false);
     }
+    find = this->TargetDependsClosures.emplace_hint(find, target,
+                                                    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);
   }
+  outputs.insert(outs.begin(), outs.end());
 }
 
 void cmGlobalNinjaGenerator::AddTargetAlias(const std::string& alias,
diff --git a/Source/cmGlobalNinjaGenerator.h b/Source/cmGlobalNinjaGenerator.h
index f556ce1..7f80d08 100644
--- a/Source/cmGlobalNinjaGenerator.h
+++ b/Source/cmGlobalNinjaGenerator.h
@@ -9,6 +9,7 @@
 #include <map>
 #include <set>
 #include <string>
+#include <unordered_map>
 #include <utility>
 #include <vector>
 
@@ -245,7 +246,7 @@ public:
     return this->RulesFileStream;
   }
 
-  std::string ConvertToNinjaPath(const std::string& path) const;
+  std::string const& ConvertToNinjaPath(const std::string& path) const;
 
   struct MapToNinjaPathImpl
   {
@@ -320,6 +321,8 @@ public:
     cmNinjaTargetDepends depends = DependOnTargetArtifact);
   void AppendTargetDependsClosure(cmGeneratorTarget const* target,
                                   cmNinjaDeps& outputs);
+  void AppendTargetDependsClosure(cmGeneratorTarget const* target,
+                                  cmNinjaOuts& outputs, bool omit_self);
   void AddDependencyToAll(cmGeneratorTarget* target);
   void AddDependencyToAll(const std::string& input);
 
@@ -448,10 +451,10 @@ private:
   typedef std::map<std::string, cmGeneratorTarget*> TargetAliasMap;
   TargetAliasMap TargetAliases;
 
-  typedef std::map<cmGeneratorTarget const*,
-                   std::set<cmGeneratorTarget const*>>
-    TargetDependsClosureMap;
-  TargetDependsClosureMap TargetDependsClosures;
+  std::map<cmGeneratorTarget const*, cmNinjaOuts> TargetDependsClosures;
+
+  /// the local cache for calls to ConvertToNinjaPath
+  mutable std::unordered_map<std::string, std::string> ConvertToNinjaPathCache;
 
   std::string NinjaCommand;
   std::string NinjaVersion;
diff --git a/Source/cmNinjaTypes.h b/Source/cmNinjaTypes.h
index ec435d9..9e962f1 100644
--- a/Source/cmNinjaTypes.h
+++ b/Source/cmNinjaTypes.h
@@ -6,6 +6,7 @@
 #include "cmConfigure.h" // IWYU pragma: keep
 
 #include <map>
+#include <set>
 #include <string>
 #include <vector>
 
@@ -16,6 +17,7 @@ enum cmNinjaTargetDepends
 };
 
 typedef std::vector<std::string> cmNinjaDeps;
+typedef std::set<std::string> cmNinjaOuts;
 typedef std::map<std::string, std::string> cmNinjaVars;
 
 #endif // ! cmNinjaTypes_h