Incremental Computation Graphs

6 points by marcecoll

polywolf

See also https://thunderseethe.dev/posts/lsp-base/ which, while longer, i think flows a bit better as an introduction to the algorithm

(Also see also https://git.sr.ht/~polywolf/driver/tree/8b6396478fbba0fdf2b495d1bb0b90600db2c2ae/item/packages/driver-engine/src/context.rs#L183 where I implemented this algorithm myself!)

I always find it interesting the slightly different takes on the core red-green concept:

For each dependency we track also what was the changed-at revision of the dependency when we depended on it.

My implementation doesn't need this? And I can't find where in the rest of the algorithm we'd depend on that.

Also missing from most discussions is a twist I added to make the changed-at checking return false more often, by eagerly re-querying dependencies that may have changed in order to not re-run a potentially expensive function with no actually-changed deps.

(I should probably figure out what Salsa does someday, because that seems to be the "canonical" version of red-green. Maybe I'll write more on this but meh I don't have that much to add)

marcecoll

Thanks for the extra references! I wrote this a few months ago when I was understanding the algorithm for the first time and it was written in a very rough way haha. I've been revisiting it as I am using it again for a VCS+CI system I'm building.

I found the algorithm very nice at the start of the year and very elegant. I think more people should know about it. One thing that I don't think I express very well is how nice it is that once you describe your computation in terms of these cacheable computation graphs a lot of the manual orchestrating I used to do before to keep things up-to-date goes away. The whole data model is very very nice to work with.

And I can't find where in the rest of the algorithm we'd depend on that.

changed_at basically tells you when this was computed the last time. Let's say you do a query at time T, you check and the last time that query value was verified was at T - 1, so it could be out of date. You then check its dependencies and to each of the dependencies you check if dep.changed_at < q.verified_at, if that's the case then the value is up to date since none of its dependencies has changed since you last verified it. That's how in my version of the algorithm at least you stay lazy and avoid recomputation.

kchanqvq

Would this be useful? https://github.com/kchanqvq/lwcells It also handles some problems like glitch-free propagation, but I guess that's more relevant for GUI than compilers.