Node linker runtime is cubic in the number of mappings

[fmeum]

🐞 bug report

Affected Rule

The issue is caused by the rule: nodejs_binary and npm_package_bin.

Is this a regression?

No

Description

The per-target runtime of the module_mappings_aspect that collects the required information for the Node linker is quadratic in the number of mappings traversed, leading to an overall cubic runtime of the aspect. Since the aspect does this work in the analysis phase, its result is not cached persistently, leading to pretty slow analysis phases after a Bazel server startup.

The reason for the quadratic runtime is that the full mapping for the transitive dependencies is built for every target and involves a traversal of the dependencies' mappings in https://github.com/bazelbuild/rules_nodejs/blob/26680a4e5da5db60601213bee1de5d607e693fc8/internal/linker/link_node_modules.bzl#L170, which is a loop that in its body calls _link_mapping which again traverses the mapping in https://github.com/bazelbuild/rules_nodejs/blob/26680a4e5da5db60601213bee1de5d607e693fc8/internal/linker/link_node_modules.bzl#L50.

Note that _link_mapping's only purpose is to catch errors. If the call is dropped, the analysis wall time used by the aspect already drops dramatically (from ~30s to ~1s in an experiment with a medium-size package.json). Maintaining the partial mappings in a depset and only flattening them once when the manifest is written would allow for a further reduction and make the aspect run in constant time per target.

🔬 Minimal Reproduction

In any kind of repository with an at least medium-size package.json (~100 direct dependencies), create a nodejs_binary target //:foo that references all packages via @npm//:node_modules.

🔥 Exception or Error

Execute:

bazel shutdown && bazel build //:foo --nobuild

and then analyze the trace profile at $(bazel info output_base)/command.profile.gz). In my case, _get_module_mappings accounts for 30s of analysis phase wall time.

🌍 Your Environment

Operating System:

Linux

Output of bazel version:

5.0.0

Rules_nodejs version:

(Please check that you have matching versions between WORKSPACE file and @bazel/* npm packages.)

5.0.2

Anything else relevant?

I prepared a PR that modifies the linker aspect to rely on depsets: #3301

[alexeagle]

Fantastic analysis, thank you! I think this problem came up in a client call this week as well.

[fmeum]

Fixed in #3301.