diff --git a/src/gn/header_checker.cc b/src/gn/header_checker.cc
index 20ed4bc..ea76f2f 100644
--- a/src/gn/header_checker.cc
+++ b/src/gn/header_checker.cc
@@ -124,6 +124,7 @@
     : build_settings_(build_settings),
       check_generated_(check_generated),
       check_system_(check_system),
+      targets_count_(targets.size()),
       lock_(),
       task_count_cv_() {
   for (auto* target : targets)
@@ -592,6 +593,9 @@
   // search_for.
 
   std::unordered_map<const Target*, ChainLink> breadcrumbs;
+  if (targets_count_ > 0) {
+    breadcrumbs.reserve(std::min(targets_count_, static_cast<size_t>(1024)));
+  }
   base::queue<ChainLink> work_queue;
   work_queue.push(ChainLink(search_from, true));
 
diff --git a/src/gn/header_checker.h b/src/gn/header_checker.h
index 0c88149..3f313fb 100644
--- a/src/gn/header_checker.h
+++ b/src/gn/header_checker.h
@@ -192,6 +192,8 @@
   // execution.
   base::AtomicRefCount task_count_;
 
+  size_t targets_count_ = 0;
+
   // Maps (target_to, target_from) -> is_permitted.
   enum class DependencyState {
     kNotADependency,