missingdeps: use nested maps for edge adjacency cache
In my tests, nested maps outperform a large map of pairs by 10-20% on a
sample Chromium missingdeps run, and are arguably simpler due to fewer
ifdefs needed.
diff --git a/src/missing_deps.cc b/src/missing_deps.cc
index adce2d2..eaa3f73 100644
--- a/src/missing_deps.cc
+++ b/src/missing_deps.cc
@@ -172,10 +172,15 @@
}
bool MissingDependencyScanner::PathExistsBetween(Edge* from, Edge* to) {
- EdgePair key(from, to);
- EdgeAdjacencyMap::iterator it = edge_adjacency_map_.find(key);
- if (it != edge_adjacency_map_.end())
- return it->second;
+ AdjacencyMap::iterator it = adjacency_map_.find(from);
+ if (it != adjacency_map_.end()) {
+ InnerAdjacencyMap::iterator inner_it = it->second.find(to);
+ if (inner_it != it->second.end()) {
+ return inner_it->second;
+ }
+ } else {
+ it = adjacency_map_.insert(std::make_pair(from, InnerAdjacencyMap())).first;
+ }
bool found = false;
for (size_t i = 0; i < to->inputs_.size(); ++i) {
Edge* e = to->inputs_[i]->in_edge();
@@ -184,6 +189,6 @@
break;
}
}
- edge_adjacency_map_.insert(std::make_pair(key, found));
+ it->second.insert(std::make_pair(to, found));
return found;
}
diff --git a/src/missing_deps.h b/src/missing_deps.h
index 211a865..ae57074 100644
--- a/src/missing_deps.h
+++ b/src/missing_deps.h
@@ -44,32 +44,6 @@
int generator_rules);
};
-struct EdgePair {
- EdgePair(Edge* from, Edge* to) : from_(from), to_(to) {}
- bool operator==(const EdgePair& other) const {
- return from_ == other.from_ && to_ == other.to_;
- }
- bool operator<(const EdgePair& other) const {
- return (from_ < other.from_) ||
- ((from_ == other.from_) && (to_ < other.to_));
- }
- Edge* from_;
- Edge* to_;
-};
-
-#if __cplusplus >= 201103L
-namespace std {
-template <>
-struct hash<EdgePair> {
- size_t operator()(const EdgePair& k) const {
- uintptr_t uint_from = uintptr_t(k.from_);
- uintptr_t uint_to = uintptr_t(k.to_);
- return hash<uintptr_t>()(uint_from ^ (uint_to >> 3));
- }
-};
-} // namespace std
-#endif // __cplusplus >= 201103L
-
struct MissingDependencyScanner {
public:
MissingDependencyScanner(MissingDependencyScannerDelegate* delegate,
@@ -95,11 +69,13 @@
private:
#if __cplusplus >= 201103L
- using EdgeAdjacencyMap = std::unordered_map<EdgePair, bool>;
+ using InnerAdjacencyMap = std::unordered_map<Edge*, bool>;
+ using AdjacencyMap = std::unordered_map<Edge*, InnerAdjacencyMap>;
#else
- typedef std::map<EdgePair, bool> EdgeAdjacencyMap;
+ typedef std::map<Edge*, bool> InnerAdjacencyMap;
+ typedef std::map<Edge*, InnerAdjacencyMap> AdjacencyMap;
#endif
- EdgeAdjacencyMap edge_adjacency_map_;
+ AdjacencyMap adjacency_map_;
};
#endif // NINJA_MISSING_DEPS_H_
