Another implementation of `@memoize` which is type inference friendly & generic functions

Package Announcements
,
1

I made another Memoize.jl package for daily use of Julia.

Suggestions & criticisms are welcom.

Overview

This package provides basic support for type inference friendly generic function memoization. It allows to customize cache key from function arguments.

  • Type inference friendly
  • Cache invalidation
  • Each method of a generic function has its own cache
  • Custom cache key
  • Recursive functions

Limitation

  • Keyword arguments or default arguments are not supported.
  • Require standard function definition with return type annotated.
  • Parametric functions are not supported.
  • Use Dict for cache, not ObjectIdDict.
  • Work best with Julia v0.6 since automatic recompilation of dependent functions is fixed.

Exposed Verbs

export @memoize, clear_cache, get_cache

Usage

Pkg.clone("https://github.com/colinfang/Memoize.jl.git")

using Memoize

@memoize function fib(x::Int)::Int
   x <= 2 ? x : fib(x - 1) + fib(x - 2)
end

@memoize function fib(x::Float64, y)::Float64
   x + y
end

julia> fib(3), fib(1.0, 5)
(3, 6.0)

julia> @time fib(100)
0.000073 seconds (199 allocations: 14.166 KiB)
juila> @time fib(100)
0.000005 seconds (5 allocations: 176 bytes)

julia> get_cache(fib)
Dict{Tuple,Dict} with 2 entries:
  (Float64, Any) => Dict{Any,Float64}(Pair{Any,Float64}((1.0, 5), 6.0))
  (Int64,)       => Dict{Any,Int64}(Pair{Any,Int64}(68, 117669030460994),Pair{A…

julia> clear_cache(fib)
julia> get_cache(fib)
Dict{Tuple,Dict} with 2 entries:
  (Float64, Any) => Dict{Any,Float64}()
  (Int64,)       => Dict{Any,Int64}()

julia> @time fib(100)
0.000027 seconds (5 allocations: 176 bytes)

julia> Base.return_types(fib, (Int,))
1-element Array{Any,1}:
 Int64

# Assume `y` doesn't affect the result.
function Memoize.make_key(::typeof(fib), x, y)
   x
end

julia> fib(1.0, 5)
6.0
julia> fib(1.0, 6)
6.0

Macro Expand

@macroexpand Memoize.@memoize function fib(x::Int)::Int
   x <= 2 ? x : fib(x - 1) + fib(x - 2)
end

quote
    let
        local #55#pt = (Int,)
        local cache = (Memoize.get!)((Memoize.Dict){Memoize.Any, Int}, Dict{Tuple,Dict}(), #55#pt)
        global fib
        function fib(x::Int)::Int
            function unmemoized()::Int
                if x <= 2
                    x
                else
                    fib(x - 1) + fib(x - 2)
                end
            end
            key = (Memoize.make_key)(fib, x)
            (Memoize.get!)(unmemoized, cache, key)
        end
    end
end
3 Likes