Performance of various memoize implementations

memoize_perf.md

Custom cache

Generic function

julia> const fib_cache = Dict()
Dict{Any,Any} with 0 entries

julia> _fib(n) = n < 3 ? 1 : fib(n-1) + fib(n-2)
_fib (generic function with 1 method)

julia> function fib(n)
           if haskey(fib_cache, n)
               return fib_cache[n]
           else
               value = _fib(n)
               fib_cache[n] = value
               return value
           end
       end
fib (generic function with 1 method)

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

Custom memoize closure

julia> fib = n -> n < 3 ? 1 : fib(n-1) + fib(n-2)
#3 (generic function with 1 method)

julia> function memoize(f)
           memo = Dict()
           x -> begin
               if haskey(memo, x)
                   return memo[x]
               else
                   value = f(x)
                   memo[x] = value
                   return value
               end
           end
       end
memoize (generic function with 1 method)

julia> fib = memoize(fib)
#5 (generic function with 1 method)

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

Memoize.jl

Note: anonymous functions are not supported

julia> @memoize fib(n) = n < 3 ? 1 : fib(n-1) + fib(n-2)
fib (generic function with 1 method)

julia> @btime fib(40)
  226.386 ns (2 allocations: 32 bytes)

Caching.jl

Generic function

julia> @cache function fib(n)
           return n < 3 ? 1 : fib(n-1) + fib(n-2)
       end
fib (cache with 0 entries, 0 in memory 0 on disk)

julia> @btime fib(40)
  1.038 μs (19 allocations: 704 bytes)
102334155

Anonymous function

julia> @cache fib = n -> n < 3 ? 1 : fib(n-1) + fib(n-2)
fib (cache with 0 entries, 0 in memory 0 on disk)

julia> @btime fib(40)
  1.057 μs (19 allocations: 704 bytes)
102334155