It seemed surprising that it would be faster to insert sorted than to just push and sort at the end, then I noticed:

we alternate between getting the file's diagnostics and adding diagnostics

That would explain it, if we were adding some diagnostics, doing a complete sort, then adding one more and doing another complete sort. Can you explain why we do this? When do we add diagnostics after having gotten the sorted diagnostics?

Minimally, we always get diagnostics after each file, and our largest rwc test now has 2100 files.

OK, but why do we query the complete list of diagnostics after each individual file? It looks like we have per-file lists available.

We query the global diagnostics before and after each file to see if they've mutated (to see if the global diagnostic is caused by the current file? I'm not fully sure on the reason) doing so caused us to sort and deduplicate all diagnostics, all the time.

@weswigham why not just sort and deduplicate diagnostics for the given fileName or global ones as they are asked.. That would be better than doing it on all files all the time and yet we dont need to to insert and keep diagnostics sorted

@sheetalkamat quicksort (as is usually done by the JS engine) has an average time complexity of n log n, but a worst case complexity of n^2 (though it may use another algo if it heuristically determines it's in a worst-case scenario). Inserting sorted is a log n operation, done n times, so is just always n log n time complexity. We always ask for sorted diagnostics so this is minimally as good as the previous delayed-sorting method from a computational standpoint, since we will always query for diagnostics at least once, and this significantly reduces the constant factor if we query for diagnostics (between mutations) more than once. Plus, it makes the implementation way cleaner to just keep a sorted list at all times (for both), since then we don't need to keep dirty bits in the state, or conditional branches on get.

@weswigham i am not sure i understand the original issue, why were we alternating between getting errors and adding them? is that for global? or for file diagnostics?

getSemanticDiagnostics, as used by emitWorker or getPreEmitDiagnostics, takes a source file (or not). When it is called with an individual source file (as is always true in emitWorker and sometimes true for getPreEmitDiagnostics), it called into checker's getDiagnostics function, which in turn calls getDiagnosticsWorker, which, when called with a sourceFile, gets the global diagnostics, then checks the file, then gets the file diagnostics and the global diagnostics again (so it can return only global diagnostics added during the check of that file). All three of those calls were capable of triggering diagnostic sorting (though only the second is likely to). Previously when any of the methods on diagnostic collection were called to get any subset of the diagnostics, it would sort all diagnostics (unless it had already been sorted and hadn't been modified in any way) - including those from files that weren't currently being looked at. Additionally, whenever you queried for all diagnostics, it would sort and dedupe everything... then combine them all into an all diagnostics array... then sort and dedupe them again. (The first sort and dedupe being extraneous.)

While a sort-once strategy is likely fine for per-file diagnostics (provided it's actually only sorted once ever), both the list of all diagnostics and the global diagnostics list need to be constantly resorted, since additions (can) occur in every file. Rather than holding a dirty flag for every file and sorting file diagnostics once, but also inserting sorted for the global and all diagnostics lists, it's much simpler, implementation-wise, to use insertSorted for all of the lists, and is just as effective to use for the per-file lists provided we always actually query for them (and we always query for diagnostics if the checker is configured to generate them), and is way less likely to become a unintended performance pitfall in the future (for example, if there's some future feature where you only check part of a file at a time).

I like your suggestion of creating allDiagnostics list on demand by combining all file diagnostics in the right order instead of having to keep a second sorted list. let's do that as well.

@mhegazy done.