bcraig created this revision.
bcraig added reviewers: zaks.anna, krememek, jordan_rose.
bcraig added a subscriber: cfe-commits.
This depends on http://reviews.llvm.org/D20930
Rehashing the ExplodedNode table is very expensive. The hashing itself is
expensive, and the general activity of iterating over the hash table is highly
cache unfriendly. Instead, we guess at the eventual size by using the maximum
number of steps allowed. This generally avoids a rehash. It is possible that
we still need to rehash if the backlog of work that is added to the worklist
significantly exceeds the number of work items that we process. Even if we do
need to rehash in that scenario, this change is still a win, as we still have
fewer rehashes that we would have prior to this change.
For small work loads, this will increase the memory used. For large work
loads, it will somewhat reduce the memory used. Speed is significantly
increased. A large .C file took 3m53.812s to analyze prior to this change.
Now it takes 3m38.976s, for a ~6% improvement.
http://reviews.llvm.org/D20933
Files:
include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
lib/StaticAnalyzer/Core/CoreEngine.cpp
Index: lib/StaticAnalyzer/Core/CoreEngine.cpp
===================================================================
--- lib/StaticAnalyzer/Core/CoreEngine.cpp
+++ lib/StaticAnalyzer/Core/CoreEngine.cpp
@@ -208,6 +208,8 @@
// Check if we have a steps limit
bool UnlimitedSteps = Steps == 0;
+ if(!UnlimitedSteps)
+ G.reserve(Steps);
while (WList->hasWork()) {
if (!UnlimitedSteps) {
Index: include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
===================================================================
--- include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
+++ include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
@@ -321,6 +321,8 @@
bool empty() const { return NumNodes == 0; }
unsigned size() const { return NumNodes; }
+ void reserve(unsigned NodeCount) { Nodes.reserve(NodeCount); }
+
// Iterators.
typedef ExplodedNode NodeTy;
typedef llvm::FoldingSet<ExplodedNode> AllNodesTy;
Index: lib/StaticAnalyzer/Core/CoreEngine.cpp
===================================================================
--- lib/StaticAnalyzer/Core/CoreEngine.cpp
+++ lib/StaticAnalyzer/Core/CoreEngine.cpp
@@ -208,6 +208,8 @@
// Check if we have a steps limit
bool UnlimitedSteps = Steps == 0;
+ if(!UnlimitedSteps)
+ G.reserve(Steps);
while (WList->hasWork()) {
if (!UnlimitedSteps) {
Index: include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
===================================================================
--- include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
+++ include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
@@ -321,6 +321,8 @@
bool empty() const { return NumNodes == 0; }
unsigned size() const { return NumNodes; }
+ void reserve(unsigned NodeCount) { Nodes.reserve(NodeCount); }
+
// Iterators.
typedef ExplodedNode NodeTy;
typedef llvm::FoldingSet<ExplodedNode> AllNodesTy;
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
