@lerna/run with just-in-time queue management

[bweggersen]

This PR introduces just-in-time (JIT) queue management when running scripts in parallel in @lerna/run. The current model for running scripts in parallel uses batches which are causing inefficiencies as threads have to wait for a batch to finish before they can pick up new tasks.

We currently have 84 packages in our monorepo. Below is a visualization of what running scripts in parallel using batches look like:

In contrast, here is a visualization of running scripts with JIT queue management:

The total build time is reduced by half!

Description

We create a graph representation of the packages to be built and an empty promise queue (p-queue). We find every leaf-node from the graph and them to the promise queue with a post-run-task that will prune the graph of references to self and then attempt to add new leaf-nodes to the promise queue. Finally, cyclical packages, if any, are added to the promise queue.

Picking leaf-nodes, pruning the graph and adding cyclical packages last are all existing patterns used in Lerna. This PR simply performs some of these operations dynamically and on a JIT basis.

Motivation and Context

As illustrated by the graphs above, allowing each thread to pick an available package instead of having to wait for a batch to finish optimizes concurrency.

How Has This Been Tested?

There are many existing tests in Lerna for running scripts in parallel. All tests are green. In addition, we have been using a fork of Lerna with JIT queue management in our repo with developers, CI, and CD running it daily for about a month.

Types of changes

• Bug fix (non-breaking change which fixes an issue)
• New feature (non-breaking change which adds functionality)
• Breaking change (fix or feature that would cause existing functionality to change)

Checklist:

• My code follows the code style of this project.
• My change requires a change to the documentation.
• I have updated the documentation accordingly.
• I have read the CONTRIBUTING document.
• I have added tests to cover my changes.
• All new and existing tests passed.

[bweggersen]

@evocateur Please let me know if you have any questions or concerns about the PR. I'm also happy to discuss the implementation if you think it could be better.

[evocateur]

Really excited about this, thanks for your patience!

[evocateur]

I'm so excited to use query-graph elsewhere in the codebase, especially with lerna publish improvements slated for the next major (#1767).

[bweggersen]

I'm so excited to use query-graph elsewhere in the codebase, especially with lerna publish improvements slated for the next major (#1767).

I wasn't aware of some of these improvements! This looks really good. Any eta?

[evocateur]

Awesome, thanks for your patience!

[evocateur]

As for ETA on lerna@4... hopefully soon-ish? I wanna merge a bunch of recent PRs that have been languishing and publish a 3.x minor before I start thinking seriously about 4.0. Maybe even plan ahead of time? (Stranger things have happened 🤣)

[revelt]

Is it possible that somehow we broke lerna run, #2117 — it ends tasks immediately and marks as done without actually doing anything. lerna 3.13.4 works fine. Please double check lerna run yourselves on 3.14.*