Auto-memoization for pure functions – how to decide when it pays off?

[u/Bro8an]

Im currently working on a compiler for my own programming language. I want the compiler to automatically memoize pure function calls, but only when it actually improves performance. The challenge: how does the compiler decide whether caching a specific recursive call (e.g., self(x-1) and self(x-2) in fibonacci) will save more time than the memory overhead? tracking how many times a function recieves the same input isnt an option as this requires all recieved inputs to be saved. too many saved calculations can cause finding the right result for a function call to be slower than the actual calculation. so the memoization table shouldnt get to big. naive fibonacci should be memoized but simple addition for an example should not be memoized. do you have any ideas?

[u/P-39_Airacobra]

what’s wrong with an explicit keyword? the problem is there’s never going to be a “better” solution, it’s always going to be a trade-off between space and speed

[u/flatfinger → u/P-39_Airacobra]

For some reason, some people are allergic to the idea that programmers are sometimes know more about some things than compilers possibly can, or that in situations where two approaches to accomplishing a task would both be acceptable, having a programmer pick one that will be used unless or until a programmer decides to change it may be better than having a compiler switch arbitrarily between them on subsequent builds.

[u/Financial-Flan1682 → u/flatfinger]

It's not that. It's that people are constantly trying to ensure that the programmer doesn't have to think about anything except the problem at hand. A huge amount of programming research has gone into this.

To be clear, not agreeing with the mentality. Just explaining it.

[u/jonathanblakes → u/Financial-Flan1682]

Which research are you thinking of specifically? I'm interested because I don't see what's wrong with knowing about the system as well as the problem at hand. We are all capable of comprehending many things simultaneously.

[u/Financial-Flan1682 → u/jonathanblakes]

Nothing specific and more talking about the space in general.

Everything about modern programming language design is about not having to think as much about the construction of programs. Garbage collection pushing towards ARC so there are no pauses, a push towards immutable data, no way to directly allocate, using pipe operators more and more across languages (to be fair, this is much more elegant, but it also follows a specific pattern in language design).

[u/catladywitch → u/Financial-Flan1682]

to be fair, the push for automatic memoisation in general comes from React, where it solves a real problem

[u/P-39_Airacobra → u/Financial-Flan1682]

I agree with you on the semantics side, but I think there’s a line to draw at optimization, where meaning is identical. Making the programmer explicitly memoize is a different matter from making the programmer explicitly free objects.

[u/flatfinger → u/Financial-Flan1682]

The vast majority of potential optimization decisions Just Don't Matter. If a piece of code would represent 0.01% of a program's execution time, even slowing it down by an order of magnitude would increase overall execution time by less than 0.1%. Neither the programmer nor implementation time should spend any significant effort on such decisions.

If there's an approach that will Just Plain Work, and performance of that approach Just Wouldn't Matter, having the programmer specify that approach and have an implementation use it will take less programmer thought than trying to ascertain whether an implementation might substitute a different approach whose semantics might fail to satisfy application requirements.

[u/P-39_Airacobra → u/flatfinger]

exactly. I would spend seconds at most deciding whether to use a “memoize” keyword. I could spend much more time than that trying to guess what the compiler will choose (and no, I don’t trust that it will always be correct). Compilers are very difficult to predict, and my program’s memory usage is something I’d like to predict

[u/flatfinger → u/P-39_Airacobra]

Yup. Additionally, having compilers attempt to automate such decisions will make it extremely difficult to do any kind of controlled benchmarking tests. Benchmarking often requires evaluating performance in conditions that are somewhat different from those a real application may face, and benchmarks will often present optimization opportunities that would not be present in a real application. An optimization that would sometimes make a benchmark run 50% faster, but would not be applicable in a real application, is worse than useless.

[u/arthurno1 → u/Financial-Flan1682]

