[afpx]

I was given a programming interview once where the interviewer gave me a DP problem (which I didn't know at the time), and he failed me because I used a cache instead of memoization. Asides from being inelegant, what are the downsides to caching?

[Jtsummers]

Memoization is caching so that's a strange reason to fail someone. You cache based on the function call and its arguments.

  SOME_FUN = dict(base_cases)
  def some_fun(a, b, c):
    if (a,b,c) in SOME_FUN: return SOME_FUN[(a,b,c)]
    result = some_fun(a - 1, b - 1, c) + some_fun(a, b, c-1) # or whatever the recursive calls would be
    SOME_FUN[(a,b,c)] = result
    return result

That's it. Some languages (Python, Lisp) make it easy to take the naive version and wrap it (Python decorators are useful here) so that you don't have to write that code above. That's what the @cache decorator in functools does for you. You can memoize the naive version without needing to actually write a specific memoized version.

[hinkley]

No, this is what forty years of semantic dilution gets you.

[Jtsummers]

https://en.wikipedia.org/wiki/Memoization

> In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls to pure functions and returning the cached result when the same inputs occur again. Memoization has also been used in other contexts (and for purposes other than speed gains), such as in simple mutually recursive descent parsing.[1] It is a type of caching, distinct from other forms of caching such as buffering and page replacement. In the context of some logic programming languages, memoization is also known as tabling.[2]

It includes citations so I won't bother repeating them. Memoization is caching, there is no confusion about this in the literature.

[hinkley]

Because Wikipedia has never been wrong and doesn’t suffer from dilution.

The distinction I am making is that caching is not memoization.

> It is a type of caching, distinct from other forms of caching

Distinct. As in not to be confused with.

[Jtsummers]

If I wrote "a square is a rectangle" would you also waste time shouting that rectangles aren't squares? I didn't write that all rectangles are squares. Nor did I write that all caching is memoization.

Even your quote doesn't support your quibbling. It says that memoization is distinct from other forms of caching. Which does not mean that it is not a form of caching.

EDIT: Removed a particularly rude bit.

[vilanye]

All dogs are mammals, but not all mammals are dogs.

[hinkley]

If everyone starts talking about dogs every time you mention mammals, eventually you will get touchy about it.

Yeah, dogs are great. But so are cats, and llamas.

[hinkley]

Global shared state. High memory overhead. Evictions mean that the beginning of your call can see potentially different values than the end, and most of us write code like this as if it is transactional. We cannot handle a user’s account being closed or upgraded to an admin in the middle of a transaction. So using a cache to keep refetching the user data instead of passing it with the call graph is fraught (and makes unit testing terrible).

As a concrete example, my coworker was trying to walk a DAG with many leaf nodes that were repeated (think dependency tree). He used a cache to do this. It had bugs (2 I knew, but 6 I found). It was one of three large calculations we made at startup, and it should have been the least of these. But it ate memory like candy and added a lot to our start time which was slowing down deployments.

So I replaced it with a DP solution that just looked like normal code, reducing startup memory by ~80 MB and start time by half. By walking the tree and making a list of all the nodes in dependency order and then processing them once, after the list was compiled. And for the microservices and dev tools where we ran this same code the startup time became negligible.

Part of the problem is that the library we used did not like being called recursively, so you had to dance around reentrancy bugs and that cost time and space. But a linearized run has no recursion.

Edit to add: I realize now that I’ve left the conclusion ambiguous.

His two main sins were one, that the cache lived beyond the useful lifetime, and two, that even with the cache some amount of post-processing was required. By unrolling the tree and running each calculation once I reduced the post processing by about 3/4 and climbing as the tree grew in width and height.

[mekoka]

Memoization is deterministic caching, meaning that the structure is a perfect stand-in for a deterministic function. The "determinism" of the function itself is relative to some agreed upon lifespan, during which if you feed it some input, the corresponding output is guaranteed to always be the same (e.g. until the next reboot, the runtime of the main program, the span of a function call, etc). Within that timespan, the result of computations can be reliably stored and retrieved from the cache. When it's exceeded, the function's corresponding cache also goes stale and should be considered unreliable and to be discarded.

Note that in the case of memoization, the guarantee of determinism (and associated lifespan) is attached to the function, not the caching structure. Unlike some other caching approaches that rely on a replacement policy.