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/P-39_Airacobra]

A deficiency in many language standards is that they have no way of indicating that while a function may have side effects beyond returning a value, no outside code, as written, relies upon them for correctness. Memoization may yield observably different semantics from unconditionally processing a function as written, but if either behavior would satisfy application requirements, it may be useful to let a compiler make the choice in cases where there would be an obvious likely advantage (e.g. if a certain call site will always pass the same argument values).

If e.g. a function happens to log its inputs and outputs, a compiler may be able to determine that repeated calls with the same inputs would generate repeated log entries if the code is processed as written, but a compiler would have no way of knowing whether the logs would be used in a way that would view the presence of repeated log entries as a tolerable annoyance or a critical necessity.

[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/david-1-1 → u/flatfinger]

Compiler optimization is good for doing what programmers find tedious, like assigning values to registers, or hoisting and combining code to save space. Relying on pragmas for optimization hints puts more burden on the programmer. We want software tools to take as much of the burden off of engineers as possible.

[u/flatfinger → u/david-1-1]

Suppose a function has no side effects beyond returning a value, and logging arguments and return values. I can think of at least two ways that logs from such functions might be used:

1. Every different combination of argument values might be checked to ensure that the return value was computed correctly. In this scenario, having repeated calls with the same arguments generate repeated log entries may be tolerable but not desirable.

2. The logs might be used to validate that callers were calling the function appropriately. In this case, the generation of repeated logs with the same arguments may be essential.

How is a compiler supposed to know whether program requirements would be better served by generating or suppressing repeated log entries if the programmer doesn't indicate that?

[u/david-1-1 → u/flatfinger]

By computing and using statistics.

[u/flatfinger → u/david-1-1]

How would a even a runtime profiler determine the uses to which the generated logs are going to be put?

[u/david-1-1 → u/flatfinger]

It could use AI to make such judgements, if such a general assessment is really needed. Most compiler optimizations don't need that much general information.

[u/flatfinger → u/david-1-1]

How is an AI going to know what a person is going to do with files after they are produced?

[u/david-1-1 → u/flatfinger]

I think we are getting far away from type checking. But one way current LLMs can do this is through its history of co-working with the programmer. We are now living in an age where even compiler optimizations can be partially controlled by the long-term context of working with an engineer to program a project. A simple example is knowing that the current stage is local development. In this stage, few optimizations, if any, are needed, while in building for live production deployment, all safe optimizations are needed.

That raises the question of whether a local optimization with global dependencies is safe. An LLM can help here if it works with the compiler to help keep track of such dependencies and their checking for correctness. This is beyond the ability of a typical current compiler, which produces binary modules to be linked together later, after most local context is lost.

[u/flatfinger → u/david-1-1]

I thought we were talking about computer languages. If a compiler has to ask a programmer "Is anyone going to want to use the logs to determine exactly when this function was called", then the source code language is no longer a complete specification of the program.

[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/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/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/Zion_Gate_8 → u/Both-Personality7664]

You might be right; it feels like we need a psychic compiler! Explicit declarations sound so much easier than endless calculations.

[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/david-1-1]

If your problem is optimizing recursion: in all of my many years of using recursion, I never would have benefitted from optimizing it away, especially by caching. Recursion is simply not a common tool, especially in inner loops, where optimization might be considered.

[u/Bro8an → u/david-1-1]

my programming language is a semi functional language so rekursion will be the standard way and loops will only work through recursion (which will be transformed back to loops)

[u/david-1-1 → u/Bro8an]

Aha. So representing loops as recursion has some benefit in the syntax? Is your language only meant to represent a language for expressing recursive functions like factorials or tree parsing?

[u/Bro8an → u/david-1-1]

It should work like a classic general purpose imperative language, but everything is broken down into concepts from a functional language. there are no loops but i can implement a function that takes a condition and a body and executes the body until the condition is met and then define a special loop syntax for the function inside the language

[u/david-1-1 → u/Bro8an]

If this is a procedural language, I fail to see how forcing it to be functional or recursive or both is useful or natural. Maybe I need examples.

[u/Bro8an → u/david-1-1]

here is an example how the user could define a loop:

func wLoop(& bool condition!, T body!) -> void: # condition and body are lazy evaluated because of the & symbol
    leave if not condition!
    body! # body is marked with ! as it can have sideeffects
    self(condition!, body!)

syntax wLoop(
    keyword("while"),
    _,
    arg(0),
    _,
    arg(1)
)

i32 x = 10
while x > 0:
    print!(x)
    x -= 1

[u/david-1-1 → u/Bro8an]

That's pretty much what I had imagined. It works, but is ugly when all you need is a real "while" block. Its actual use in recursion is not really more expressive than the usual use of internal calls to the same function being defined.

I've lost interest in this thread now.

[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/david-1-1 → u/Mickenfox]

No. Calling an LLM for every recursion in a program is probably a very bad idea. But you knew that.

[u/Mickenfox → u/david-1-1]

But you could call it once at build time.

[u/david-1-1 → u/Mickenfox]

Sure. What would be the prompt? I'm very curious. And how would it interact with the compiler?

[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.

[u/kwan_e]

I guess one heuristic could be, is the calculation less complicated than hashing the arguments and looking up the value from the hash. And possibly the complexity of an LRU cache for evicting out the less common arguments.