Process packages in parallel

[pastelsky]

scip-typescript currently can take several minutes to index yarn workspaces. It does not seem to saturate CPU enough or use all cores. Ideally there should be an option to do indexing for multiple packages concurrently to reduce this time.

This would be useful considering slow indexing reduces the benefit of type indexing in the first place on a repository with high frequency commits as a new commits can invalidate the ongoing index.

[varungandhi-src]

Could you share a rough number for how many lines of code / second are you seeing indexing at and what your target number is based on workspace size and peak commit velocity? IIRC, one of the problems here was that we didn't have easy access to the dependency graph between packages in a workspace, which meant the determining the order of indexing was non-trivial, and it would be wasteful to do the naive thing of indexing in parallel without understanding the dependency graph as that would likely lead to a bunch of duplicated work.

Even if we did things in dependency order, it might not be fast enough if your build graph is not wide enough.

[pastelsky]

I'm currently trying to index a large monorepo with over 600+ packages, so I'm a sure topologically sorted graph would be wide enough to saturate CPUs.

Could you share a rough number for how many lines of code / second are you seeing indexing at

It roughly takes me 20 mins to index on a repository with ~2M SLOC of typescript on an M1 Macbook Pro.

what your target number is based on workspace size and peak commit velocity.

Master for us gets updated roughly once every 15 minutes (but this could be higher going forward). Ideally we'd want to be able to index + compress + upload + process well within this time. But given that sourcegrpah does not invalidate the entire index when a new commit is pushed (IIRC from docs), it might not be too bad if the time exceeds that by a bit. Still, the faster, the better.

[pastelsky]

it would be wasteful to do the naive thing of indexing in parallel without understanding the dependency graph as that would likely lead to a bunch of duplicated work.

I think even with some duplicated work, having an option to use more cores might be several times faster on a multi-core machine, and that could be just enough for some repositories to exceed their master update rate. Perhaps this can be something that can be made more efficient over time rather than not providing an option at all ?

I'm happy to test out any early changes and give feedback on it from our repositories if it helps. Very interested in making this scale for us at the moment (and should hopefully help other enterprise users of sourcegraph too)

[varungandhi-src]

But given that sourcegrpah does not invalidate the entire index when a new commit is pushed

Right, code navigation will fall back to the nearest index if one can't be found for the latest commit.

Perhaps this can be something that can be made more efficient over time rather than not providing an option at all ?

That's a fair point. We could try exposing an option for this... In the meantime, if you want a quick workaround, one thing you could try is avoid the workspace indexing option and instead individually invoke the indexer for each inner tsconfig.json from a shell script or similar, and then pass extra -file= arguments to src CLI when uploading the index. We kinda' used this workaround earlier in the Sourcegraph monorepo with lsif-node, but we haven't run into the need for it with scip-typescript.

Thanks for sharing the numbers. Based on those, it seems like the indexer is running much slower than we'd expect... The number you gave ends up being ~1.7k SLOC/s, whereas IIRC early benchmarks were around 5k - 10k SLOC/s, so we may have had a serious regression there too.

[olafurpg]

@pastelsky Thank you for reporting! Can you elaborate with more details about your build? For example, are you able to typecheck your existing TypeScript code in parallel with a separate tool?

The scip-typescript index tsconfig.json command tried to have similar behavior as tsc -b tsconfig.json, except it generates an index.scip file instead of outputting JavaScript. Just like parallell typechecking is outside the scope of the tsc command-line utility, I am on the fence about trying to add parallel indexing to scip-typescript itself. Instead, I'd prefer if your build system can parallelize invocations of scip-typescript.

For the record, I'm not opposed to adding basic parallell processing support to scip-typescript. I'm mostly curious to better understand your problem and see if there's a reasonable alternative solution that you can use.

[pastelsky]

For example, are you able to typecheck your existing TypeScript code in parallel with a separate tool?

No, we use standard tsc (v 4.5) for type-checking, and it consistently takes me less than 3 minutes to type-check my entire repository with the same tsconfig.json object. We aren't considering parallelization because 3 minutes is pretty reasonable for our codebase size.

Another thing I noticed is that the times that scip-typescript prints out per package —

is usually an order of magnitude different from what I perceive. For example, in this case, the time period between the previous package being indexed and this message being printed was more like 2 seconds than 293 millis.

Almost as though the time is spent between packages boundaries rather than scanning TS code of the package itself.

[pastelsky]

