5 ms·

If your lang has 1st class functions (edit: inc. closures[1]) you can write memoisers trivially and use them like var fm = add_memoisation_to(f); // used g

If your lang has 1st class functions (edit: inc. closures[1]) you can write memoisers trivially and use them like var fm = add_memoisation_to(f); // used generics for c#/scala Done this in javascript, scala, C#. Can't remember how I handled params, it's not a big deal. @dataflow: you build in cache limits, either by time or space, and instrumenting so you can get feedback (eg. hit rate, cache size, whether the cache turnover indicates thrashing). Very little code, a page or two. [1] and if it doesn't, just use objects. Slightly less streamlined code but otherwise identical semantics.

dataflow 4y ago
Nobody is claiming you can't come up with some way to limit the cache size if you wanted to. What I'm saying is (a) you usually need to have the user do something about the cache (most people want to just set @memoize and forget about cache invalidation), and (b) the cache policy (and note this isn't necessarily just about the size of the cache, but about which entries are evicted) is frequently problem-dependent, and a general-purpose one may not end up being all that useful. I can say from personal experience that, while I cache stuff all the time, the number of times I recall seeing @functools.memoize (or the equivalent in any language) used in any real-world code (i.e. not classroom exercises) is exactly zero, whether in my own code or that of anyone else—despite the fact that caching is incredibly common. Just look at common Python libraries (even the standard library itself) and count how many times they use @memoize anywhere. It will be minuscule if not exactly zero. And the fact that it is not widespread is not due to lack of knowledge of the technique. Notice this is the same reason why you don't see a general-purpose "tree" or "graph" class in many languages' standard libraries [1]: you certainly can make one, but design has strong dependence on the actual problem you're solving, and it's hard to come up with a general-purpose one that's handy and useful. Of course, some people try anyway, and it occasionally gets used, but nowhere remotely as often as people need trees or graphs. Same thing here. [1] https://stackoverflow.com/a/2982420 https://stackoverflow.com/a/2982420
- zasdffaa 4y ago
  If you want other than LRU or time-to-expire then I take your point, but those are IME the most common types, therefore support it. The cache in python's functools are default 128 items, LRU (from memory). If you really want specialised caching policy then you can have that as an extra object/function passed in to the cache (edit: a predicate or predicate closure), but I've never needed it. LRU all the way for me and most others. > Just look at common Python libraries (even the standard library itself) and count how many times they use @memoize anywhere. Obviously! They are general purpose so they can't make any guess, and if they need caching that's up to the user, who can then add @functools.memoize in one line. That's what it's there for! > And that fact is not widespread is not due to lack of knowledge of the technique. IME it very much is. > Notice this is the same reason why you don't see a general-purpose "tree" or "graph" class in many languages' standard libraries But then caching is far simpler than graphs, and anyway from your link: "(Out of more than a dozen projects in various domains I have been involved in so far, I recount two which actually needed graphs.) So I guess there was no really big pressure from the Java community in general to have a Graph in the Collection Framework."
zo1 4y ago
Have been using easy decorator memoization in python for at least a decade. This is not new and far from impossible to do using probably even older versions of python. I implemented it in 2.5 IIRC.
- zasdffaa 4y ago
  I was responding to "was more first class in popular languages". I know about python's functools lib and its memoisation decorator. Point was, if you didn't have it and wanted it, it's easy; no need for the language to provide it.
  - robertlagrant 4y ago
    Don't let this guy see math.tau.
    - zasdffaa 4y ago
      This guy sees your point and this guy does indeed wonder why it's there when 2*Pi will do. But if it's about python the answer is simple - unlike many other languages python does fold constants, but does't fold expressions using variables even if the variable is never changed so there's an unavoidable cost unless you write out the value literally, or have it as a constant. Or - in PEP 628 - it's just a bit of a larf https://peps.python.org/pep-0628/ https://peps.python.org/pep-0628/ Perhaps this guy should grow a sense of humour.
      - robertlagrant 4y ago
        > Perhaps this guy should grow a sense of humour. Agreed!
- merlincorey 4y ago
  It's a built-in decorator now called `functools.cache`[0]. [0] https://docs.python.org/3/library/functools.html#functools.cache https://docs.python.org/3/library/functools.html#functools.c...

dataflow 4y ago

Nobody is claiming you can't come up with some way to limit the cache size if you wanted to. What I'm saying is (a) you usually need to have the user do something about the cache (most people want to just set @memoize and forget about cache invalidation), and (b) the cache policy (and note this isn't necessarily just about the size of the cache, but about which entries are evicted) is frequently problem-dependent, and a general-purpose one may not end up being all that useful. I can say from personal experience that, while I cache stuff all the time, the number of times I recall seeing @functools.memoize (or the equivalent in any language) used in any real-world code (i.e. not classroom exercises) is exactly zero, whether in my own code or that of anyone else—despite the fact that caching is incredibly common. Just look at common Python libraries (even the standard library itself) and count how many times they use @memoize anywhere. It will be minuscule if not exactly zero. And the fact that it is not widespread is not due to lack of knowledge of the technique. Notice this is the same reason why you don't see a general-purpose "tree" or "graph" class in many languages' standard libraries [1]: you certainly can make one, but design has strong dependence on the actual problem you're solving, and it's hard to come up with a general-purpose one that's handy and useful. Of course, some people try anyway, and it occasionally gets used, but nowhere remotely as often as people need trees or graphs. Same thing here. [1] https://stackoverflow.com/a/2982420 https://stackoverflow.com/a/2982420

zasdffaa 4y ago
If you want other than LRU or time-to-expire then I take your point, but those are IME the most common types, therefore support it. The cache in python's functools are default 128 items, LRU (from memory). If you really want specialised caching policy then you can have that as an extra object/function passed in to the cache (edit: a predicate or predicate closure), but I've never needed it. LRU all the way for me and most others. > Just look at common Python libraries (even the standard library itself) and count how many times they use @memoize anywhere. Obviously! They are general purpose so they can't make any guess, and if they need caching that's up to the user, who can then add @functools.memoize in one line. That's what it's there for! > And that fact is not widespread is not due to lack of knowledge of the technique. IME it very much is. > Notice this is the same reason why you don't see a general-purpose "tree" or "graph" class in many languages' standard libraries But then caching is far simpler than graphs, and anyway from your link: "(Out of more than a dozen projects in various domains I have been involved in so far, I recount two which actually needed graphs.) So I guess there was no really big pressure from the Java community in general to have a Graph in the Collection Framework."

zo1 4y ago

Have been using easy decorator memoization in python for at least a decade. This is not new and far from impossible to do using probably even older versions of python. I implemented it in 2.5 IIRC.

zasdffaa 4y ago
I was responding to "was more first class in popular languages". I know about python's functools lib and its memoisation decorator. Point was, if you didn't have it and wanted it, it's easy; no need for the language to provide it.
- robertlagrant 4y ago
  Don't let this guy see math.tau.
  - zasdffaa 4y ago
    This guy sees your point and this guy does indeed wonder why it's there when 2*Pi will do. But if it's about python the answer is simple - unlike many other languages python does fold constants, but does't fold expressions using variables even if the variable is never changed so there's an unavoidable cost unless you write out the value literally, or have it as a constant. Or - in PEP 628 - it's just a bit of a larf https://peps.python.org/pep-0628/ https://peps.python.org/pep-0628/ Perhaps this guy should grow a sense of humour.
    - robertlagrant 4y ago
      > Perhaps this guy should grow a sense of humour. Agreed!
merlincorey 4y ago
It's a built-in decorator now called `functools.cache`[0]. [0] https://docs.python.org/3/library/functools.html#functools.cache https://docs.python.org/3/library/functools.html#functools.c...