Durable Incrementality

I love incremental-compute systems. The idea is so cool, a lot of the implementations are really interesting to read about. Definitely feels like one of those under-appreciated techniques.

It’s cool that’s there’s quite a lot of it going on rust land. There’s this, I believe the rust compiler has a little differential dataflow thing, Frank McSherry has done a stack of cool stuff with the timely and differential dataflow libraries-some of which lives on in Materialize db.

> The second Salsa property is laziness. When changing the input, one can go and eagerly mark reverse-dependencies as “this might have changed”. This could create redundant work — if two modifications arrive one-after-another in a row, invalidating everything twice is wasteful. Or there might be some top-level queries whose results are no longer interesting

Er, what? If you get 2 modifications before actually forcing the computation, the second won't have to mark anything since it will quickly see "this node is already dirty" and stop propagating the dirty flag upward.

The interesting optimizations to me are 1. when should nodes share a dirty flag, and 2. for what simplicity level should you just always redo the calculation (this is highly dependent on what kind of interpreter or compiler/runtime you're evaluating with).

I wonder how this compares to comemo [1] [2], they're both memoization frameworks with "tricks" to limit invalidation.

The trick in comemo's blog post is to make the dependencies fine-grained, by tracking and only comparing what parts of them are actually used; while the trick here is to have functions depend on other outputs instead of the root input, so changes don't propagate all the way (+ laziness). But I'm sure some comemo functions are memoized on incremental computations, and salsa has some way to e.g. not recompute the entire AST when the source code changes.

I suspect there's also an issue where most incremental computations tend to invalidate way more than they need to; like if someone accidentally creates a function which takes a big array and an index, and only access the element at or a few elements around that index, but the anything in big array changing will cause it to be recomputed. So is there a system to profile what gets recomputed every time a query is run?

[1] https://laurmaedje.github.io/posts/comemo/

[2] https://github.com/typst/comemo

A bit more context in lobste.rs discussion: https://lobste.rs/s/te7x8n/durable_incrementality

I believe that tracking the number of potentially-changed direct inputs per node would be sufficient, would have better performance and would require fewer workarounds like durabilities. Further, it wouldn't turn O(N) updates into O(MN) ones (where M is the total size of your computation and N is the nodes affected by an update).

However, it would require dependencies to be tracked in both directions, so it's probably not possible to engineer it into Salsa, which seems to only track dependencies from consumer to producer.

I was going to blog about this design in detail, but never got around to it.

This seems very similar to Signals [1] in Angular.

[1] https://angular.io/guide/signals

I really like that "just check if the function output changes" trick. It's so simple but I never thought of it myself.

Is the computation graph derived from Rust code directly? Or does the user need to do the graph building?