Stream: t-compiler/wg-rls-2.0

Topic: rust-analyzer is slow :-(


matklad (May 20 2019 at 21:27, on Zulip):

I've finally wrapped up my course about Rust, so I have more time to hack on the analyzer.

I am doing some refactorings now, and observing that it is pretty slow. Will hopefully look into that. I have three hypothesis:

Jeremy Kolb (May 20 2019 at 21:40, on Zulip):

The diagnostics thing is definitely real. I've also noticed sometimes that things get so bad it hangs up new line insertion.

matklad (May 20 2019 at 21:42, on Zulip):

And this is the third hypothesis: slow diagnostics shouldn't block interactive features...

I wonder what's the best way to design for that? I guess, in the main loop, we should have two thread pools:

Florian Diebold (May 21 2019 at 07:09, on Zulip):

I think Chalk integration is at least a big part of it, and I think I'll switch it to my fuel branch

matklad (May 21 2019 at 07:26, on Zulip):

Yeah, but I am also pretty sure that we don't do a good job prioritizing queries. For example, when you open the new project and ask for document symbobls, you have to wait until the whole project is processed, but, iirc, this needs only syntax.

I guess, in addition to fuel, we should have "weights", which allow us to selectively slow-down particular subsystems, to make sure that only relevant functionality is degraded, and not the whole server

Jeremy Kolb (May 21 2019 at 13:29, on Zulip):

Am I right in remembering that we do not support the cancellation request? Is it possible that cancellation requests are coming through and we aren't processing them so things are getting backed up?

matklad (May 21 2019 at 13:32, on Zulip):

We don't support client-initiated cancellation, but I think it shouldn't be relevant

matklad (May 21 2019 at 13:33, on Zulip):

I've done some quick profiling and the picture I see is that chalk is sometimes quite slow

matklad (May 21 2019 at 13:33, on Zulip):
       2937ms - diagnostics
           2243ms - implements_query
matklad (May 21 2019 at 13:34, on Zulip):

There are also quite some queries which take a loong time themselves, but don't have long deps listed

matklad (May 21 2019 at 13:35, on Zulip):

I think this is because thouse queries are actually blocked on that one slow chalk query

Laurențiu Nicola (May 21 2019 at 13:35, on Zulip):

8568ms - crate_def_map_query

Laurențiu Nicola (May 21 2019 at 13:35, on Zulip):

is this normal?

matklad (May 21 2019 at 13:35, on Zulip):

For the initial load -- yeah

Laurențiu Nicola (May 21 2019 at 13:36, on Zulip):

11447ms - diagnostics

Florian Diebold (May 21 2019 at 13:37, on Zulip):

yeah, some Chalk queries can basically take arbitrarily long as long as we don't limit them

matklad (May 21 2019 at 13:38, on Zulip):

We probably want to add cancellation support to chalk at some point as well

Florian Diebold (May 21 2019 at 13:38, on Zulip):

... maybe we should just drive the chalk solver loop ourselves :thinking:

Florian Diebold (May 21 2019 at 13:39, on Zulip):

if we did, cancellation and fuel would be easy

matklad (May 21 2019 at 13:39, on Zulip):

would this be enough?

Like, if the loop yields next solution, there can be arbitrary computations inside (nested loops, for example)

matklad (May 21 2019 at 13:42, on Zulip):

@Florian Diebold could you also create "chalk is slow" issue in the chalk repo? :-) You've looked into it way more than I did, so you should better understand what "slow" means. I hope if we put this on the radar for the chalk developers, they'll come up with some nice optimizations :-)

Florian Diebold (May 21 2019 at 13:42, on Zulip):

they are usually fast, though, I think. I'm not very familiar with the details, but when it needs to solve a nested goal, it just does one step there and then returns a 'no results yet, might have more' error (https://github.com/rust-lang/chalk/blob/3238c6d0bc7d09b6eebe069ebd47dfabae787082/chalk-engine/src/logic.rs#L51)

Florian Diebold (May 21 2019 at 13:43, on Zulip):

hm yeah, maybe I should try to reproduce some slow cases in the chalk test harness

matklad (May 21 2019 at 13:45, on Zulip):

Just to clarify, the slowness is due to chalk exploring some exponential search space, and not due to the fact that some simple optimizations (aka accidentally quadratic) are missing?

Florian Diebold (May 21 2019 at 13:45, on Zulip):

I think in general, they know this though -- it's what e.g. https://github.com/rust-lang/chalk/issues/217 and https://github.com/rust-lang/chalk/issues/80 are about

detrumi (May 21 2019 at 13:46, on Zulip):

My guess would be that Chalk is really inefficient in searching some goals, instead of it getting too much input

detrumi (May 21 2019 at 13:46, on Zulip):

Yeah, the non-enumerable goals problem is one where Chalk is looking at Sized(?T) first, which is a really bad search order

Florian Diebold (May 21 2019 at 13:47, on Zulip):

the cases I've seen are mostly that you have something like where ?0: Foo, ?0: Send and it tries enumerating every single type that implements Send, even though there might be just a few that implement Foo; or variations of that

Florian Diebold (May 21 2019 at 13:48, on Zulip):

which is exacerbated by us having lots of cases where there is no solution, so in our case ?0: Foo might actually have no solution and it really tries to enumerate all types

