Memoization of complex calculations across runs / partial source code changes

[leopoldaschenbrenner]

Here's a pattern that comes up in a project I'm working on

• complex_variable = [heavy computation, lots of code in heavy model, takes a while to run]
• simpleComputation(params) = [simple computation that uses complex_variable, say params.multiplier*complex_variable]

The heavy model for complex_variable will only change every once in a while. At the same time, it would be nice to be able to iterate interactively with simpleComputation (eg, try with a bunch of diff input params iteratively, without having to rerun complex variable every time).

So in addition to just memoizing/caching for a given run of squiggle, could be very useful to cache across runs. (Or even, at least in this case, caching across runs would be more useful.)

[leopoldaschenbrenner]

I.e., cache across partial source code edits

[quinn-dougherty]

There are three approaches for memoization broadly. Any one of them is a sizable epic, plausible for 0.5 or 0.4.x

wasm-bindgen

#990 showed how to import wasm modules, which are compiled artifacts from a rust codebase, into rescript.

• Perhaps a memoization utility written in rust could be used, so that it's happening at the wasm level.
• Perhaps for-free caching from the cached crate would work nicely. We'd have to widen the area of the wasm surface for that to be useful, though.

Service workers

One interesting web feature for a fine tune over caching stuff is service workers. https://developer.mozilla.org/en-US/docs/Web/API/Cache

Resources:

• https://webbureaucrat.gitlab.io/articles/writing-service-workers-in-rescript/
• https://developer.mozilla.org/en-US/docs/Web/API/Service_Worker_API/Using_Service_Workers

Pure rescript

We could roll a memoization library in pure rescript.

Some ideas

• https://github.com/dwwoelfel/ocaml-lru-cache

[umuro]

Memoization needs both internal and external cache

Importing "cached" would be feasible if one could work on it.

However, I think that for memoization going out side for persistent storage, ending up accessing redis, etc is too much.

Cons of external cache

• Being tied up to the external processes will indeed slow down the runtime too much. Every function call will end up causing a redis call for example. 100% of the time external calls is a disaster.

Cons of internal cache
But even for a quick table in JavaScript, there are some problems.

• JavaScript does not have a call to report available memory size. So we cannot discard cache items based on memory.
• JavaScript heap size limit seems to be 1.3GB in general. This might be too limiting. Too little cache means constantly trashing the cashe without being able to use it. That means one has to find the cache size by trial and error.

Overall I don't see a immediate solution that would work fast

A quick in Rescript solution might be like this:

• Use FIFO
• Limit the FIFO size (.e.g 1000 entries) so that JavaScript does not run out of memory.

In fact a true solution should be a hybrid solution to maintain a good performace. Not one of the options.

• Lookup in memory FIFO
• If not found then use external cache
• If something goes out in FIFO then put it to the external cache

Thus we need both the internal solution and bridging to sth like "cached" above. It is not internal or external. It has to be both.

The problem is that only internal or only external cache will bring down the whole performance. It has to be a cascaded hybrid solution.

[berekuk]

In ReducerProject, each source file is run separately, so a partial solution for this will be available by splitting the heavy parts which change less frequently into their own files.

[leopoldaschenbrenner]

Yeah, some context on a common use case:

• file1: some heavy model, doesn't change that often, outputs "key_intermediate_variable"
• file2: some light calculations using "key_intermediate_variable"

So the useful thing here would be to make "key_intermediate_variable" cached - then could rapidly iterate on the light calculations in file2 (would be basically instant), rather than waiting ~30sec each time for "key_intermediate_variable" to be recomputed.