🧠 educational Persistent incrementality in Rust
https://rust-glancer.github.io/blog/persistent-incrementality-in-rust/59
u/Sharlinator 4d ago
The most common example of incremental computing is probably UIs that redraw/relayout/recompute only the parts of the view that are actually affected by a state change.
21
40
u/afdbcreid 4d ago
This is really interesting to me as a rust-analyzer maintainer, more than all other your posts about Rust Glancer.
People have been long asking about only-disk-backed backend for Salsa or rust-analyzer. And we've been rejecting that, on the assumption that:
It will downgrade performance too much.
Building on (1), we cannot enable it by default, so it will have great complexity.
There is still a lot to optimize in rust-analyzer's memory consumption.
(3) is still true, though less - but we expect to save multiple gigabytes per project with the forthcoming rowan rewrite. We expect memory usage by then to stay on the realm of few hundred megabytes on medium-large projects - probably more than the 100mb Rust Glancer aims for, but still very manageable and maybe not worth optimizing like that.
For a while I strongly believed (1) and (2), but neither side has proof. If Rust Glancer can really be as efficient with on-disk storage, that'd be a really convincing argument to do that.
Note - I say if, because I'm not yet convinced it is. rustc has a lot of small queries that often need to be revalidated and retrieved. I need to look more on your code, but it seems you do a lot of these (e.g. lowering types for declarations) on-demand during inference. Performance-wise, if it can hold the same perf bar it's interesting - but I'm afraid this cannot be 100% correct.
21
u/popzxc 4d ago
Hey, happy to hear that :)
I'm working on a clean integration of Ajika and currently ~halfway through, and I'll make sure to include proper comparisons on several projects to see both the average query execution time (initial and repeated), as well as other relevant stuff.
That said, a few things:
When I say that the performance matches rust-analyzer, I talk about _perceived_ performance. E.g. right now I have my experimental (dirty) version of Rust Glancer running locally, and it does feel instant. In benchmarks, it will be slower, though, e.g. completions can take 30-50ms more (approximately, don't remember the exact number) but it still feels instant; references might take 100ms more, but again it does not feel like a hiccup.
I'd say that memory-based mode might still matter for people without NVME SSD, since this whole idea is based on assumption that your disk is pretty fast. Though if Ajika will look convincing, I think it will be possible to add first-class support for the in-memory backend.
18
u/afdbcreid 4d ago
The point about the speed of the disk is important, but I mainly talked about (1) - as the code is growing more complicated (and especially with a lot of macros, where even rust-analyzer struggles to do realtime completion), performance might degrade.
Furthermore, rust-analyzer was never meant to be just a LSP, and now it also practically isn't - people are using it to power tools analyzing Rust code, either in watch-like mode (like IDE, either from a real IDE or not) or in cold-start mode. Both cases analyze a lot of code unlike an IDE, which can make quite a difference in how fast queries are.
As a simple test, the best IDE feature to approximate this is "Find all references", because it require inferring many bodies if you search for a common name (historically rust-analyzer had really difficult time to find all references to
new(). I fixed that via a cool heuristic - that was one of my first PRs to r-a when I started becoming a regular contributor - but it was only a workaround for this cases and similar, the fundamental problem remains the same and is the same for any language server).
21
u/ezwoodland 4d ago
Surprised your list didn't include typst's incremental library: https://crates.io/crates/comemo
14
u/popzxc 4d ago
Interesting, didn't know about this one! I knew about Salsa and I knew that I need something similar but with persistence, so my search was focused only on alternative solutions that offer it. This one seems to be memory-only, but I really like the minimalistic API and ergonomics of it (though I worry that for a long-living application one would want more control over low level stuff).
9
u/epage cargo · clap · cargo-release 4d ago
Still doing requirements gathering but this looks like its in the general direction that I'm needing!
How does the on-disk caching handle clean up? Does it remove all results that weren't reached by the current operation? Or does it keep all results and have some kind of GC?
I'm wondering if there is a good way to handle interleaving the running of multiple versions.
Would there be a way to conditionally cache to disk? My application currently always caches but there is a request to not always cache the failure of an external operation as the operation might have changed.
5
u/popzxc 4d ago
> How does the on-disk caching handle clean up? Does it remove all results that weren't reached by the current operation? Or does it keep all results and have some kind of GC?
It has several layers: after operation ends, the output values that are no longer needed are reported to the storage and storage cleans them up, plus storage does maintenance passes that compress packs / remove dead values / performs cleanup based on configuration (e.g. storage limits and retention deadline). Maintenance is a part of the query lifecycle, so there is no separate GC thread.
> I'm wondering if there is a good way to handle interleaving the running of multiple versions.
You mean multiple versions of the application running in parallel? In Rust Glancer I solved that by having a lock on the cache when it's active, and just claiming a new instance if the current one is busy. So you might end up with several copies of state, but on restart your "previous one" can be picked up by the new instance.
> Would there be a way to conditionally cache to disk? My application currently always caches but there is a request to not always cache the failure of an external operation as the operation might have changed.
Right now, if the operation is successful, it will be cached. But I think that adding it is possible, I already have the retention policy so it shouldn't be hard to make it possible to override it per execution. (the tricky part is that if the intent is "retry next time" it should also invalidate all the reverse dependencies without failing the query completely, but that also should be solvable)
4
u/epage cargo · clap · cargo-release 4d ago
It has several layers: after operation ends, the output values that are no longer needed are reported to the storage and storage cleans them up, plus storage does maintenance passes that compress packs / remove dead values / performs cleanup based on configuration (e.g. storage limits and retention deadline). Maintenance is a part of the query lifecycle, so there is no separate GC thread.
My current on-disk cache only retains the last run so if you toggle between fundamentally different runs, you are always getting cache misses.
So it sounds like this has the same issue?
You mean multiple versions of the application running in parallel? In Rust Glancer I solved that by having a lock on the cache when it's active, and just claiming a new instance if the current one is busy. So you might end up with several copies of state, but on restart your "previous one" can be picked up by the new instance.
I'm not talking about concurrent access from multiple instances (though that is also a concern: I can't serialize application runs) but multiple versions running back to back. Maybe I misunderstood but I thought that changing versions would cause a cache flush/miss.
4
u/popzxc 4d ago
Well, there are three version identifiers: Ajika schema version, your app schema version, database revision. Your app schema version is provided by you.
So if you can identify the kind of the application run somehow (maybe with extra metadata), you can in theory have a unique identifier for a "run kind" when you open the database (e.g. `v1-run0` / `v1-run1`), which would make the cache unique to this run and it won't collide internally. But at this point it becomes a problem of routing to the corresponding database.
Otherwise, yup, Ajika is not really designed to hold several versions of answer per query / hold multiple incompatible datasets.
5
u/SkiFire13 4d ago
I wonder the reason behind the choice of writing immediately to risk any result, and having to reload them when needed for the next query. Wouldn't it be faster if some data (up to a memory limit) was cached in RAM, so that it's faster to access for the next query? Or is the additional complexity not worth it because the OS caching of the file makes it not matter too much in practice?
3
u/popzxc 4d ago
Well, data is not _immediately_ released, it's reused within a query, otherwise it would be too wasteful.
Adding something like an LRU cache is possible, but I want to design this part more before I introduce it. IMHO, one of the more interesting directions could be having more controls on the particular query retention strategy, so that you can decide which queries are "hot" (and should be kept in memory when possible) and which queries are "cold" (and safe to offload ASAP).
OS caching of the file seems to help, but I think still it's a good direction to investigate; I just postpone it until I actually migrate Rust Glancer to Ajika.
3
u/Thick-Pineapple666 3d ago
I love your style of writing. Great structure, storytelling keeps me hooked, very interesting even though I never touched that problem you're trying to solve.
6
1
u/Mrblahblah200 4d ago
This is awesome! So I’m assuming the reason rust-analyzer is so memory heavy is because it uses salsa and that stays in memory? Maybe we need a ajika rewrite of rust-analyzer
1
u/danielv134 3d ago
I am currently using rust analyzer from an experimental CLI to do analysis of references across a project. This is in many ways a worst case scenario: no disk, no long term client, so no r-a daemon, so no cache in memory. Obviously not a long term strategy, but in the mean time it emphasizes that even on a small project (but using std) the r-a phase takes a while to run.
Here is the challenge for persistency: in a simplified condition of a reasonably fast, always half empty disk, does the number of times a particular release of std gets analyzed approach "just once"?
2
u/popzxc 3d ago
Yup, sysroot (std, core, alloc, proc_macro) is analyzed once per stored cache (and obviously per target version).
1
u/danielv134 3d ago
The "per stored cache" is exactly what I'm concerned about.
To quickly analyze many (possibly unrelated and small) projects, I'd want to amortize the analysis of sysroot across the independent projects.
In principle, a public sysroot should be analyzed once per target, then its analysis delivered via rustup.
Can we have one stored cache per workspace (including sysroot), and then have the project workspaces reuse (instead of redo) the sysroot's cache?
2
u/popzxc 3d ago
I think it's technically possible, and I'm also thinking about adding that in the future, but not right now -- even if you'll create a meant-to-be-shared instance of Ajika, it currently expects exclusive ownership. This is (relatively) easily fixable, though, we could add a read-only mode where the database after creation will be locked by N readers, and unlocking it would require to free it.
Then this could work by first creating a database with sysroot analysis, and then have 1 database for sysroot + 1 app-specific one. The next improvement could be adding sub-databases to Ajika, so that you don't end up having 2 database objects (meaning nested `run`s).
So I can see it working, nothing in the architecture prevents that, but it's not implemented yet.
2
u/danielv134 3d ago
I'm looking at (current github) glancer. Sharing is prevented by many causes, a few of them are easily fixable (per-workspace cache, paths and hashes that depend on things that do not affect analysis results).
I see one blocker that is harder to fix: CrateRef depends on position of Crate in the current workspace.
This can be worked around for sysroot by assigning the sysroot crates fixed positions. I'm going to try this for my own purposes.
A more principled fix would use stable crate IDs instead, but that would affect engine internals.
2
u/popzxc 3d ago
Yup, the current architecture is significantly affected by hand-rolled caches which have grown well beyond the scope where it doesn't affect the architecture too much (which is mentioned in the blog post). Significant chunk of it will be removed with the Ajika introduction (there is a bunch of stacked PRs there -- migration is in progress). And there is a bunch of stuff I don't really like but as you said it is fixable.
For now, as long as fs artifacts do not exceed 1gb per instance, I don't prioritize the storage reuse. My main priorities for now are speed and completeness. And luckily indexing is not really a concern right now; on the Ajika-migrated version indexing Bevy (one of the toughest beasts in the ecosystem) takes <10s (obviously, not including proc macros, since these are not supported yet), and this cache is reusable, so it's a one-time cost.
But yeah, these issues are known, and eventually I'll get to them.
2
u/danielv134 3d ago
Yeah, using a shared .cache directory, removing the unnecessary path/hash participants, and hard coding the sysroot CrateRef positions reduced the latency I see (on a new small project) by ~8x. Let me know if a PR would be welcome.
100
u/popzxc 4d ago
Heya. Long time no see. A lot of effort went into this post, so I hope you like it.
As usual, the post is handwritten, so all the mistakes are my own; I believe that imperfect English is more pleasant to read than polished but bland LLM speak.
BTW, new release for Rust Glancer is coming soon (tm), and this post is _very_ relevant here. I'm very excited about the upcoming release :)