From 6cbf6a51976c9092f84ef4a90d35fb6fd60f5898 Mon Sep 17 00:00:00 2001
From: Brad King <brad.king@kitware.com>
Date: Mon, 8 Feb 2016 12:37:47 -0500
Subject: Fix internal target lookup performance regression
Refactoring in commit v3.5.0-rc1~272^2~13 (cmGlobalGenerator: Remove
direct storage of targets, 2015-10-25) replaced an efficient data
structure mapping from target name to cmTarget instance with a linear
search. Lookups through cmGlobalGenerator::FindTarget are done a lot.
Restore the efficient mapping structure with a name indicating its
purpose.
Reported-by: Bartosz Kosiorek <gang65@poczta.onet.pl>
---
Source/cmGlobalGenerator.cxx | 46 +++++++++++++-------------------------------
Source/cmGlobalGenerator.h | 18 ++++++++++++++++-
Source/cmMakefile.cxx | 2 ++
3 files changed, 32 insertions(+), 34 deletions(-)
diff --git a/Source/cmGlobalGenerator.cxx b/Source/cmGlobalGenerator.cxx
index d7bec44..65e7b12 100644
--- a/Source/cmGlobalGenerator.cxx
+++ b/Source/cmGlobalGenerator.cxx
@@ -1649,6 +1649,7 @@ void cmGlobalGenerator::ClearGeneratorMembers()
this->ExportSets.clear();
this->TargetDependencies.clear();
+ this->TargetSearchIndex.clear();
this->ProjectMap.clear();
this->RuleHashes.clear();
this->DirectoryContentMap.clear();
@@ -2177,18 +2178,20 @@ bool cmGlobalGenerator::IsAlias(const std::string& name) const
return this->AliasTargets.find(name) != this->AliasTargets.end();
}
+void cmGlobalGenerator::IndexTarget(cmTarget* t)
+{
+ if (!t->IsImported() || t->IsImportedGloballyVisible())
+ {
+ this->TargetSearchIndex[t->GetName()] = t;
+ }
+}
+
cmTarget* cmGlobalGenerator::FindTargetImpl(std::string const& name) const
{
- for (unsigned int i = 0; i < this->Makefiles.size(); ++i)
+ TargetMap::const_iterator i = this->TargetSearchIndex.find(name);
+ if (i != this->TargetSearchIndex.end())
{
- cmTargets& tgts = this->Makefiles[i]->GetTargets();
- for (cmTargets::iterator it = tgts.begin(); it != tgts.end(); ++it)
- {
- if (it->second.GetName() == name)
- {
- return &it->second;
- }
- }
+ return i->second;
}
return 0;
}
@@ -2212,25 +2215,6 @@ cmGlobalGenerator::FindGeneratorTargetImpl(std::string const& name) const
return 0;
}
-cmTarget*
-cmGlobalGenerator::FindImportedTargetImpl(std::string const& name) const
-{
- for (unsigned int i = 0; i < this->Makefiles.size(); ++i)
- {
- const std::vector<cmTarget*>& tgts =
- this->Makefiles[i]->GetOwnedImportedTargets();
- for (std::vector<cmTarget*>::const_iterator it = tgts.begin();
- it != tgts.end(); ++it)
- {
- if ((*it)->GetName() == name && (*it)->IsImportedGloballyVisible())
- {
- return *it;
- }
- }
- }
- return 0;
-}
-
cmGeneratorTarget* cmGlobalGenerator::FindImportedGeneratorTargetImpl(
std::string const& name) const
{
@@ -2264,11 +2248,7 @@ cmGlobalGenerator::FindTarget(const std::string& name,
return this->FindTargetImpl(ai->second);
}
}
- if (cmTarget* tgt = this->FindTargetImpl(name))
- {
- return tgt;
- }
- return this->FindImportedTargetImpl(name);
+ return this->FindTargetImpl(name);
}
cmGeneratorTarget*
diff --git a/Source/cmGlobalGenerator.h b/Source/cmGlobalGenerator.h
index bc6e17d..82bb35c 100644
--- a/Source/cmGlobalGenerator.h
+++ b/Source/cmGlobalGenerator.h
@@ -278,6 +278,8 @@ public:
std::set<std::string> const& GetDirectoryContent(std::string const& dir,
bool needDisk = true);
+ void IndexTarget(cmTarget* t);
+
static bool IsReservedTarget(std::string const& name);
virtual const char* GetAllTargetName() const { return "ALL_BUILD"; }
@@ -420,7 +422,6 @@ protected:
std::map<std::string, std::string> AliasTargets;
cmTarget* FindTargetImpl(std::string const& name) const;
- cmTarget* FindImportedTargetImpl(std::string const& name) const;
cmGeneratorTarget* FindGeneratorTargetImpl(std::string const& name) const;
cmGeneratorTarget*
@@ -430,6 +431,21 @@ protected:
virtual bool UseFolderProperty();
private:
+
+#if defined(CMAKE_BUILD_WITH_CMAKE)
+# ifdef CMake_HAVE_CXX11_UNORDERED_MAP
+ typedef std::unordered_map<std::string, cmTarget*> TargetMap;
+# else
+ typedef cmsys::hash_map<std::string, cmTarget*> TargetMap;
+# endif
+#else
+ typedef std::map<std::string,cmTarget *> TargetMap;
+#endif
+ // Map efficiently from target name to cmTarget instance.
+ // Do not use this structure for looping over all targets.
+ // It contains both normal and globally visible imported targets.
+ TargetMap TargetSearchIndex;
+
cmMakefile* TryCompileOuterMakefile;
// If you add a new map here, make sure it is copied
// in EnableLanguagesFromGenerator
diff --git a/Source/cmMakefile.cxx b/Source/cmMakefile.cxx
index cba29eb..950b247 100644
--- a/Source/cmMakefile.cxx
+++ b/Source/cmMakefile.cxx
@@ -2128,6 +2128,7 @@ cmMakefile::AddNewTarget(cmState::TargetType type, const std::string& name)
cmTarget& target = it->second;
target.SetType(type, name);
target.SetMakefile(this);
+ this->GetGlobalGenerator()->IndexTarget(&it->second);
return &it->second;
}
@@ -4218,6 +4219,7 @@ cmMakefile::AddImportedTarget(const std::string& name,
// Add to the set of available imported targets.
this->ImportedTargets[name] = target.get();
+ this->GetGlobalGenerator()->IndexTarget(target.get());
// Transfer ownership to this cmMakefile object.
this->ImportedTargetsOwned.push_back(target.get());
--
cgit v0.12
From 9b7d5871b86036da009119e14f54d161f2d44f24 Mon Sep 17 00:00:00 2001
From: Brad King <brad.king@kitware.com>
Date: Mon, 8 Feb 2016 12:50:56 -0500
Subject: Improve internal generator target structure lookup
In commit v3.5.0-rc1~272^2~6 (cmGlobalGenerator: Add FindGeneratorTarget
API, 2015-10-25) a lookup was implemented via linear search. Replace it
with an efficient data structure.
Suggested-by: Stephen Kelly <steveire@gmail.com>
---
Source/cmGlobalGenerator.cxx | 49 +++++++++++++-------------------------------
Source/cmGlobalGenerator.h | 6 ++++++
Source/cmLocalGenerator.cxx | 2 ++
3 files changed, 22 insertions(+), 35 deletions(-)
diff --git a/Source/cmGlobalGenerator.cxx b/Source/cmGlobalGenerator.cxx
index 65e7b12..fc8cf06 100644
--- a/Source/cmGlobalGenerator.cxx
+++ b/Source/cmGlobalGenerator.cxx
@@ -1650,6 +1650,7 @@ void cmGlobalGenerator::ClearGeneratorMembers()
this->ExportSets.clear();
this->TargetDependencies.clear();
this->TargetSearchIndex.clear();
+ this->GeneratorTargetSearchIndex.clear();
this->ProjectMap.clear();
this->RuleHashes.clear();
this->DirectoryContentMap.clear();
@@ -2186,6 +2187,14 @@ void cmGlobalGenerator::IndexTarget(cmTarget* t)
}
}
+void cmGlobalGenerator::IndexGeneratorTarget(cmGeneratorTarget* gt)
+{
+ if (!gt->IsImported() || gt->IsImportedGloballyVisible())
+ {
+ this->GeneratorTargetSearchIndex[gt->GetName()] = gt;
+ }
+}
+
cmTarget* cmGlobalGenerator::FindTargetImpl(std::string const& name) const
{
TargetMap::const_iterator i = this->TargetSearchIndex.find(name);
@@ -2199,37 +2208,11 @@ cmTarget* cmGlobalGenerator::FindTargetImpl(std::string const& name) const
cmGeneratorTarget*
cmGlobalGenerator::FindGeneratorTargetImpl(std::string const& name) const
{
- for (unsigned int i = 0; i < this->LocalGenerators.size(); ++i)
+ GeneratorTargetMap::const_iterator i =
+ this->GeneratorTargetSearchIndex.find(name);
+ if (i != this->GeneratorTargetSearchIndex.end())
{
- const std::vector<cmGeneratorTarget*>& tgts =
- this->LocalGenerators[i]->GetGeneratorTargets();
- for (std::vector<cmGeneratorTarget*>::const_iterator it = tgts.begin();
- it != tgts.end(); ++it)
- {
- if ((*it)->GetName() == name)
- {
- return *it;
- }
- }
- }
- return 0;
-}
-
-cmGeneratorTarget* cmGlobalGenerator::FindImportedGeneratorTargetImpl(
- std::string const& name) const
-{
- for (unsigned int i = 0; i < this->LocalGenerators.size(); ++i)
- {
- const std::vector<cmGeneratorTarget*>& tgts =
- this->LocalGenerators[i]->GetImportedGeneratorTargets();
- for (std::vector<cmGeneratorTarget*>::const_iterator it = tgts.begin();
- it != tgts.end(); ++it)
- {
- if ((*it)->IsImportedGloballyVisible() && (*it)->GetName() == name)
- {
- return *it;
- }
- }
+ return i->second;
}
return 0;
}
@@ -2260,11 +2243,7 @@ cmGlobalGenerator::FindGeneratorTarget(const std::string& name) const
{
return this->FindGeneratorTargetImpl(ai->second);
}
- if (cmGeneratorTarget* tgt = this->FindGeneratorTargetImpl(name))
- {
- return tgt;
- }
- return this->FindImportedGeneratorTargetImpl(name);
+ return this->FindGeneratorTargetImpl(name);
}
//----------------------------------------------------------------------------
diff --git a/Source/cmGlobalGenerator.h b/Source/cmGlobalGenerator.h
index 82bb35c..48fa704 100644
--- a/Source/cmGlobalGenerator.h
+++ b/Source/cmGlobalGenerator.h
@@ -279,6 +279,7 @@ public:
bool needDisk = true);
void IndexTarget(cmTarget* t);
+ void IndexGeneratorTarget(cmGeneratorTarget* gt);
static bool IsReservedTarget(std::string const& name);
@@ -435,16 +436,21 @@ private:
#if defined(CMAKE_BUILD_WITH_CMAKE)
# ifdef CMake_HAVE_CXX11_UNORDERED_MAP
typedef std::unordered_map<std::string, cmTarget*> TargetMap;
+ typedef std::unordered_map<std::string, cmGeneratorTarget*>
+ GeneratorTargetMap;
# else
typedef cmsys::hash_map<std::string, cmTarget*> TargetMap;
+ typedef cmsys::hash_map<std::string, cmGeneratorTarget*> GeneratorTargetMap;
# endif
#else
typedef std::map<std::string,cmTarget *> TargetMap;
+ typedef std::map<std::string,cmGeneratorTarget *> GeneratorTargetMap;
#endif
// Map efficiently from target name to cmTarget instance.
// Do not use this structure for looping over all targets.
// It contains both normal and globally visible imported targets.
TargetMap TargetSearchIndex;
+ GeneratorTargetMap GeneratorTargetSearchIndex;
cmMakefile* TryCompileOuterMakefile;
// If you add a new map here, make sure it is copied
diff --git a/Source/cmLocalGenerator.cxx b/Source/cmLocalGenerator.cxx
index 1d17032..912be0c 100644
--- a/Source/cmLocalGenerator.cxx
+++ b/Source/cmLocalGenerator.cxx
@@ -455,11 +455,13 @@ void cmLocalGenerator::GenerateInstallRules()
void cmLocalGenerator::AddGeneratorTarget(cmGeneratorTarget* gt)
{
this->GeneratorTargets.push_back(gt);
+ this->GlobalGenerator->IndexGeneratorTarget(gt);
}
void cmLocalGenerator::AddImportedGeneratorTarget(cmGeneratorTarget* gt)
{
this->ImportedGeneratorTargets.push_back(gt);
+ this->GlobalGenerator->IndexGeneratorTarget(gt);
}
void cmLocalGenerator::AddOwnedImportedGeneratorTarget(cmGeneratorTarget* gt)
--
cgit v0.12