3 ms·
> How do you implement `memoize`? > I think that you basically can’t, in JavaScript. Or, more accurately: I can’t think of a way to do it.[1] Oh, this is a ca
by crdrost 2y ago
> How do you implement `memoize`?
> I think that you basically can’t, in JavaScript. Or, more accurately: I can’t think of a way to do it.[1]
Oh, this is a case for WeakMaps right?
const MemoCache = new WeakMap();
function memoize(f, x) {
const cache = MemoCache.get(f) || new Map()
MemoCache.set(f, cache)
if (!cache.has(x)) {
cache.set(x, f(x))
}
return cache.get(x);
}
Oh wait:
> 1. You could create a global memoization map keyed on the function that you’re calling, but this would actually have different semantics than I’m imagining. If I said `memoize(f, 1) + memoize(f, 1)` I would expect those to each invoke `f`, because instances of `memoize` shouldn’t share results. Why not? Because this is a fake example, and a global memoization is a different (easier!) thing than per-call-site memoization.
Like I get what you're saying but you could just cache the call site too?
const MemoCache2 = new WeakMap();
function memoize2(f, x) {
const callsite = new Error().stack
const macro_cache = MemoCache2.get(f) || {};
const micro_cache = macro_cache[callsite] || new Map();
macro_cache[callsite] = micro_cache;
MemoCache2.set(f, macro_cache)
if (!micro_cache.has(x)) {
micro_cache.set(x, f(x))
}
return micro_cache.get(x);
}
I admit that this is something of a trickery though, but I mean, it's trickery specifically to work around that this person doesn't want to write `const my_f1 = memoize(f), my_f2 = memoize(f)` in some location on the screen. Precisely because people who write JavaScript are not accustomed to macros, they are not expecting `memoize(f, 1) + memoize(f, 1)` to be a proper memoization expression, they aren't expecting weird stuff with weakmaps and inspecting stack traces to identify call sites and all that.
- kragen 2y agoi think reflecting on the stack is a valid solution to the problem and one that henry probably didn't think of. technically i think you need to extract just the first frame of the stack though. also reflection is often slow so it wouldn't be surprising if this ended up being a solution that was too slow to be useful
- ianthehenry 2y agothis is a very funny way to do this, thanks! i was thinking of using the (deprecated but still widely supported(?)) `caller` property but was sad that it wouldn't admit multiple memoization dictionaries per calling function (also wouldn't work at the top-level but, like, who cares). but using the stack trace is great. i mean, you know, this isn't really... this isn't really a thing that you would ever want to do, but i am glad that life found a way
- kragen 2y agoit might be; you'd have to benchmark it to be sure
- taeric 2y agoI'm intrigued on why you would want those two calls to memoize separately? I'm sure there are reasons it could be needed, such that I'm not trying to argue against it. Genuinely curious to see a situation it would be desired.
- kragen 2y agoa more plausible example than memoization is something like a polymorphic inline cache, where the cache can be very small and therefore fast to search but tends to be different at different callsites
- taeric 2y agoMakes sense, I was thinking this is largely recreating L2 caches and such. Where you don't mind that they would memoize the same data, but the expectation is more that each caller would have a small subset they are specifically using over and over.
- lupire 2y agoIf you knew the answer, why did you ask the question?
- saghm 2y agoSometimes it's nice to abstract a place where you need the answer from the way you determine the answer; that's basically why functions exist in the first place! Later on, if you decide that you want to tweak the way the implementation works, you don't need to do it literally everywhere.
- taeric 2y agoI thought of an answer after asking. Still curious if there are others.
- kragen 2y ago
- loa_in_ 2y agoWait, can't you just set the property on the function object itself to accomplish this?
- layer8 2y agoStack is not the same as the callsite. (It’s technically also a non-standard property.)