On Wed, Jun 11, 2014 at 10:46 AM, Brad King wrote:
> I was able to lower the constant factor on the O(n^2) time
> locally with a change to make GetTransitiveTargetClosure
> callers:
>
>
> http://cmake.org/gitweb?p=cmake.git;a=blob;f=Source/cmTarget.cxx;hb=487b6ccd#l5215
>
> http://cmake.org/gitweb?p=cmake.git;a=blob;f=Source/cmTarget.cxx;hb=487b6ccd#l5431
>
> receive the value returned by reference from an internal map
> that memoizes the result. See attached patch series.
Actually attached this time.
-Brad
>From bdd2a90f8aa0fad1e215fe9aac3c0da04c835555 Mon Sep 17 00:00:00 2001
Message-Id: <bdd2a90f8aa0fad1e215fe9aac3c0da04c835555.1402498210.git.brad.k...@kitware.com>
From: Brad King <brad.k...@kitware.com>
Date: Wed, 11 Jun 2014 10:39:13 -0400
Subject: [PATCH 1/3] cmTarget: Drop unused GetTransitiveTargetClosure argument
The method is never called with any headTarget besides "this".
---
Source/cmTarget.cxx | 9 ++++-----
Source/cmTarget.h | 1 -
2 files changed, 4 insertions(+), 6 deletions(-)
diff --git a/Source/cmTarget.cxx b/Source/cmTarget.cxx
index 01edde9..cb382ff 100644
--- a/Source/cmTarget.cxx
+++ b/Source/cmTarget.cxx
@@ -5213,7 +5213,7 @@ PropertyType checkInterfacePropertyCompatibility(cmTarget const* tgt,
|| (!impliedByUse && !explicitlySet));
std::vector<cmTarget*> deps;
- tgt->GetTransitiveTargetClosure(config, tgt, deps);
+ tgt->GetTransitiveTargetClosure(config, deps);
if(deps.empty())
{
@@ -5429,7 +5429,7 @@ bool isLinkDependentProperty(cmTarget const* tgt, const std::string &p,
const std::string& config)
{
std::vector<cmTarget*> deps;
- tgt->GetTransitiveTargetClosure(config, tgt, deps);
+ tgt->GetTransitiveTargetClosure(config, deps);
if(deps.empty())
{
@@ -6163,18 +6163,17 @@ void processILibs(const std::string& config,
//----------------------------------------------------------------------------
void cmTarget::GetTransitiveTargetClosure(const std::string& config,
- cmTarget const* headTarget,
std::vector<cmTarget*> &tgts) const
{
std::set<cmTarget*> emitted;
cmTarget::LinkImplementation const* impl
- = this->GetLinkImplementationLibraries(config, headTarget);
+ = this->GetLinkImplementationLibraries(config, this);
for(std::vector<std::string>::const_iterator it = impl->Libraries.begin();
it != impl->Libraries.end(); ++it)
{
- processILibs(config, headTarget, *it, tgts, emitted);
+ processILibs(config, this, *it, tgts, emitted);
}
}
diff --git a/Source/cmTarget.h b/Source/cmTarget.h
index 2d51835..0b95a50 100644
--- a/Source/cmTarget.h
+++ b/Source/cmTarget.h
@@ -280,7 +280,6 @@ public:
cmTarget const* headTarget,
std::vector<cmTarget*> &libs) const;
void GetTransitiveTargetClosure(const std::string& config,
- cmTarget const* headTarget,
std::vector<cmTarget*> &libs) const;
/** The link implementation specifies the direct library
--
2.0.0
>From 5d15419d061648cc24ab2bb01a1dace63698e4f3 Mon Sep 17 00:00:00 2001
Message-Id: <5d15419d061648cc24ab2bb01a1dace63698e4f3.1402498210.git.brad.k...@kitware.com>
In-Reply-To: <bdd2a90f8aa0fad1e215fe9aac3c0da04c835555.1402498210.git.brad.k...@kitware.com>
References: <bdd2a90f8aa0fad1e215fe9aac3c0da04c835555.1402498210.git.brad.k...@kitware.com>
From: Brad King <brad.k...@kitware.com>
Date: Wed, 11 Jun 2014 10:39:51 -0400
Subject: [PATCH 2/3] cmTarget: Rename Get{TransitiveTarget =>
LinkImplementation}Closure
The method computes the transitive closure of targets starting with
the current target link implementation libraries. Clarify the name.
---
Source/cmTarget.cxx | 6 +++---
Source/cmTarget.h | 4 ++--
2 files changed, 5 insertions(+), 5 deletions(-)
diff --git a/Source/cmTarget.cxx b/Source/cmTarget.cxx
index cb382ff..6a0826f 100644
--- a/Source/cmTarget.cxx
+++ b/Source/cmTarget.cxx
@@ -5213,7 +5213,7 @@ PropertyType checkInterfacePropertyCompatibility(cmTarget const* tgt,
|| (!impliedByUse && !explicitlySet));
std::vector<cmTarget*> deps;
- tgt->GetTransitiveTargetClosure(config, deps);
+ tgt->GetLinkImplementationClosure(config, deps);
if(deps.empty())
{
@@ -5429,7 +5429,7 @@ bool isLinkDependentProperty(cmTarget const* tgt, const std::string &p,
const std::string& config)
{
std::vector<cmTarget*> deps;
- tgt->GetTransitiveTargetClosure(config, deps);
+ tgt->GetLinkImplementationClosure(config, deps);
if(deps.empty())
{
@@ -6162,7 +6162,7 @@ void processILibs(const std::string& config,
}
//----------------------------------------------------------------------------
-void cmTarget::GetTransitiveTargetClosure(const std::string& config,
+void cmTarget::GetLinkImplementationClosure(const std::string& config,
std::vector<cmTarget*> &tgts) const
{
std::set<cmTarget*> emitted;
diff --git a/Source/cmTarget.h b/Source/cmTarget.h
index 0b95a50..ea50179 100644
--- a/Source/cmTarget.h
+++ b/Source/cmTarget.h
@@ -279,8 +279,8 @@ public:
void GetTransitivePropertyTargets(const std::string& config,
cmTarget const* headTarget,
std::vector<cmTarget*> &libs) const;
- void GetTransitiveTargetClosure(const std::string& config,
- std::vector<cmTarget*> &libs) const;
+ void GetLinkImplementationClosure(const std::string& config,
+ std::vector<cmTarget*> &libs) const;
/** The link implementation specifies the direct library
dependencies needed by the object files of the target. */
--
2.0.0
>From 1d84985979e1c46fffcb3b09fc305a54396a8e93 Mon Sep 17 00:00:00 2001
Message-Id: <1d84985979e1c46fffcb3b09fc305a54396a8e93.1402498210.git.brad.k...@kitware.com>
In-Reply-To: <bdd2a90f8aa0fad1e215fe9aac3c0da04c835555.1402498210.git.brad.k...@kitware.com>
References: <bdd2a90f8aa0fad1e215fe9aac3c0da04c835555.1402498210.git.brad.k...@kitware.com>
From: Brad King <brad.k...@kitware.com>
Date: Wed, 11 Jun 2014 10:40:36 -0400
Subject: [PATCH 3/3] cmTarget: Cache GetLinkImplementationClosure results
Store them internally and return by reference to avoid duplicate
computation.
---
Source/cmTarget.cxx | 34 ++++++++++++++++++++++------------
Source/cmTarget.h | 4 ++--
2 files changed, 24 insertions(+), 14 deletions(-)
diff --git a/Source/cmTarget.cxx b/Source/cmTarget.cxx
index 6a0826f..9d82d88 100644
--- a/Source/cmTarget.cxx
+++ b/Source/cmTarget.cxx
@@ -170,12 +170,15 @@ public:
CachedLinkInterfaceSourcesEntries;
mutable std::map<std::string, std::vector<TargetPropertyEntry*> >
CachedLinkInterfaceCompileFeaturesEntries;
+ mutable std::map<std::string, std::vector<cmTarget*> >
+ CachedLinkImplementationClosure;
mutable std::map<std::string, bool> CacheLinkInterfaceIncludeDirectoriesDone;
mutable std::map<std::string, bool> CacheLinkInterfaceCompileDefinitionsDone;
mutable std::map<std::string, bool> CacheLinkInterfaceCompileOptionsDone;
mutable std::map<std::string, bool> CacheLinkInterfaceSourcesDone;
mutable std::map<std::string, bool> CacheLinkInterfaceCompileFeaturesDone;
+ mutable std::map<std::string, bool> CacheLinkImplementationClosureDone;
};
//----------------------------------------------------------------------------
@@ -5212,8 +5215,8 @@ PropertyType checkInterfacePropertyCompatibility(cmTarget const* tgt,
assert((impliedByUse ^ explicitlySet)
|| (!impliedByUse && !explicitlySet));
- std::vector<cmTarget*> deps;
- tgt->GetLinkImplementationClosure(config, deps);
+ std::vector<cmTarget*> const& deps =
+ tgt->GetLinkImplementationClosure(config);
if(deps.empty())
{
@@ -5428,8 +5431,8 @@ bool isLinkDependentProperty(cmTarget const* tgt, const std::string &p,
const std::string& interfaceProperty,
const std::string& config)
{
- std::vector<cmTarget*> deps;
- tgt->GetLinkImplementationClosure(config, deps);
+ std::vector<cmTarget*> const& deps =
+ tgt->GetLinkImplementationClosure(config);
if(deps.empty())
{
@@ -6162,19 +6165,26 @@ void processILibs(const std::string& config,
}
//----------------------------------------------------------------------------
-void cmTarget::GetLinkImplementationClosure(const std::string& config,
- std::vector<cmTarget*> &tgts) const
+std::vector<cmTarget*> const&
+cmTarget::GetLinkImplementationClosure(const std::string& config) const
{
- std::set<cmTarget*> emitted;
+ std::vector<cmTarget*>& tgts =
+ this->Internal->CachedLinkImplementationClosure[config];
+ if(!this->Internal->CacheLinkImplementationClosureDone[config])
+ {
+ this->Internal->CacheLinkImplementationClosureDone[config] = true;
+ std::set<cmTarget*> emitted;
- cmTarget::LinkImplementation const* impl
+ cmTarget::LinkImplementation const* impl
= this->GetLinkImplementationLibraries(config, this);
- for(std::vector<std::string>::const_iterator it = impl->Libraries.begin();
- it != impl->Libraries.end(); ++it)
- {
- processILibs(config, this, *it, tgts, emitted);
+ for(std::vector<std::string>::const_iterator it = impl->Libraries.begin();
+ it != impl->Libraries.end(); ++it)
+ {
+ processILibs(config, this, *it, tgts , emitted);
+ }
}
+ return tgts;
}
//----------------------------------------------------------------------------
diff --git a/Source/cmTarget.h b/Source/cmTarget.h
index ea50179..14aef5f 100644
--- a/Source/cmTarget.h
+++ b/Source/cmTarget.h
@@ -279,8 +279,8 @@ public:
void GetTransitivePropertyTargets(const std::string& config,
cmTarget const* headTarget,
std::vector<cmTarget*> &libs) const;
- void GetLinkImplementationClosure(const std::string& config,
- std::vector<cmTarget*> &libs) const;
+ std::vector<cmTarget*> const&
+ GetLinkImplementationClosure(const std::string& config) const;
/** The link implementation specifies the direct library
dependencies needed by the object files of the target. */
--
2.0.0
--
Powered by www.kitware.com
Please keep messages on-topic and check the CMake FAQ at:
http://www.cmake.org/Wiki/CMake_FAQ
Kitware offers various services to support the CMake community. For more
information on each offering, please visit:
CMake Support: http://cmake.org/cmake/help/support.html
CMake Consulting: http://cmake.org/cmake/help/consulting.html
CMake Training Courses: http://cmake.org/cmake/help/training.html
Visit other Kitware open-source projects at
http://www.kitware.com/opensource/opensource.html
Follow this link to subscribe/unsubscribe:
http://public.kitware.com/cgi-bin/mailman/listinfo/cmake-developers
