Topological parallel grouping for script execution in workspaces about pnpm HOT 5 OPEN

It should already work as you described, when you use pnpm -r. Unless, you use pnpm -r --no-sort (https://pnpm.io/cli/recursive#--no-sort)

from pnpm.

There might be a regression here: with v8.3.1, topology of workspace is respected. With 8.15.3, it is not.

Last working version is 8.6.12. First breaking one is 8.7.0.

After digging a bit more, I spotted that it might be due to the resolution of #6922; in my case, replacing relative links to workspace packages with workspace:* worked, and the topology was respected. Yet, this is IMO a breaking change that should be mentioned, and the section in the docs using relative path might be out of date

from pnpm.

Good question, consider the following simple case

a(1) - b(10) - d(1)
  \      \
   c(10)  e(1)

The result of topological sorting is

[ 'c', 'd', 'e' ], [ 'b' ], [ 'a' ]

When pnpm executes, it takes one group as a whole, so cde takes 10s, b takes 10s, a takes 1s, and the total takes 21s.

 time pnpm -r build

Executed in   21.24 secs      fish           external

But we can clearly see: when de finishes executing, we can start b's execution, de takes 1s, cb takes 10s, a takes 1s, and it only takes 12 seconds.

Most tools don't implement this optimization, and it's not hard to implement, it's just that pnpm's execution logic is too complex.

Using the --no-sort parameter disrupts the order of dependencies

 time pnpm -r --no-sort build
Scope: 5 of 6 workspace projects
c build$ sleep 10 && echo c
│ c
└─ Done in 10s
d build$ sleep 1 && echo d
│ d
└─ Done in 1s
a build$ sleep 1 && echo a
│ a
└─ Done in 1s
b build$ sleep 10 && echo b
│ b
└─ Done in 10s
e build$ sleep 1 && echo e
│ e
└─ Done in 1s

demo:
https://github.com/ahaoboy/pnpm-graph-demo

from pnpm.

Since pnpm uses p-limit, which can only restrict the max concurrent tasks but can't read their dependencies, "grouping tasks by dependency and executing each group in sequence" seems to be the best choice.

If pnpm wants to make use of each worker, it must implement a data structure like this:

interface Task {
  id: string;        // or any other values that can be used as "key"
  fn: Promise<void>;
  prevIds: string[]; // to judge whether this task can be run
  nextIds: string[]; // to trigger next tasks
}

Then it can flatten the "groups" (each cycle should be a subsequence of it) and use it to create a Task[], for example:

[
  { id: 'a', fn: ..., prevIds: [], nextIds: ['c', 'e'] },
  { id: 'b', fn: ..., prevIds: [], nextIds: ['d'] },
  { id: 'c', fn: ..., prevIds: ['a'], nextIds: ['e'] },
  { id: 'd', fn: ..., prevIds: ['b'], nextIds: [] },
  { id: 'e', fn: ..., prevIds: ['a', 'c'], nextIds: [] },
]

Finally, we can implement a task runner with concurrency limit:

• When a task x is triggered, it uses x.prevIds to judge whether it can be run.
• When a task x is finished, it tries to trigger all tasks whose id is in x.nextIds.

from pnpm.

"grouping tasks by dependency and executing each group in sequence" seems to be the best choice.

Maybe we can think a little further ahead, we can borrow ideas like parcel-graph, performance and memory will be better than Map, and topological sorting, group execution, interrupt and resume execution of these features should be able to be reused by other package management

from pnpm.