tree fdbedbec7455b7501d2d5fb5da817f1f9662d519
parent 2ab81981a83bb790d40305773284476e8d7bef4c
author Takuto Ikuta <tikuta@google.com> 1789456378 +0900
committer gn-scoped@luci-project-accounts.iam.gserviceaccount.com <gn-scoped@luci-project-accounts.iam.gserviceaccount.com> 1789517311 -0700

[gn] Use std::unordered_map for waiting_map_

Previously, BuilderRecord::waiting_map_ was a base::flat_map. For
heavily depended-upon targets (such as core libraries like //base:base
and popular configs) that have thousands of dependents, inserting a new
dependent in waiting_map_ caused a binary search followed by an O(N)
memmove of all subsequent elements to keep the flat_map sorted.

Once StringAtomSet global lock contention is eliminated, worker threads
parse and submit targets to the Builder at a much higher rate, making
these O(N) memmove insertions a major bottleneck on the main thread.

However, waiting_map_ only requires point lookup by pointer and full
traversals to notify dependents of state changes; it never requires
sorted order (and functions like GetSortedUnresolvedDeps already sort
their output explicitly).

Switching to std::unordered_map eliminates the array shifts on insertion.

Benchmark results (`gn gen out/Default` on Chromium, 5 runs with hyperfine,
official release build configuration with Fuchsia Clang + libc++ +
static libjemalloc.a + LTO):
- Stacked on StringAtomSet sharding (CL 26540):
  2.258s ± 0.035s -> 2.060s ± 0.064s (-198ms / -8.8%, min 2.011s)
- Compared to origin/main:
  2.755s ± 0.029s -> 2.060s ± 0.064s (-695ms / 1.34x faster)

Output ninja files remain bit-for-bit identical across all 14,639 files.

TAG=agy
CONV=4cb5d931-60a8-4f44-8632-3e8d9fb10a8d

Change-Id: I3174ee798a5f6d0c58736fc05ad4ed2684b1d37c
Reviewed-on: https://gn-review.googlesource.com/c/gn/+/26560
Reviewed-by: Matt Stark <msta@google.com>
Commit-Queue: Takuto Ikuta <tikuta@google.com>