Change language server to use concurrent cancellable reads and exclusive writes

[dsherret]

I think the change in #9271 to an async mutex at a high level was very good to do in that it quickly made the code less error prone and accessible for other developers working on it (harder for devs to make mistakes, removed race conditions, and eliminated deadlocks), however it does have some performance drawbacks since only one task can run through the language server code at one a time.

To expand on the work of #9271, we could split up the code for concurrent read actions and exclusive write actions (phase 1) and then introduce cancellable read actions (phase 2). I believe this would improve the performance of the language server and not introduce too much complexity since the locking still happens at a high level.

Write actions would be anything that updates the user state (input state), so file text changes or configuration updates. These would require exclusive access to the document cache. On write, any read actions would be waited on before proceeding (and maybe cancelled... not sure). These write actions should be very quick and only update the necessary state. Ideally we should be lazy about computing data.

Read actions would be concurrent with other read actions and be cancellable (read actions would be actions such as "find references", "go to definition", etc.). Read actions should still be able to lazily compute and cache data (mutate), but the result of these actions should be pure in that if multiple tasks compute the same value at the same time they would have the same result (ideally though, both tasks could wait on the result computed by a single task... this could be achieved without much added complexity by pushing down the complexity into a reusable general synchronization struct... maybe this will be phase 3 and only if necessary).

To implement phase 1, we could use a RwLock and then ensure the code is structured in such a way that this pattern is very clear and hard for a developer to make a concurrency mistake.

For phase 2, we could use tokio cancellation tokens more liberally in the read actions. This would also have the added benefit of allowing us to also more easily support cancellable LSP commands (cancelRequest) in the future. It might be worth considering cancelling all read actions on a write, but I'm not sure... perhaps just listening for an LSP cancelRequest command is sufficient. We can see once we go to implement it.

cc @kitsonk @bnoordhuis @lucacasonato

[kitsonk]

To implement phase 1, we could use a RwLock and then ensure the code is structured in such a way that this pattern is very clear and hard for a developer to make a concurrency mistake.

@ry was quite opposed to this when I was adding them previously, as he felt it complicated things.

At the end of the day though, we have Language Server Benchmarks so it should be possible to prove that discreet read/write locks would improve performance. I am somewhat skeptical it would, because the biggest bottleneck in performance is tsc, which operates in sync. Being able to cancel inflight requests with tsc would give us a better performance boost than discreet read/write locks I suspect.

[dsherret]

@ry was quite opposed to this when I was adding them previously, as he felt it complicated things.

@kitsonk it would be a single RwLock at the top level similar to the current Mutex and then refactoring the code a bit. I don't think it would complicate things too much in this scenario, but I'd like to hear more about that. I'll ask Ryan later.

At the end of the day though, we have Language Server Benchmarks so it should be possible to prove that discreet read/write locks would improve performance. I am somewhat skeptical it would, because the biggest bottleneck in performance is tsc, which operates in sync. Being able to cancel inflight requests with tsc would give us a better performance boost than discreet read/write locks I suspect.

Yeah, I agree that we would expect the biggest performance boost to come from supporting cancellation. That said, we might find it beneficial (but I'm unsure if it's correct) to cancel "read" requests when a "write" request occurs and we would get a performance boost from that cancellation. Also, I think in the long run, handling "read" requests in parallel would probably help in some scenarios... the one I can think of right now (if I'm understanding correctly) is if a long "find references" request happens then the user asks to format the file (to my understanding, formatting would be a "read" request because it's only returning the text edits and doesn't update the document cache).

It is really unfortunate that tsc is synchronous and I agree that it's the biggest bottleneck ☹

[kitsonk]

the one I can think of right now (if I'm understanding correctly) is if a long "find references" request happens then the user asks to format the file (to my understanding, formatting would be a "read" request because it's only returning the text edits and doesn't update the document cache)

Maybe, but I think we are talking milliseconds of blocking at worst in that scenario.

To get a clearer picture of where the time is spent, and where performance could be improved, work on a fairly large project for a while and then do the Deno: Language Server Status. You will get stats for the last 1000 requests. Just looking now, I am seeing the long pole in the tent being update_diagnostics_ts at 49ms which runs in a seperate thread (though it blocks other requests being processed by tsc), followed by semantics_token_full at 34ms. Which is why I think #11032 would give us a better win. While it wouldn't immediately address semantics_token_full it could easily build towards that and mean we don't have to go into tsc for things like semantic tokens, and try to limit tsc just for type checking diagnostics.

(Taking a look at that though, we might want to keep more than a 1000 records in the performance ring buffer though.)

[bartlomieju]

@dsherret @kitsonk is this issue still relevant after your recent changes to LSP (#12747, #12720, #12868)?

[dsherret]

@bartlomieju yup. Those are slowly also part of working towards this. I want to hold off on doing this change for a bit just to let the other changes settle and I think there's still one more refactor to do, but it would be like turning on a switch when we do it (at least for the concurrent reads/exclusive writes because it would just be using a tokio rwlock).

Bert stumbled on a good scenario where this is relevant where you do import completions at the same time as formatting. We could ensure both of those are "read requests" and therefore happen at the same time and formatting wouldn't be hung up by import completions downloading something.

[bartlomieju]

Thanks for the update.