Richard Feldman (Feb 09 2022 at 01:54): Richard Feldman (Feb 09 2022 at 01:54):what if we had a memoization primitive that works like a generalized version of Elm's Html.lazy?
basically it's a way to memoize function calls faster than is currently possible in Roc. The API would be:
Memo.run : Memo a b, a, (a -> b) -> { answer : b, memo : Memo a b }Memo.empty : Memo * *the way it works is:
Memo.run three arguments: a Memo, a 1-argument function, and an argumentMemo.empty, then it calls the 1-arg function passing the given arg, and returns both the return value as well as a (non-empty) Memo which stores the function, the arg, and the return valueMemo, it compares the given function and the given arg to the ones stored inside the Memo; if they're the same, then it doesn't bother calling the function and instead returns the stored answer directlyMemo, or if the function is different, then it works the same way as if you'd given it Memo.empty (call the given function with the given arg, return the result and a Memo which stores them)This would have to be a new builtin because, by design, neither shallow reference equality nor comparing functions for equality are operations Roc supports. However, in this particular use case, it seems harmless to do both because it's only a performance optimization; you can't actually use this API to change the behavior of your program - aside from making it run faster or slower.
This builtin would be useful in some of the GUI stuff I'm working on right now - for example, directly using it to implement an equivalent of Html.lazy, which as far as I can tell is not currently possible, even with platform tricks (meaning in the absence of this builtin, something else would have to change for lazy to be implementable - e.g. how code generation works).
Richard Feldman (Feb 09 2022 at 01:57):anyone have thoughts on this idea?
Richard Feldman (Feb 09 2022 at 02:01):(incidentally, Memo.empty would have no performance overhead or require any special conditional treatment; it would just have the equivalent of a null function pointer, so the comparison always fails no matter what real function you give to Memo.run)
Ayaz Hafiz (Feb 09 2022 at 02:07):What if equality is instead optimized to catch the case where you’re comparing two of the same pointers?
My worry with this is the proposed behavior is that it will be difficult for application authors to reason about when their values are referentially equal and when they aren’t, because memory allocation isn’t something we expose to the end user or guarantee a consistent behavior for (at least today).
Additionally, I see an interest for user space software to use some derivatives of this idea - for example suppose I want a variable maximum size for my memoization cache, or I want to use a different caching policy (LRU/FIFO/etc). If users are likely to do this anyway, or at least not discouraged from, it may be better to see if we can optimize for the general case.
More seriously, comparing by reference could always break referential transparency - that may not be something Roc wants!
Richard Feldman (Feb 09 2022 at 02:22):What if equality is instead optimized to catch the case where you’re comparing two of the same pointers?
I think that would already be the case (e.g. if the pointers are the same, we don't have to bother following them to know that whatever they point to is also equal) - but in the case of reference equality, we actively want different behavior: if the pointers are different, we don't even bother traversing to see if their contents happen to be the same, just proceed as though they're different
Richard Feldman (Feb 09 2022 at 02:24):More seriously, comparing by reference could always break referential transparency - that may not be something Roc wants!
yeah, that's a major reason I don't want to have a reference equality primitive in the language (like OCaml does) :big_smile:
however, this API can't break referential equality. If you call Memo.run passing the same arguments, it will return the same (in the structural equality sense, as usual) answer every time, guaranteed. Elm's lazy does reference equality, and it indeed has some edge cases that don't appear anywhere else in the language, but that's also necessary to unlock performance that isn't achievable any other way!
Richard Feldman (Feb 09 2022 at 02:27):My worry with this is the proposed behavior is that it will be difficult for application authors to reason about when their values are referentially equal and when they aren’t, because memory allocation isn’t something we expose to the end user or guarantee a consistent behavior for (at least today).
this is true, although it's also true that performance optimization in every language inevitably requires looking under the hood into internal implementation details that weren't necessary to think about before, so I don't think that concern disqualifies a performance optimization tool in the same way it would most APIs
Ayaz Hafiz (Feb 09 2022 at 02:32):but in the case of reference equality, we actively want different behavior: if the pointers are different, we don't even bother traversing to see if their contents happen to be the same, just proceed as though they're different
But why not both? That way a user gets the benefits of really fast equality checking when two objects are the reference, without losing out on returning a cached result when objects are structurally equal - in my mind, many things that are worth caching are much more expensive to compute than structural equality
Richard Feldman (Feb 09 2022 at 02:37):hm, I was going to point out a benefit, but then I realized it doesn't actually work :laughing:
Ayaz Hafiz (Feb 09 2022 at 02:38):I don't think that concern disqualifies a performance optimization tool in the same way it would most APIs
I definitely agree it shouldn't disqualify it - I just wonder if there is a better way to expose this kind of optimization in the language besides a single builtin API
Richard Feldman (Feb 09 2022 at 02:38):the idea was that if we can just do a reference equality check, then we don't need to traverse pointers, which in turn means we don't need to hold onto a reference - meaning the thing we're storing doesn't need to have its reference count incremented because even if it gets freed, we can still do the reference equality check
...but then I realized this could cause its refcount to be 1, meaning it would be eligible for in-place mutation, and therefore a reference equality check could return false positives, which would be very bad :sweat_smile:
Richard Feldman (Feb 09 2022 at 02:40):so actually, realizing that I think sells me on it being a structural equality check for the arg
Richard Feldman (Feb 09 2022 at 02:40):(if nothing else)
Richard Feldman (Feb 09 2022 at 02:40):so then the new primitive would be needed only for checking function equality
Richard Feldman (Feb 09 2022 at 02:41):which in the general case seems like a risky proposition, but in this particular case seems harmless
Ayaz Hafiz (Feb 09 2022 at 02:42):well function equality can only be checked referentially.. at least unless we can prove certain functions halt, which is probably out of the question :)
Richard Feldman (Feb 09 2022 at 02:44):as far as alternative designs go, I'm open to suggestions!
Ayaz Hafiz (Feb 09 2022 at 02:53):I think the need for referential function equality convinces me that this as a builtin is a good idea
What if Memo captures the function that it's memoizing over? That is the API would look something like
Memo.empty : (a -> b) -> Memo a b # Maybe Memo.new?
Memo.run : Memo a b, a -> { answer: b, memo: Memo a b }
My thought here is that usually one would want to memoize different arguments to the same function - and if I want to cache the computations of different arguments/functions, I can do so with this API by having the function (a -> b) be something like { apply, val } -> apply val, which to me in some ways makes it more explicit that I might be memoizing both over different functions and different arguments to those functions.
Richard Feldman (Feb 09 2022 at 03:02):interesting!
Richard Feldman (Feb 09 2022 at 03:06):so one use case I can think of which might benefit from this design is:
let's say I have a huge list (like 10K elements) of items I want to render. One of the things a user can do is to delete an item from the middle of the list. (We don't necessarily have to actually remove it and shift everything over; we can just mark it as "deleted" and then not render it.)
how can we performance-optimize that scenario? Ideally we want to be able to cache the renderings of the other 9999 elements, such that we don't have to re-render every single one of them just because the list as a whole changed
Richard Feldman (Feb 09 2022 at 03:07):actually nm I don't think we need to memoize to make that fast
Richard Feldman (Feb 09 2022 at 03:08):as long as we have the concept of leaf nodes updating in-place without requiring that the parent re-render, which is already a separate thing I'm looking into, so nm that's not a good example
Ayaz Hafiz (Feb 09 2022 at 03:13):one example I can think of is if you have something that needs a network fetch to render, but you want to reuse the last fetched data until some TTL expiry - that use case might be a little bit different though since it requires a bit more work for caching
Last updated: Jun 16 2026 at 16:19 UTC