detrumi (May 21 2019 at 13:49, on Zulip):

Not sure if changing the ordering would help in that case

Florian Diebold (May 21 2019 at 13:50, on Zulip):

if we know that a certain clause has no solutions at all, we can immediately stop, right?

detrumi (May 21 2019 at 13:51, on Zulip):

Ah yes, it'll know whether Foo is implemented, and only search through the Send part if some of those impls depend on that

Hoang Luu (May 21 2019 at 13:57, on Zulip):

This seems similar to RDBMS's join problem, can we solve it same fashion? I.e. estimating number of impls per trait

Florian Diebold (May 21 2019 at 13:58, on Zulip):

that's the direction that https://github.com/rust-lang/chalk/issues/80 goes in, I think

matklad (May 21 2019 at 13:59, on Zulip):

https://github.com/frankmcsherry/blog/blob/master/posts/2018-05-19.md#addendum-2018-05-21-treefrog-leapjoin is an interesting read on the topic

matklad (May 21 2019 at 13:59, on Zulip):

of joins

Laurențiu Nicola (May 21 2019 at 14:03, on Zulip):

pasted image

Laurențiu Nicola (May 21 2019 at 14:03, on Zulip):

ugh, so slow

Jeremy Kolb (May 21 2019 at 14:04, on Zulip):

you're right I just flipped trace on and cancellation is pretty rare

Laurențiu Nicola (May 21 2019 at 14:10, on Zulip):

could running cargo check block typing (e.g. adding a newline) in RA?

Jeremy Kolb (May 21 2019 at 14:12, on Zulip):

No I don't believe that it does. I've seen this happen with cargo watch disabled.

Jeremy Kolb (May 21 2019 at 14:12, on Zulip):

As well as no issue when running cargo check while typing

Laurențiu Nicola (May 21 2019 at 14:13, on Zulip):

I just saw RA thinking that cargo check is running while it wasn't

memoryruins (May 21 2019 at 14:15, on Zulip):

is ra_cli's rust-analysis a good way to bench parts of ra?

memoryruins (May 21 2019 at 14:15, on Zulip):

ran valgrind massif and callgrind on top of it as it analyzed ra's repo an hour ago. looks like it captured a good bit of data. I won't be available to look closer until this afternoon though

memoryruins (May 21 2019 at 14:16, on Zulip):

attaching a zip containing data and two screenshots (of kcachegrind and massif-visualizer) if anyone can make better use of them in the meantime ra-massif-callgrind.zip

Edwin Cheng (May 21 2019 at 15:25, on Zulip):

@Laurențiu Nicola Currently the toggling of animation about cargo check is just a simple string comparison to '[Finished running'. So maybe it fail to parse it. However, it should not related to this issue.

Laurențiu Nicola (May 21 2019 at 17:45, on Zulip):

@matklad did you intend to disable Chalk in https://github.com/rust-analyzer/rust-analyzer/commit/26463f189ff75e92990375ee5ae08d3903d39e66?

matklad (May 21 2019 at 17:56, on Zulip):

absolutelly nor

matklad (May 21 2019 at 17:57, on Zulip):

that one time when you decide that it's fine to send a trivial PR without bors...

memoryruins (May 21 2019 at 19:20, on Zulip):

ran valgrind --tool=callgrind ~/projects/contribute/rust-analyzer/target/release/ra_cli analysis-stats on a handful of crates, such as RA itself, cranelife, crossterm, and regex.

memoryruins (May 21 2019 at 19:21, on Zulip):

for each project, ra_parser::parser::Parser::nth is calling a handful of functions from ra_mbe::subtree_source that make-up for the majority of instruction reads/calls, drastically outnumbering everything else rust-analysis is doing.

memoryruins (May 21 2019 at 19:21, on Zulip):

tried rust-analysis on a fresh cargo new <crate> without any changes. it reported 696965 calls to ra_mbe::subtree_source::SubTreeWalker::walk_token from WalkCursor::current, 9689599 calls in WalkerOwner::get from within is_token_joint_to_next, 15248879 calls in WalkerOwner::get from within <ra_mbe::subtree_source::SubtreeTokenSource as ra_parser::TokenSource>::token_kind in an empty fresh project. running a perf record also has ra_mbe::subtree_source::WalkerOwner::get at the top of the list of overhead.

memoryruins (May 21 2019 at 19:32, on Zulip):

disclaimer: today is the first time I've used callgrind, so although the above stood out, I might be missing something :)

matklad (May 21 2019 at 19:34, on Zulip):

I think callgrind gives you precise statistic regarding the number of calls, but is not very precise when it comes to real time measurnments

Laurențiu Nicola (May 21 2019 at 19:52, on Zulip):

I assume that includes rust-src? Is the standard library code mbe-heavy?

memoryruins (May 21 2019 at 19:56, on Zulip):

makes sense, the manual said to focus more on the instruction reads/Ir in the source view, but the above functions stood out in that regard too.

memoryruins (May 21 2019 at 19:58, on Zulip):

rust-src sounds like a possibility. I need to look in what all analysis-statsas a command includes. noticed it used in another PR for a bench and rolled with it

Last update: Nov 12 2019 at 16:20UTC