Hacker News Reader

Comment by j_m_b | Hacker News Reader

|We implemented automatic memoization of top-level computations using a source-to-source translator. This is particularly beneficial in our use-case where multiple policies can refer to the same shared value, and we want to compute it only once. Note, this is per-request memoization rather than global memoization, which lazy evaluation already provides.

I would like to know more about this. What is a request exactly? An API call? If so, when an existing policy is changed, do the memoization tables have to change as well? How are the memoization tables shared? If this is running on a cluster, I would imagine that lookups in a memoization table could be a bottleneck to performance.

View on HN

For example, let's say that one of the things you want to compute is the number of friends of the current user. This value is used all over the codebase, but it only makes sense in the context of the current request (because every request has a different idea of "the current user"). So this is a memoized value, even though in the language it looks like a top-level expression.

Memoization only stores results during a request. It starts empty at the beginning of the request and is discarded at the end, and it is not shared with any other requests. It's just a map that's passed around (inside the monad) during a request.

Thanks for the response. Just trying to expand my brain here =), so I have a followup question.

I always thought of memoization as storing the parameters to, and result of, a function call in a memotable. Doing some quick research, I came across this definition of memoization from NIST that sounds more general "Save (memoize) a computed answer for possible later reuse, rather than recomputing the answer." What I understand from what you said is that when a request is processed, it produces a map that is passed around for the duration of the request.

Something like:

Request -> (some processes) -> memoized map -> Policy Filters

How is the memoized map reused?

The memo table (map) is a bit of state that is maintained throughout the request's lifetime. When we compute a memoized value, it is inserted into the map, and if we need the value again we can just grab it from the map instead of recomputing it.

The "automatic" bit is that we insert the code that consults the map so the programmer doesn't have to write it. The map itself is already invisible, because it's inside the monad. So the overall effect is a form of automatic memoization.

Reply on news.ycombinator.com