diff --git a/src/gn/builder_record.cc b/src/gn/builder_record.cc
index 5c0b84d..8896925 100644
--- a/src/gn/builder_record.cc
+++ b/src/gn/builder_record.cc
@@ -71,10 +71,14 @@
 void BuilderRecord::AddDep(BuilderRecord* dep) {
   DCHECK(state_ == STATE_DEFINED);
   all_deps_.add(dep);
+  WaitInfo* info = nullptr;
   if (!dep->is_resolved()) {
     // This cannot be resolved yet if any of its standard dependencies is not
     // resolved.
-    if (dep->waiting_on_resolution_.add(this)) {
+    if (!info)
+      info = &dep->waiting_map_[this];
+    if (!info->wait_resolved) {
+      info->wait_resolved = true;
       unresolved_count_++;
       DEBUG_BUILDER_RECORD_LOG("-- AddDep waiting_on_resolution %s -> %s\n",
                                dep->ToDebugString().c_str(),
@@ -84,7 +88,10 @@
   if (!dep->is_finalized()) {
     // Finalization of the current record is blocked until the
     // dependency is finalized.
-    if (dep->waiting_on_finalization_.add(this)) {
+    if (!info)
+      info = &dep->waiting_map_[this];
+    if (!info->wait_finalized) {
+      info->wait_finalized = true;
       unfinalized_count_++;
       DEBUG_BUILDER_RECORD_LOG("-- AddDep waiting_on_finalization %s -> %s\n",
                                dep->ToDebugString().c_str(),
@@ -109,10 +116,14 @@
   //    where we might write the ninja file before the validation output path
   //    is computed.
   all_deps_.add(dep);
+  WaitInfo* info = nullptr;
   if (!dep->is_defined()) {
     // The record cannot be resolved yet if any of its validation dependencies
     // is not defined.
-    if (dep->waiting_on_validation_definition_.add(this)) {
+    if (!info)
+      info = &dep->waiting_map_[this];
+    if (!info->wait_validation_defined) {
+      info->wait_validation_defined = true;
       unresolved_count_++;
       DEBUG_BUILDER_RECORD_LOG(
           "-- AddValidationDep waiting_on_validation_definition %s -> %s\n",
@@ -122,7 +133,10 @@
   if (!dep->is_resolved()) {
     // This record cannot be finalized if any of its validation deps is not
     // resolved.
-    if (dep->waiting_on_validation_resolution_.add(this)) {
+    if (!info)
+      info = &dep->waiting_map_[this];
+    if (!info->wait_validation_resolved) {
+      info->wait_validation_resolved = true;
       unfinalized_count_++;
       DEBUG_BUILDER_RECORD_LOG(
           "-- AddValidationDep waiting_on_validation_resolution %s -> %s\n",
@@ -185,12 +199,14 @@
     const {
   std::vector<const BuilderRecord*> result;
   for (auto it = all_deps_.begin(); it.valid(); ++it) {
-    BuilderRecord* dep = *it;
-    if (dep->waiting_on_resolution_.contains(
-            const_cast<BuilderRecord*>(this)) ||
-        dep->waiting_on_validation_definition_.contains(
-            const_cast<BuilderRecord*>(this)))
+    const BuilderRecord* dep = *it;
+    auto wait_it = dep->waiting_map_.find(this);
+    if (wait_it == dep->waiting_map_.end())
+      continue;
+    if (wait_it->second.wait_resolved ||
+        wait_it->second.wait_validation_defined) {
       result.push_back(dep);
+    }
   }
   std::sort(result.begin(), result.end(), LabelCompare);
   return result;
@@ -224,4 +240,4 @@
   result += ")";
   return result;
 }
-#endif  // DEBUG_BUILDER_RECORD
\ No newline at end of file
+#endif  // DEBUG_BUILDER_RECORD
diff --git a/src/gn/builder_record.h b/src/gn/builder_record.h
index 9c3f0be..fd05fd8 100644
--- a/src/gn/builder_record.h
+++ b/src/gn/builder_record.h
@@ -8,6 +8,7 @@
 #include <memory>
 #include <utility>
 
+#include "base/containers/flat_map.h"
 #include "gn/item.h"
 #include "gn/location.h"
 #include "gn/pointer_set.h"
@@ -187,12 +188,13 @@
   // false, stop and return false.
   template <typename Func>
   bool NotifyDependentsWaitingOnValidationDefinition(Func&& func) {
-    BuilderRecordSet waiting_deps =
-        std::move(waiting_on_validation_definition_);
-    for (auto it = waiting_deps.begin(); it.valid(); ++it) {
-      BuilderRecord* waiting = *it;
-      if (waiting->OnDefinedValidationDep(this) && !func(waiting))
-        return false;
+    for (auto& pair : waiting_map_) {
+      if (pair.second.wait_validation_defined) {
+        pair.second.wait_validation_defined = false;
+        BuilderRecord* waiting = pair.first;
+        if (waiting->OnDefinedValidationDep(this) && !func(waiting))
+          return false;
+      }
     }
     return true;
   }
@@ -221,11 +223,13 @@
   // stop and return false.
   template <typename Func>
   bool NotifyDependentsWaitingOnResolution(Func&& func) {
-    BuilderRecordSet waiting_deps = std::move(waiting_on_resolution_);
-    for (auto it = waiting_deps.begin(); it.valid(); ++it) {
-      BuilderRecord* waiting = *it;
-      if (waiting->OnResolvedDep(this) && !func(waiting))
-        return false;
+    for (auto& pair : waiting_map_) {
+      if (pair.second.wait_resolved) {
+        pair.second.wait_resolved = false;
+        BuilderRecord* waiting = pair.first;
+        if (waiting->OnResolvedDep(this) && !func(waiting))
+          return false;
+      }
     }
     return true;
   }
@@ -235,12 +239,13 @@
   // |func| returns false, stop and return false.
   template <typename Func>
   bool NotifyDependentsWaitingOnValidationResolution(Func&& func) {
-    BuilderRecordSet waiting_deps =
-        std::move(waiting_on_validation_resolution_);
-    for (auto it = waiting_deps.begin(); it.valid(); ++it) {
-      BuilderRecord* waiting = *it;
-      if (waiting->OnResolvedValidationDep(this) && !func(waiting))
-        return false;
+    for (auto& pair : waiting_map_) {
+      if (pair.second.wait_validation_resolved) {
+        pair.second.wait_validation_resolved = false;
+        BuilderRecord* waiting = pair.first;
+        if (waiting->OnResolvedValidationDep(this) && !func(waiting))
+          return false;
+      }
     }
     return true;
   }
@@ -263,11 +268,13 @@
   // stop and return false.
   template <typename Func>
   bool NotifyDependentsWaitingOnFinalization(Func&& func) {
-    BuilderRecordSet waiting_deps = std::move(waiting_on_finalization_);
-    for (auto it = waiting_deps.begin(); it.valid(); ++it) {
-      BuilderRecord* waiting = *it;
-      if (waiting->OnFinalizedDep(this) && !func(waiting))
-        return false;
+    for (auto& pair : waiting_map_) {
+      if (pair.second.wait_finalized) {
+        pair.second.wait_finalized = false;
+        BuilderRecord* waiting = pair.first;
+        if (waiting->OnFinalizedDep(this) && !func(waiting))
+          return false;
+      }
     }
     return true;
   }
@@ -281,30 +288,40 @@
   // as a list sorted by label.
   std::vector<const BuilderRecord*> GetSortedUnresolvedDeps() const;
 
+  // Used by unit-tests.
+
   // Records that are waiting on this one to be defined. This is used for
   // "validations" dependencies which don't require the target to be fully
   // resolved, only defined.
-  BuilderRecordSet& waiting_on_validation_definition() {
-    return waiting_on_validation_definition_;
-  }
-  const BuilderRecordSet& waiting_on_validation_definition() const {
-    return waiting_on_validation_definition_;
+  BuilderRecordSet waiting_on_validation_definition() const {
+    BuilderRecordSet result;
+    for (const auto& pair : waiting_map_) {
+      if (pair.second.wait_validation_defined)
+        result.add(pair.first);
+    }
+    return result;
   }
 
   // Records that are waiting on this one to be resolved. This is the other
   // end of the "unresolved deps" arrow for standard dependencies.
-  BuilderRecordSet& waiting_on_resolution() { return waiting_on_resolution_; }
-  const BuilderRecordSet& waiting_on_resolution() const {
-    return waiting_on_resolution_;
+  BuilderRecordSet waiting_on_resolution() const {
+    BuilderRecordSet result;
+    for (const auto& pair : waiting_map_) {
+      if (pair.second.wait_resolved)
+        result.add(pair.first);
+    }
+    return result;
   }
 
   // Records that are waiting on this one to be resolved before they can be
-  // written to the ninja file. This is used for "validations" dependencies.
-  BuilderRecordSet& waiting_on_validation_resolution() {
-    return waiting_on_validation_resolution_;
-  }
-  const BuilderRecordSet& waiting_on_validation_resolution() const {
-    return waiting_on_validation_resolution_;
+  // written to the Ninja file. This is used for "validations" dependencies.
+  BuilderRecordSet waiting_on_validation_resolution() const {
+    BuilderRecordSet result;
+    for (const auto& pair : waiting_map_) {
+      if (pair.second.wait_validation_resolved)
+        result.add(pair.first);
+    }
+    return result;
   }
 
   // Comparator function used to sort records from their label.
@@ -357,10 +374,16 @@
   size_t unfinalized_count_ = 0;
 
   BuilderRecordSet all_deps_;
-  BuilderRecordSet waiting_on_resolution_;
-  BuilderRecordSet waiting_on_finalization_;
-  BuilderRecordSet waiting_on_validation_definition_;
-  BuilderRecordSet waiting_on_validation_resolution_;
+
+  // A specialized { dependent -> wait_info } map used to track
+  // which state changes dependents of this record are waiting for.
+  struct WaitInfo {
+    bool wait_resolved = false;
+    bool wait_finalized = false;
+    bool wait_validation_defined = false;
+    bool wait_validation_resolved = false;
+  };
+  base::flat_map<BuilderRecord*, WaitInfo> waiting_map_;
 
   BuilderRecord(const BuilderRecord&) = delete;
   BuilderRecord& operator=(const BuilderRecord&) = delete;