Yes. But that is a wrong trail. Programming is about not just solving domain specific problems, but also about solving them efficiently on the hardware on which the solution runs. It means that there isbalways that low-level implementation leak into the problem domain. In order to efficient, i.e. obtain maximal speed or minimal usage of computing resource, one has adapt the problem solution to the hardware at the hand.

It is true that we can automate a lot of things, which compilers are for, but the automation is always a trade off between generalization and specific optimizations.

Also, as someone said, problems can be solved in different ways, and sometimes a particular solution might benefit some particular hardware more.

[u/Bro8an → u/P-39_Airacobra]

its not just space vs speed. when the cache grows too big because the functions inputs are two random searching through a cache everytime a function is called gets slower over timer. so actually its speed vs speed + memory

[u/snugar_i → u/Bro8an]

if the cache is a hash map, searching should be O(1) regardless of size

[u/yjlom → u/snugar_i]

A hashmap typically has far fewer slots than possible keys, so eventually you get collisions, to solve those you must search a list or tree or something and then it becomes O(log n) or O(n).

[u/snugar_i → u/yjlom]

Then you re-hash it to have more slots so that it gets under the specified load factor again, which is still amortized O(1)

[u/omega1612]

From what I know there are two main ways for this:

1) use/write a jit compiler

2) collect at runtime the info, then pass it back to the compiler and recompile based on it.

Other options are to create some heuristics depending on what tradeoffs you want to have. Is it fine if it optimizes unneeded functions? Or should it be conservative and avoid it as much as possible?

There is a reason why compilation optimization is it's own field.

[u/Bro8an → u/omega1612]

the problem is to find a clear distinction between function with predictable inputs and random inputs. functions with random inputs wont be affected by the optimization at all but slowed down because of the caused overhead when going through the cache. my current attempt would be to only optimize recursive functions that call themselves at least twice. fib(n) = fib(n-1)+fib(n-2) would be effected. factorial(x) = x * factorial(x-1) would not be effected.

[u/yjlom → u/Bro8an]

A less general but much more powerful optimization: if it only calls itself with n - k as argument, with k constant, you can make it tail recursive by giving it an array of size #k as an extra argument. From there you can do TCE, bringing it down to O(n × #k).

