Fastest way to do memoization?

General Usage Performance
1

I have a two-argument function, for which I want to cache the results. Currently I use a Dict to store the previous results. The performance is OK, but profiling said that a lot of time is taken by finding the index.

    dict_index = Base.ht_keyindex(S.fval, (i,j))
    if dict_index >= 0
        return S.fval.vals[dict_index]
    end

Is it possible to make this faster?

2

Depending on the data an array with findfirst or, better if possible, searchsortedfirst may be faster.
Also be user to use a type-stable dict or array.

3

Fastest way in terms of less programming and mental overhead? I’d recommend the excellent GitHub - marius311/Memoization.jl: Easily and efficiently memoize any function, closure, or callable object in Julia. by @marius311 . It’s been very well optimized in my experience and additionally has quite a lot of flexibility.

4 Likes
4

Thanks. I will try the library.

1 Like
5

I’m not sure if this is possible. The number of cached results is huge, at least O(10^6).

1 Like
6

Yeah, just tested it here, and it seems that searchsortedfirst is never faster than a getindex from a dict. They are similar at <100 elements only. So that’s not an option.

7

Why use the internal method ht_index instead of official:

return get!(S.fval, (i,j)) do
    # slow path using (i,j)
end

which also stores the value in S.fval.

Small demo:

julia> d = Dict(1=>2)
Dict{Int64, Int64} with 1 entry:
  1 => 2
julia> get!(d, 1) do
       println("slow")
       5
       end
2
julia> get!(d, 3) do
       println("slow")
       5
       end
slow
5
julia> d
Dict{Int64, Int64} with 2 entries:
  3 => 5
  1 => 2
8

You need to show more code for people to be able to help you. What is S? What is S.fval? What is S.fval.vals? Is your Dict properly typed? Are you digging into the internals of Dict, because this doesn’t look like Julia code I’m familiar with.

9

Thank you, because I didn’t know.

This is more elegant. Unfortunately, the performance is the same.

10

The code is for a matrix-like struct SMat,

struct SMat{fvalT}
    ....
    fval::Dict{NTuple, fvalT}
    function SMat(....)
        new(..., Dict{NTuple{2, Int}, fvalT}())
    end
end

I believe the Dict fval is properly typed, which stores the values of the matrix.

function getindex(S::SMat, i::Int, j::Int)
    return get!(S.fval, (i,j)) do
        # Slow path
    end
end

The function I want to cache is this getindex. Thanks to @Dan, it is quite elegant now.

Profiling shows that get! is hit many times and it calls ht_keyindex2!. To be honest, the Dict is already quite fast. Maybe I should consider other ways to cache the results?

11 
julia> isconcretetype(NTuple)
false

NTuple isn’t a concrete type. You have to specify both the number and type of members, for example NTuple{2, Int}.

1 Like
12

Thank you! I thought specifying the type in new is good enough. With this fix, it’s 20% faster now.

1 Like