Design: memoizing functions with composite type arguments

General Usage
1

Hi, I have been troubled by a specific design problem for a few days. The problem is as follows:

I have a function f

struct foo
   data::Matrix{Float64}
end

function f(x::foo)
   ...
end

Since f is fairly expensive, I want to memoize its results using Dict. However, changing x.data will not change its hash. In this sense, function f may return wrong results because of memoization.

Any suggestions to resolve this problem?

Since x.data can be very large, I do not want to memoize the results with x.data as keys. The best approach I can think of is to make x.data immutable, which I don’t know how to do.

2

You can either

  1. Write a method for Base.hash that uses data. The default just falls back to object_id(x).

  2. Avoid changing values.

While 1. is an immediate fix, and helps you reuse results for structures that share the same matrix, think about 2. in addition. It sometimes leads to more transparent code.

3

Thanks, I think I will try to avoid changing values. However, I have a question regarding the first approach: How does hash works for a composite type? Why changing x.data does not change hash(x).

4

Look at the sources, eg

@edit hash(f, zero(UInt))

and you will see what is going on. The fallback method for composite hashes does not actually look into the object.

You can also try

if you don’t want to implement hashing yourself.

2 Likes