tree c45e8e78114ba6cacc996d60f0b0232948a02cae
parent 2c775ed71ed9c7ceb11823ced47a1a2640883403
author Takuto Ikuta <tikuta@google.com> 1771917100 +0900
committer GN LUCI <gn-scoped@luci-project-accounts.iam.gserviceaccount.com> 1771921132 -0800

Optimize reachability cache to drastically reduce BFS executions

The most significant part of this optimization is caching the
reachability search results starting from a 'from_target'. By sharing
this cache across all files and includes within the same target, we
avoid redundant, expensive BFS traverses, which was the primary
bottleneck.

Benchmark results on macOS (hyperfine):

Benchmark 1: gn_main gen out/no_clang_modules/ --check
  Time (mean ± σ):     15.978 s ±  0.107 s    [User: 139.317 s, System: 20.336 s]
  Range (min … max):   15.845 s … 16.141 s    10 runs


Benchmark 2: gn_bfs_cache gen out/no_clang_modules/ --check
  Time (mean ± σ):      7.578 s ±  0.048 s    [User: 23.380 s, System: 38.648 s]
  Range (min … max):    7.481 s …  7.656 s    10 runs

Summary
  gn_bfs_cache ran 2.11 ± 0.02 times faster than gn_main

Additionally, this change:
- Shards the cache into 64 shards using std::unordered_map and fine-grained
  locking (std::shared_mutex) to reduce lock contention during concurrent
  checks.
- Uses std::unique_ptr for ReachabilityCache to safely manage non-copyable
  objects (due to the included mutex).

Bug: 484862257
Change-Id: I9a85e813ba942384eb1237fa965e447b1224659d
Reviewed-on: https://gn-review.googlesource.com/c/gn/+/21160
Reviewed-by: David Turner <digit@google.com>
Commit-Queue: Takuto Ikuta <tikuta@google.com>