# Memoization performance

**URL:** <https://discourse.julialang.org/t/memoization-performance/26361>\
**Category:** General Usage\
**Created:** [July 14, 2019, 7:17pm UTC](https://discourse.julialang.org/t/memoization-performance/26361 "2019-07-14T19:17:26Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![tk3369](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tk3369/32/2824_2.png) [@tk3369](https://discourse.julialang.org/u/tk3369)\
**Post date:** [July 14, 2019, 7:17pm UTC](https://discourse.julialang.org/t/memoization-performance/26361/1 "2019-07-14T19:17:26Z")

</div>

Consider the classic fibonacci example:

```julia
fib = n -> n < 3 ? 1 : fib(n-1) + fib(n-2)

```

I have benchmarked several memoization implementations. The result is somewhat surprising. In theory, they work almost the same way. I wonder how it ends up with such a big difference. See [this gist](https://gist.github.com/tk3369/877c2c60f41f6b0941e76e977e916192) for details.

| # | How | Performance |
| --- | --- | --- |
| 1 | Custom caching code | 34 ns (generic) |
| 2 | Custom memoize closure | 51 ns (anonymous) |
| 3 | [Memoize.jl](https://github.com/JuliaCollections/Memoize.jl) | 223 ns (generic) |
| 4 | [Caching.jl](https://github.com/zgornel/Caching.jl) | 1038 ns (generic), 1057 ns (anonymous) |

---

<div class="post-metadata">

**Author:** ![tkoolen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkoolen/32/1603_2.png) [@tkoolen](https://discourse.julialang.org/u/tkoolen)\
**Post date:** [July 14, 2019, 8:35pm UTC](https://discourse.julialang.org/t/memoization-performance/26361/2 "2019-07-14T20:35:29Z")

</div>

What are you actually trying to measure? `@btime` prints the minimum time over all iterations, and since the cache will contain the result for `fib(40)` at some point, you’re really just benchmarking cache lookup. Is that really what you’re interested in?

BTW, for your custom caching code the cache is a `Dict{Any, Any}`, and you’re basically doubling the hash computation cost by first doing a `haskey` and then a `getindex`. You could probably speed things up by using a `Dict{Int, Int}` and using `get!`. But if you’re going to go to the trouble of customizing for this particular application, why not use a `Vector{Int}` as the cache?

---

<div class="post-metadata">

**Author:** ![tk3369](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tk3369/32/2824_2.png) [@tk3369](https://discourse.julialang.org/u/tk3369)\
**Post date:** [July 14, 2019, 8:46pm UTC](https://discourse.julialang.org/t/memoization-performance/26361/3 "2019-07-14T20:46:57Z")

</div>

> [@tkoolen](#):
>
> since the cache will contain the result for `fib(40)` at some point, you’re really just benchmarking cache lookup.

This is a very good point. But if that’s the case then all of these options should be almost identical. I think Memoize.jl uses An `IdDict`. Maybe the overhead came from the construction of the key.

It is just a toy example. I am just interested in the best way to do memoization. I’m in the process of writing a book, and this is one of the subject areas.

---

<div class="post-metadata">

**Author:** ![tkoolen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkoolen/32/1603_2.png) [@tkoolen](https://discourse.julialang.org/u/tkoolen)\
**Post date:** [July 14, 2019, 8:49pm UTC](https://discourse.julialang.org/t/memoization-performance/26361/4 "2019-07-14T20:49:28Z")

</div>

> [@tk3369](#):
>
> I think Memoize.jl uses An `IdDict` .

Yes, by default, but you can also specify the type of the cache.

---

<div class="post-metadata">

**Author:** ![zgornel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/zgornel/32/217487_2.png) [@zgornel](https://discourse.julialang.org/u/zgornel)\
**Post date:** [July 15, 2019, 7:43am UTC](https://discourse.julialang.org/t/memoization-performance/26361/5 "2019-07-15T07:43:44Z")

</div>

In the case of `Caching.jl`, a seemingly ‘long’ time is spent on hashing the input arguments. You can check out (if interested) the hashing function [here](https://github.com/zgornel/Caching.jl/blob/3d2563e72f35cc143dd18eb9cb18940feb4a6cd0/src/utils.jl#L2)  
For example:

```julia
@btime Caching.arghash(40)
  283.898 ns (4 allocations: 80 bytes)
0x63e396942df414aa

```

As a speed reference, on my machine,

```julia
@cache fib = n -> n<3 ? 1 : fib(n-1) + fib(n-2)
@btime fib(40)
  701.531 ns (17 allocations: 688 bytes)
102334155

```

Since it is being defined recusively, some time is spent on checking and inserting new values i.e.

```julia
julia> fib
fib (cache with 40 entries, 40 in memory 0 on disk)

```

I do have to say that nanosecond timings are not that relevant for the type of operations memoization is usually used for (i.e. operations that take orders of magnitude more time to complete i.e. `ms`/`s` for the increase in memory to be warranted).

In essence, all memoizers calculate hashes and lookup that hash in a dictionary however the type of hashing and checks performed have a slight performance penalty.

For small functions and very high speed i.e. `ns`-order, a custom memoizer is a much better choice.

---

<div class="post-metadata">

**Author:** ![Per](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/per/32/10387_2.png) [@Per](https://discourse.julialang.org/u/Per)\
**Post date:** [July 15, 2019, 12:18pm UTC](https://discourse.julialang.org/t/memoization-performance/26361/6 "2019-07-15T12:18:14Z")

</div>

[StaticNumbers](https://github.com/perrutquist/StaticNumbers.jl) can also be used for compile-time “memoization” of numeric functions (using Julia’s dispatch table as the cache). With the `fib` function from that package’s readme, I get:

```julia
julia> @btime fib(40)
  0.020 ns (0 allocations: 0 bytes)
102334155

```

This is cheating of course, since all of the computation takes place at compile time. As @tkoolen already said: `@btime` is probably not the most interesting benchmark for memoized functions…

Edit: I should probably mention that StaticNumbers is not intended for memoization. It just happens to work like that in this specific case because the compiler is able to do all the simplification.

---

<div class="post-metadata">

**Author:** ![Marc.Cox](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/marc.cox/32/7514_2.png) [@Marc.Cox](https://discourse.julialang.org/u/Marc.Cox)\
**Post date:** [October 5, 2020, 8:16pm UTC](https://discourse.julialang.org/t/memoization-performance/26361/7 "2020-10-05T20:16:12Z")

</div>

Thank You for these benchmarks for Memoization performance ,

I understand your benchmarks and book here might have been before LRUCache  
but the thread safe ( aka no race conditions ) use case is very important when you want reliable and predictable results like so "\*A particular use case of this package is to implement function memoization **for functions that can simultaneously be called from _different_ threads."**

[https://github.com/JuliaCollections/LRUCache.jl](https://github.com/JuliaCollections/LRUCache.jl)

Maybe time to update the website and/or revise book ?

HTH

Ps\> Maybe “There is nothing new under the sun ?” so I can’t help noticing this is recapitulating the design for Java **ConcurrentHashMap** and table lookups as described here \>\> [java - Is a HashMap thread-safe for different keys? - Stack Overflow](https://stackoverflow.com/questions/2688629/is-a-hashmap-thread-safe-for-different-keys#2688817)