tree 735c7e2ecc3e552d2bd2f1ec40c675f61039f681
parent 127dd2a6d582528d6d61c4d838dc17385ef31abd
author Nico Weber <thakis@chromium.org> 1790228836 -0700
committer gn-scoped@luci-project-accounts.iam.gserviceaccount.com <gn-scoped@luci-project-accounts.iam.gserviceaccount.com> 1790230521 -0700

Don't write order-only deps reachable through direct deps

The size of the generated ninja files is quadratic: NinjaCBinaryTargetWriter writes an order-only dep for every non-linkable
dep of a target. `source_set("a")` depending on `source_set("b")`
depending on `source_set("c")` produced:

build phony/c.linkdeps: phony c.o
build phony/b.linkdeps: phony b.o || phony/c.linkdeps
build phony/a.linkdeps: phony a.o || phony/b.linkdeps phony/c.linkdeps

a.linkdeps listing c.linkdeps is not needed.

Instead, only write order-only deps for:

1. Direct deps (looking through groups, which have no build statement).
2. Libraries inherited through direct deps whose build statement doesn't
   list them (e.g. Rust libraries, or final targets that forward shared
   libraries).
3. Frameworks (create_bundle targets). ClassifyDependency() doesn't
   treat them as non-linkable deps of non-final targets.

https://issues.chromium.org/issues/40278737#comment7 compares ninja
files before and after this patch and checks that they are equivalent.

Results for a Chromium build (mac, arm64, is_debug=false):

                                      before         after
  size of all loaded .ninja files     2634 MB        1009 MB
    .linkdeps phony edges             1442 MB          15 MB
    `||` on alink edges                181 MB           5 MB
    `||` on link edges                  21 MB         0.3 MB
  gn gen (hyperfine, 6 runs)          2.917s ± .047  2.160s ± .052
    user / sys                        18.5s / 7.2s   12.3s / 4.7s

Chromium no-op builds of base_unittests (target already built, hyperfine,
M-series Mac), for siso and various ninja versions:

                                               before          after
  siso v1.6.0 (autoninja), -offline            1.058s ± .031   735.5 ms ± 13.7
    user / sys                                 7.0s / 2.0s     3.7s / 1.9s
  depot_tools ninja (1.12.1)                   10.09s ± .10    4.37s ± .02
  ninja v1.13.2                                6.388s ± .049   2.755s ± .009
  ninja with some local changes to tweak perf  950.9 ms ± 5.1  535.8 ms ± 2.7

(`siso -n` and `ninja -n` are within 2% of the no-op times.)

No intended behavior change.

Bug: chromium:40278737
Change-Id: I517db1c641001e404d3e02ab0e653c1133076d7f
Reviewed-on: https://gn-review.googlesource.com/c/gn/+/26740
Commit-Queue: Nico Weber <thakis@chromium.org>
Reviewed-by: Takuto Ikuta <tikuta@google.com>
Reviewed-by: Nico Weber <thakis@google.com>