Memoisation

Sometimes, we have pure functions that will return the exact same output for a given input. Instead of having to re-calculate these values again and again, we may want to store these values so that they returned quickly, instead of having to recompute the result again. This only makes sense when we are calling the same method many times with the same inputs, and we have the memory resources to keep track of the results.

This technique is known as memoisation, which caches the result of a function call based on the input arguments. Let’s take a very simple example of calculating a number in the Fibonacci sequence:

function fib(n)
    if n == 1
        return 1
    end
    return n * fib(n-1)
end

We can create a functor to combine the functor and the storage of the results in a dictionary:

struct CachedFib
    cache::Dict{Int, Int}
end

# Create an argument-less constructor
CachedFib() = CachedFib(Dict{Int, Int}())

function (f::CachedFib)(n)
    if n == 1
        return 1
    end
    cache = f.cache
    # Check if the cache contains the result
    if haskey(cache, n)
        return cache[n]
    end
    # If not, actually calculate the result
    result = n * f(n-1)
    # Store the result in the cache
    cache[n] = result
    # Return the result
    return result
end

We can now create this functor and use it to calculate our values:

cached_fib_fn = CachedFib();
println(cached_fib_fn(4))

24

Note that the backing cache does not have to be a dictionary, or even stored in main memory, one can just as easily use a disk cache as well for results that take a long time to run. This pattern can be very useful for long-running calculations that may be interrupted, such as a HPC job. Using the disk as a cache can easily allow you to recover from stops, avoiding having to recalculate everything from the beginning.