4 ms·
I love the memoization/caching stuff. I know someone will blurt out “Haskell!” or whatnot, but I wish memoization was more first class in popular languages. It
by Waterluvian 4y ago
I love the memoization/caching stuff.
I know someone will blurt out “Haskell!” or whatnot, but I wish memoization was more first class in popular languages. It’s a great way to maintain performance without having to reason about the implementation details of your code. A decorator in the stdlib gets pretty close.
- cozzyd 4y agoNow I'm wondering, can this be done in c++ with variadic templates?
- dataflow 4y agoThe problem with memoization too easy is that you generally want a sane cache policy for the problem, and that's generally problem dependent. Otherwise you blow up program memory usage.
- aastronaut 4y agoI only need invalidation policies if i want to cache functions that aren't referentially transparent.
- dataflow 4y agoYou also need invalidation policies if the number of items you cache might end up too large in practice. That has nothing to do with referential transparency.
- aastronaut 4y agotbh i never ran into such an issue with my applications and it sounds to me like a physical constraint: i don't expect to be able to keep something cached in memory that is larger than the available memory. if i would see myself optimizing for the best "maxsize" property (assuming lru_cache), then i would rather change to a probabilistic data structure like a bloom filter or cuckoo filter (or whatever the contemporary approach there is). can you elaborate the problem a bit more please?
- dataflow 4y ago> can you elaborate the problem a bit more please? Simplest example: take any function you memoized with @functools.memoize. The more it's called, the the bigger the cache can grow. Run it on a stream of inputs and you're practically guaranteed to run out of RAM. This obviously has nothing to do with referential transparency.
- aastronaut 4y agomemoization is a means of simple optimization to speed up a program, just like GP wrote. you exchange the cost of executing a function with the cost of memory utilization. say you memoize a function that is referentially transparent, needs 10secs to finish its execution and return its result (eg. factorial). then the memoization would just cache the arguments plus the return value to reduce the 10secs into a simple comparison. the worst that could happen is a missed hit which would invoke the expensive function again - just like what would happen without the optimization. that isn't a big concern, as the function is referentially transparent (without side-effects). memoization lives in this perfect mathematical world where memory for maxsize entries will always be available. but if your expensive function is referentially opaque, but still pure, then you can't only depend on the arguments of the function, but you need to take more context into account and the additional context requires a form of cache invalidation. the context can be counter-based (only re-evaluate every nth call), time-based (re-evaluate at most once every t time, throttling or debouncing), or both (only allow for at most n/t re-evaluations over time, rate-limiting) etc. in my book that isn't memoization anymore, it's just caching. and you need to define a policy that defines its invalidation. if your stream of inputs exceeds the available memory, it lives outside the perfect mathematical world and i'd guess you have other problems than a speed optimization through memoization. you'd then need to consider space-efficiency and i would argue that memoization is the wrong kind of optimization for that problem.
- zasdffaa 4y agoIf 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 agoNobody 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 agoIf 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."