Memoization and Value types

129 views
Skip to first unread message

Travis Keep

unread,
Mar 27, 2023, 11:15:01 AM3/27/23
to golang-nuts
I have this package: https://pkg.go.dev/github.com/keep94/sqroot, which computes square roots to arbitrary precision.  The Number type is a value type that represents a square root value. Early on it made sense to make Number be an immutable value type because it represents an immutable value such as sqrt(5).  

However, now I want to add memoization to square root values. I have done this in a private branch, by adding a WithMemoize() method to Number that returns a new Number with memoization turned on.  I have made the memoization multiple goroutine safe so that Number types still appear as immutable numerical values.  

However, I am not sure that memoization works well with Value type semantics.  For instance, if I have two Numbers, x and y, and I set y = x and continue to use x, y will see any future memoization done for x because I implement memoization with pointers behind the scenes.  But, y = x implies that y gets a snapshot of x and won't see future changes in x.  Moreover, I will never be able to add a method to Number that returns information about memoization progress because that would break immutability of the Number value type.

To solve this dilemma, I could change the API to be pointer based, by accepting and returning *Number instead of Number.  Then I could say that Number does not support assignment directly. The advantage of using *Number is that if x and y are *Number and I set y = x, it is clear that whatever happens to x will happen to y because they point to the same instance. However, that would be a huge breaking change.

Any suggestions on what to do?

Kevin Chowski

unread,
Mar 27, 2023, 9:06:39 PM3/27/23
to golang-nuts
If you are willing to include some global state to your package, you could always have memoizing logic occur outside of the Number type. That is - you could still have every Number be passed around by value, but for calculating sqrt you'd check some threadsafe global state and either return a pre-calculated value or calculate+cache it.

The obvious downside is that cleaning up this pre-calculation is tricky. A naive implementation would cause all sqrts to be cached for the rest of the program execution. A more complex one would involve some sort of expiration.

Eltjon Metko

unread,
Mar 28, 2023, 3:59:18 AM3/28/23
to golang-nuts
I am a little confused by this. Memoization does not belong with the type but with the action. So in your case the sqrt would have a memoization and not the Number. 
Reply all
Reply to author
Forward
0 new messages