commit c4eb7329bf61c276544148febb9a51ede58783ba
author Takuto Ikuta <tikuta@google.com> Wed Nov 12 15:11:07 2025 +0900
committer GN LUCI <gn-scoped@luci-project-accounts.iam.gserviceaccount.com> Wed Nov 12 00:13:11 2025 -0800
tree 768ba458d314a5cbd94c9ade078d44adcbc6cd5e
parent e7f3202128bdb2429872fdb138626a010b2bff7f

Use unordered_map instead of map in HeaderChecker

Also use emplace instead of insert to optimize performance.

With this CL, `gn gen --check` takes 120 seconds.

```
tikuta-mac:src tikuta$ time ~/ghq/gn.googlesource.com/gn/out/gn.optimized gen --check -C out/UTRmac-rel/
Done. Made 38392 targets from 4274 files in 119262ms

real    1m59.941s
user    15m7.501s
sys     0m14.056s
```

Without this CL, `gn gen --check` takes 126 seconds.

```
tikuta-mac:src tikuta$ time ~/ghq/gn.googlesource.com/gn/out/gn gen --check -C out/UTRmac-rel/
Done. Made 38392 targets from 4274 files in 125567ms

real    2m6.297s
user    16m6.596s
sys     0m12.044s
```

Context: https://chat.google.com/room/AAAAqkI-BEQ/g5GWL0SzKBI/g5GWL0SzKBI?cls=10
Change-Id: Ia8c4596c8301b76a916cb11c18171215d67eab1e
Reviewed-on: https://gn-review.googlesource.com/c/gn/+/20260
Commit-Queue: Takuto Ikuta <tikuta@google.com>
Reviewed-by: David Turner <digit@google.com>

src/gn/header_checker.cc

diff --git a/src/gn/header_checker.cc b/src/gn/header_checker.cc
index 05c74d6..1ecc90a 100644
--- a/src/gn/header_checker.cc
+++ b/src/gn/header_checker.cc
@@ -5,6 +5,7 @@
 #include "gn/header_checker.h"
 
 #include <algorithm>
+#include <unordered_map>
 
 #include "base/containers/queue.h"
 #include "base/files/file_util.h"
@@ -561,7 +562,7 @@
   // a shortest dependency chain (in reverse order) from search_from to
   // search_for.
 
-  std::map<const Target*, ChainLink> breadcrumbs;
+  std::unordered_map<const Target*, ChainLink> breadcrumbs;
   base::queue<ChainLink> work_queue;
   work_queue.push(ChainLink(search_from, true));
 
@@ -585,7 +586,7 @@
 
     // Always consider public dependencies as possibilities.
     for (const auto& dep : target->public_deps()) {
-      if (breadcrumbs.insert(std::make_pair(dep.ptr, cur_link)).second)
+      if (breadcrumbs.emplace(dep.ptr, cur_link).second)
         work_queue.push(ChainLink(dep.ptr, true));
     }
 
@@ -596,7 +597,7 @@
       // public/private-ness.
       first_time = false;
       for (const auto& dep : target->private_deps()) {
-        if (breadcrumbs.insert(std::make_pair(dep.ptr, cur_link)).second)
+        if (breadcrumbs.emplace(dep.ptr, cur_link).second)
           work_queue.push(ChainLink(dep.ptr, false));
       }
     }