tree a8dc087ba3d4cd350ba7af0002b8ddfb87d1179e
parent 28fc44708c4fe418a3c243931067e99e6497e3f8
author Matt Stark <msta@google.com> 1788751750 +1000
committer gn-scoped@luci-project-accounts.iam.gserviceaccount.com <gn-scoped@luci-project-accounts.iam.gserviceaccount.com> 1788847469 -0700

Use ReachabilityCache to improve performance of loop detection

Together with the previous optimizations, this changes the time
complexity of suggestions be no longer proportional to the number of targets in the build graph.

To benchmark this, I changed the allowlist for `check_includes_strict`
to //*, then ran `gn check`.

Before: Outputs a few errors per second. Left it running for a few
minutes and I had no way to tell how long it was going to take, but
probably hours.
After: Outputs 295,000 errors in 22 seconds.

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