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.

2 files changed, 15 insertions, 34 deletions

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 @@ void MissingDependencyScanner::PrintStats() {
 }
 
 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 @@ bool MissingDependencyScanner::PathExistsBetween(Edge* from, Edge* to) {
       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 @@ class MissingDependencyPrinter : public MissingDependencyScannerDelegate {
                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 @@ struct MissingDependencyScanner {
 
  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_