Substantiate the value of ShakeQueue

[pepeiborra]

ShakeQueue adds substantial complexity and the benefits are unclear.

• What problem does the queue solve?
• What are priorities used for?
• What are retries used for?
• How does cancellation work now?

It seems to me that the queue is designed with useWithState in mind, but it will overall make ghcide either less responsive or less accurate.

Would this be needed if the Shake database could handle multiple concurrent computations?

[mpickering]

Thanks Pepe, great questions.

The introduction of the queue was completely motivated by the desire to make the IDE more responsive but slightly less accurate for specific requests. In particular I was motivated by the fact that when used on GHC, hover times always had a high latency and completions were unusable because they took over 5s to display! [1]. For hover and completions, if the information is slightly out of date it can be corrected by the position mapping and so should return instantly even if the current document version is slightly ahead. In particular for completions, they are rarely going to change and if they are inaccurate it doesn't really matter but if they are slow then they are unusable.

Desire 1: We want user requests to return instantly. In particular requests such as hover should be instant.

Implementation: We introduced a new class of actions called IdeAction which are allowed to read from the Values variable but not directly call functions from the Action monad which are run by shake and have to establish freshness. The main way for functions in this monad to query information is by using the useWithStaleFast function.

It is critical that this fast request path is NOT run by shakeRun because only one instance of shakeRun is permitted at once and so these requests would block on other operations competing. This problem was mitigated in the old implementation by canceling the previously running action on any call to shakeRun but this causes the perverse situation where computing a hover causes typechecking to be cancelled. An IDE is also constantly requesting stuff like outline, completions, code actions etc which cause a lot cancellations and redundant starts.

Further to this, there is no general requeueing mechanism, so if a request is cancelled then that's it, or is it? There is one requeueing mechanism already implemented in ghcide in the form of the kick action in exe/Main.hs. After every single call to shakeRun the kick action used to be called in order to check that the files of interest were typechecked.

There are several issues with kick:

• This approach is far too coarse grained. The cancellation mechanism in ShakeQueue is a much more refined version of the old kicking behaviour which works for any requests other than typechecking.
• As hovering used to by run with shakeRun is would add a 0.2 overhead to the duration of any hover call reported in the logging (the effect was mitigated by the definition of runAction which could signal one path was finished quickly by signalling to barrier but the timing did not account for this).
• It leads to a lot of redundant work, there is no reason a hover should cause a file to be typechecked.

So I wanted to remove the kick behaviour and only trigger typechecking when a file was actually modified in order to make less work happen on every request. See FileStore.hs for where the
typechecking is now triggered.

If you remove kick but keep the old exceptions behaviour where any new request would kill the specific typechecking invoked by the methods in FileStore.hs and you wouldn't get diagnostics for a specific file so if kick is removed there needs to be a general requeueing mechanism as well in case the important calls get cancelled.

The queue mechanism is also used for other things.

Firstly, when a hover action is requested the information is returned instantly but a new request is queued to update the information in GetSpanInfos. The same for completions and so on. Therefore the stale information should never be very far out of date.

Secondly, the queueing mechanism allowed me to implement the propagation feature, where when you save a file then all the other files which depend on it are triggered for recompilation as well so you can diagnostics for the whole project.

Thirdly, the queueing feature is used during initialisation of a new component to generate the cache of ModIface for all the new targets. On the initial load, when a new component is discovered then the GhcSession is immediately returned but then uses ModIface is queued so that at some later point diagnostics for the whole component will be generated like when you load a component into GHCi.

In general there are many situations where you do not want to block the IDE responding to a request but you would also like something to happen later on as a result of something specific changing. This is a nice way to implement that in the shake world rather than completely reimplement the architecture.

This brings us onto the purpose of priorities, some of these actions we care less about running promptly than others. Honestly, the queue size has always been so small that priorities are not that important so the complexity could be removed but I haven't attempted to tune the priority structure yet and was going to be guided by tracing and profiling if that was necessary.

There is a tradeoff between how big you make each batch of actions you pass to shakeRun. The more actions you pass the less time overall will be taken because more work can be shared between each action (for example checking freshness of files) but the longer time it will be until the next batch can start. For small projects (< 300) modules everything is so fast the queue size is rarely bigger than 5.

Finally about cancellations, the ShakeQueue contains a cancellation action which is currently only called by shakeRunInternalKill. The cancellation action is created when a new batch is created in the workerThread and checks to see which of the actions in the batch have already completed and requeues the ones which didn't.

Let me know if anything there is unclear but it reflects the thought process we went through when deciding to use the queue and it works very well for me in practice.

[pepeiborra]

How would your answer change if shakeRun could be called concurrently?

[mpickering]

I don't know exactly. How are you imagining it would improve things now you understand our motivation?

[pepeiborra]

My understanding is that the queue exists for the following reasons:

1. To avoid suboptimal cancellations (typecheck cancelled by hover, only to be restarted)
2. To enable retries (thus no need for a "global" kick)
3. To enable background work

All of those three stem from the single-threaded nature of shakeRun. I think all of 1,2,3 would be non issues if it was possible to either:
a. add work to the existing shakeRun without restarting it, or
b. run multiple shakeRun executions in parallel

This is only speculation, I have no idea if this restriction can be lifted at all. But perhaps worth exploring?