# Fastest way to do memoization?

**URL:** <https://discourse.julialang.org/t/fastest-way-to-do-memoization/95100>\
**Category:** Performance\
**Tags:** performance\
**Created:** [February 23, 2023, 6:57pm UTC](https://discourse.julialang.org/t/fastest-way-to-do-memoization/95100 "2023-02-23T18:57:58Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![linwaytin](https://avatars.discourse-cdn.com/v4/letter/l/898d66/32.png) [@linwaytin](https://discourse.julialang.org/u/linwaytin)\
**Post date:** [February 23, 2023, 6:57pm UTC](https://discourse.julialang.org/t/fastest-way-to-do-memoization/95100/1 "2023-02-23T18:57:58Z")

</div>

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.

```julia
    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?

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [February 23, 2023, 7:03pm UTC](https://discourse.julialang.org/t/fastest-way-to-do-memoization/95100/2 "2023-02-23T19:03:32Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![TheCedarPrince](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/thecedarprince/32/17323_2.png) [@TheCedarPrince](https://discourse.julialang.org/u/TheCedarPrince)\
**Post date:** [February 23, 2023, 7:22pm UTC](https://discourse.julialang.org/t/fastest-way-to-do-memoization/95100/3 "2023-02-23T19:22:44Z")

</div>

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.](https://github.com/marius311/Memoization.jl) by @marius311 . It’s been very well optimized in my experience and additionally has quite a lot of flexibility.

---

<div class="post-metadata">

**Author:** ![linwaytin](https://avatars.discourse-cdn.com/v4/letter/l/898d66/32.png) [@linwaytin](https://discourse.julialang.org/u/linwaytin)\
**Post date:** [February 23, 2023, 7:24pm UTC](https://discourse.julialang.org/t/fastest-way-to-do-memoization/95100/4 "2023-02-23T19:24:38Z")

</div>

Thanks. I will try the library.

---

<div class="post-metadata">

**Author:** ![linwaytin](https://avatars.discourse-cdn.com/v4/letter/l/898d66/32.png) [@linwaytin](https://discourse.julialang.org/u/linwaytin)\
**Post date:** [February 23, 2023, 7:26pm UTC](https://discourse.julialang.org/t/fastest-way-to-do-memoization/95100/5 "2023-02-23T19:26:47Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [February 23, 2023, 7:39pm UTC](https://discourse.julialang.org/t/fastest-way-to-do-memoization/95100/6 "2023-02-23T19:39:10Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Dan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dan/32/42581_2.png) [@Dan](https://discourse.julialang.org/u/Dan)\
**Post date:** [February 23, 2023, 7:52pm UTC](https://discourse.julialang.org/t/fastest-way-to-do-memoization/95100/7 "2023-02-23T19:52:43Z")

</div>

Why use the internal method `ht_index` instead of official:

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

```

which also stores the value in `S.fval`.

Small demo:

```julia
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

```

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [February 23, 2023, 8:30pm UTC](https://discourse.julialang.org/t/fastest-way-to-do-memoization/95100/8 "2023-02-23T20:30:12Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![linwaytin](https://avatars.discourse-cdn.com/v4/letter/l/898d66/32.png) [@linwaytin](https://discourse.julialang.org/u/linwaytin)\
**Post date:** [February 23, 2023, 8:45pm UTC](https://discourse.julialang.org/t/fastest-way-to-do-memoization/95100/9 "2023-02-23T20:45:50Z")

</div>

Thank you, because I didn’t know.

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

---

<div class="post-metadata">

**Author:** ![linwaytin](https://avatars.discourse-cdn.com/v4/letter/l/898d66/32.png) [@linwaytin](https://discourse.julialang.org/u/linwaytin)\
**Post date:** [February 23, 2023, 9:06pm UTC](https://discourse.julialang.org/t/fastest-way-to-do-memoization/95100/10 "2023-02-23T21:06:32Z")

</div>

The code is for a matrix-like struct `SMat`,

```julia
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.

```julia
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?

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [February 23, 2023, 9:12pm UTC](https://discourse.julialang.org/t/fastest-way-to-do-memoization/95100/11 "2023-02-23T21:12:45Z")

</div>

> [@linwaytin](#):
>
> `fval::Dict{NTuple, fvalT}`  
> I believe the Dict `fval` is properly typed

```julia
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}`.

---

<div class="post-metadata">

**Author:** ![linwaytin](https://avatars.discourse-cdn.com/v4/letter/l/898d66/32.png) [@linwaytin](https://discourse.julialang.org/u/linwaytin)\
**Post date:** [February 23, 2023, 9:18pm UTC](https://discourse.julialang.org/t/fastest-way-to-do-memoization/95100/12 "2023-02-23T21:18:23Z")

</div>

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