tree 896143746bf3d35bf38d574c95ea831aa801c01b
parent 38eb2a1b71f55281f8e4b6043fe8864411c45383
author Andrew Grieve <agrieve@google.com> 1749046193 -0400
committer GN LUCI <gn-scoped@luci-project-accounts.iam.gserviceaccount.com> 1749047032 -0700

Optimize Target::EnsureFileIsGeneratedByDependency()

For targets with a large number of generated inputs, it's very common
for those generated inputs to be generated by the same target, and for
them to be listed in the same order within that target. As such, start
the search for subsequent generated sources where the previous one was
found.

In Chromium, some large target onresolve() steps were taking 500-800ms
on my machine to run this check. With this change, they now take ~1ms.

//third_party/blink/renderer/bindings/modules/v8:v8 was the slowest one.
It has a large tree of public_deps, and lot of generated source files
(~5000), and has deps with a large number of outputs (mojom).

I at first tried creating creating an unordered_set<OutputFile> for
targets with large number of outputs, but that did not noticeably
improve runtime.

Hyperfine Benchmark from Chromium:
Before:
  Time (mean ± σ):      8.001 s ±  0.203 s    [User: 62.682 s, System: 53.541 s]
  Range (min … max):    7.773 s …  8.362 s    10 runs

After:
  Time (mean ± σ):      7.349 s ±  0.251 s    [User: 66.903 s, System: 50.486 s]
  Range (min … max):    6.974 s …  7.655 s    10 runs


Bug: chromium:398002893
Change-Id: I4989052ecaf6e3cc4ad2acb4cb5c94e98e83c5a1
Reviewed-on: https://gn-review.googlesource.com/c/gn/+/18960
Reviewed-by: David Turner <digit@google.com>
Commit-Queue: Andrew Grieve <agrieve@google.com>