If the resulting function is multilinear however, each step becomes a matrix-vector multiplication, which means that computing the whole function becomes a matrix exponentiation, followed by a matrix-vector multiplication, which brings it down to O(log n * (#k)³).

In the usual case where #k is small, that's a massive gain. There's tons of little specific optimizations like this that one can reach for.

[u/Both-Personality7664]

I'm not sure how the compiler can know what the compute/memory tradeoffs are in general except by running the code in question with the relevant inputs, and at that point you can just have the compiler do the memoization for you - I'm not sure you're going to get much better than an explicit declaration, say at function definition, that this function should be memoized over this set of inputs.

[u/glasket_ → u/Both-Personality7664]

Heuristics and profile-guided optimization are the typical ways you'd deal with an optimization like this with unknowns. Still, an explicit keyword makes sense because the compiler isn't guaranteed to get it right (outside of very thorough profiling).

If OP wants to avoid having people abusing it by throwing it on everything, then using an ugly name or tucking it into a special namespace will cause a surprising amount of people to just avoid it. People tend to treat __builtin_thing or builtin::thing like they're plague-ridden.

[u/SoSKatan → u/Both-Personality7664]

In theory it could do some fuzz tests of different inputs and measure if the time cost of the call is much slower than a cold (not in cpu cache) memory read than maybe it could be a good candidate, assuming there is amble free memory.

Problem is now your compiler has a halting problem, what if the function being tested never returns or a takes 2 years to calculate

[u/SoSKatan]

So with modern CPUs, memory latency is very very slow compared to computation.

I mean consider a funny counter example: simple addition.

In theory one could memoize the result of addition. Want to know what 5 + 10 is? Well let’s first check the memory slot that is mapped to, if it’s empty then do the work and write the result.

So by memoizing this, you are making it slower by several orders of magnitude.

A pure function means no IO, which means it’s pretty much just computation. So this is only a useful optimization for extremely extremely slow functions. It’s best to leave it as a per function opt in thing that’s done by hand.

[u/AnArmoredPony → u/SoSKatan]

a pure function may require multiple memory look ups

[u/Jwosty]

I agree with the others that it probably isn’t something you necessarily need your compiler to automatically figure out for you but… if you’re gonna do it, dynamic runtime profiling (like how tiered JIT compilation works) might be workable

[u/AdvanceAdvance]

In order to do this implicitly, you need to measure. Were I doing this with the constraint that there is no "calibration run" to make the determination, I would add a memoization for every pure function call. Using a LIFO (starvation) queue, look at the number of calls for the speed/space tradeoff. If memoization is doing well, expand the queue size, else toss two starving entries and permanently reduce the queue.

That said, memoization makes much sense for "find me the customer information for this nonce, you know, the one I just asked about" or "computer the next thirty moves of this subpatch of a game of life." Most of time, it doesn't make sense as few functions are really pure.

[u/Bro8an → u/AdvanceAdvance]

thanks<3 this is a realy helpful!

[u/Bro8an → u/AdvanceAdvance]

i like your attemp but one thing im realizing is, that a you say the cache is getting smaller when it performs badly (to reduce overhead) but a smaller cache would cause even more cache misses which causes a feedback loop where a slidly worse performing cache vanishes entirely.

[u/mamcx]

This is basically the question a query optimizer must answer every time.

Is even harder there, because the QE must look at the ever-changing (or assume is) data and reorder, on the fly, without being worse that just execute the query as-is.

The main difference with "static optimizer" is that is easier, but also, it need more "pessimist" view and not worry for small-ish improvements.

After building one, roughly:

• There is a "known" set of patterns that often improve performance, so you look at that

This is basically all.

You see this often in interpreters/advanced compilers every time they talk about "unrolling, loop fusion, ..." etc. Because this a mature field with a know set of what are the ones that gives more profit just do it them is decent enough.

• You have a budget

This is the answer for "save more time than the memory overhead". Is necessary to put the limits in a budget based in decent heuristics, common usage patterns, what the machine loves, etc and you just check against that. Else, you "deoptimize" and then let the developer be in charge of add some annotation to know when taking always the optimization (with thing like assert for example).

---

More on point, is "know" that tail-calls can be optimized very well and in fact reduce memory and cpu.

Basically anything that can be turn into a procedural variant is worth the effort just because (so things like iterators).

Other "known" is that you can do:

http://www.pathsensitive.com/2019/07/the-best-refactoring-youve-never-heard.html

I think at most both of this will be more than enough and can't think right know of anything else that could very surely good results(?) but in my domain of query compilers recursion and such is not a focus.

[u/Toothpick_Brody]

In general this might be impossible to solve, but I was hoping some commenter might at least know a useful heuristic! 

[u/Mickenfox]

I know it's probably not you want, but I'm curious how well just hooking it up to a LLM would work.

[u/matthieum]

I want the compiler to automatically memoize pure function calls, but only when it actually improves performance.

I assume you want a cache, rather than keeping every single pair of arguments -> result in cache for the lifetime of the program?

If so, you're going to need to answer some questions:

1. How many entries should be cached?
   • Should the cache "bound" be specific per function, or for all functions?
   • In the former case, should the bound be specific to an instance of a generic function, or shared across all instances?
2. What eviction policy should the cache use?
3. Possibly, what container/look-up method should the cache use?
4. Possibly, should the cache be thread-local, or global?

So many variants, so many usecases, it feels like users may want a say, no?

[u/DLCSpider]

I don't think there is a way around explicitness. It's not only a question of "should this be memoized at all?" but also about how much history you keep. Think of number to string conversions: a simple if input == lastInput then return cached might greatly benefit performance and memory because the check is cheap, even if it fails every now and then. But a hash table lookup for the last n computations is probably too slow and may keep dead strings alive.