Digging a little deeper into my hunch, I profiled a run of scip-typescript.
Indeed my guess was correct. scip-typescript is bottlenecked not by how fast it can scan lines of code, but how many "packages" exist in a monorepo.

This happens because scip-typescript re-initializes a type checker for every package —
https://github.com/sourcegraph/scip-typescript/blob/main/src/ProjectIndexer.ts#L25-L28
this is a very costly operation.

How costly can be seen from this profile of scip-typescript operating on 10 packages —
For every package, scip-typescript spends —

• 46.7% on ts.createProgram
• 20% of its time on ts.getTypeChecker
• Only 10.4% of its time on ProjectIndexer#index

This also explains why I can run yarn tsc on my entire mono-repo in under 3 minutes (where presumably the checker is initialized only once but with more files upfront), but indexing takes ~20 mins. The majority of time is spent in just re-creating the type checker rather than indexing.

Given that workspaces are popular, and monorepos are common — the benchmark of "5k - 10k SLOC/s" seems purely theoretical.

See profiling results —
54312.clinic-flame.html.zip

[olafurpg]

@pastelsky thank you for the detailed information. This is very helpful, especially the flamegraph!

This also explains why I can run yarn tsc on my entire mono-repo in under 3 minutes

Can you please confirm that this is for a clean build? Our benchmarks indicate that tsc typechecks around 1-4k loc/s (the exact number varies between projects). For the sourcegraph/sourcegraph repo, we clean typecheck 160k lines in ~2 minutes (~1.3k loc/s) but we admittedly have heavy usage of rxjs that most likely slows down typechecking compared to normal codebases. At ~2m loc and 3 minutes, your codebase is getting typechecked at ~11k loc/s, which sounds surprisingly fast.

[olafurpg]

Me and @varungandhi-src investigated our usage of ts.createProgram and learned a few things:

• We currently call ts.createProgram once for every project to ensure that each project gets correct compiler options. We could consolidate all ts.createProgram invocations but that would mean that they use incorrect compiler options (including project root settings, relative paths won't resolve correctly, etc.).
• TypeScript has APIs for incremental compilation, added in this PR Api for tsc --build and --incremental microsoft/TypeScript#31432
• scip-typescript doesn't re-use a ts.CompilerHost instance between projects. We tried using this but didn't notice any performance difference in the sourcegraph/sourcegraph repository. We also can't find examples online where the compiler host is recommended to solve performance issues.
• One hypothesis: the slow performance may be happening from deep project dependency chains. For example, if loading a project requires re-typechecking all transitive dependencies then it becomes quadratic. We may not be experiencing pathological performance in the sourcegraph/sourcegraph repo because the deepest dependency chain is maybe ~3-4 projects max. @pastelsky Do you have a rough idea how long the dependency chains can be?

[pastelsky]

Can you please confirm that this is for a clean build?

Yes, this is for a clean build. Here's the tsconfig in use, which could make a difference —

tsconfig.json

{
  "compilerOptions": {
     "baseUrl": "./",
    "noEmit": true,
    "module": "CommonJS"
    "allowJs": false,
    "strict": true,
    "declaration": true,
    "esModuleInterop": true,
    "downlevelIteration": true,
    "jsx": "react",
    "moduleResolution": "node",
    "sourceMap": true,
    "skipLibCheck": true,
    "isolatedModules": true,
    "target": "es2019",
    "lib": [
      "dom",
      "dom.iterable",
      "es5",
      "scripthost",
      "es2015.core",
      "es2015.collection",
      "es2015.symbol",
      "es2015.iterable",
      "es2015.promise",
      "es2016.array.include"
    ]
  },
}

[pastelsky]

scip-typescript doesn't re-use a ts.CompilerHost instance between projects. We tried using this but didn't notice any performance difference in the sourcegraph/sourcegraph repository. We also can't find examples online where the compiler host is recommended to solve performance issues.

I haven't tried this out personally, but I remember another tool we use — API extractor that also runs TS analysis per package recommending this —
https://api-extractor.com/pages/contributing/building/#:~:text=These%20test%20projects,each%20project%20individually.

@pastelsky Do you have a rough idea how long the dependency chains can be?

Like I said, we have about ~600 packages in our monorepo, and these do internally link to each other — and in some cases the dependency chains can be some levels deep. I don't think what we have is very atypical though.
I guess by initializing ts.createProgram for each project, you essentially are repeating work for all common dependencies. And having a way to cut down on that is the only way to make this faster.