From 122b63ac47a3060e05b5886347f03db8f4ef3ca7 Mon Sep 17 00:00:00 2001 From: Ben Craig Date: Fri, 10 Jun 2016 13:22:13 +0000 Subject: [PATCH] Preallocate ExplodedNode hash table 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 git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@272394 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h | 2 ++ lib/StaticAnalyzer/Core/CoreEngine.cpp | 5 +++++ 2 files changed, 7 insertions(+) diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h index a4e9226616..b14a1cc5f6 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h +++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h @@ -321,6 +321,8 @@ public: 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 AllNodesTy; diff --git a/lib/StaticAnalyzer/Core/CoreEngine.cpp b/lib/StaticAnalyzer/Core/CoreEngine.cpp index c75fb2e763..da608f6c75 100644 --- a/lib/StaticAnalyzer/Core/CoreEngine.cpp +++ b/lib/StaticAnalyzer/Core/CoreEngine.cpp @@ -208,6 +208,11 @@ bool CoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps, // Check if we have a steps limit bool UnlimitedSteps = Steps == 0; + // Cap our pre-reservation in the event that the user specifies + // a very large number of maximum steps. + const unsigned PreReservationCap = 4000000; + if(!UnlimitedSteps) + G.reserve(std::min(Steps,PreReservationCap)); while (WList->hasWork()) { if (!UnlimitedSteps) { -- 2.50.1