Memoization.jl

Easily and efficiently memoize any function in Julia.
Author marius311
Popularity
37 Stars
Updated Last
1 Year Ago
Started In
November 2019

Memoization.jl

Build Status

Easily and efficiently memoize any function in Julia.

Usage

julia> using Memoization

julia> @memoize f(x) = (println("Computed $x"); x)

julia> f(2)
Computed 2
2

julia> f(2)
2

Highlights

  • All function definition forms with args and/or kwargs and/or type parameters work.

  • Your function remains inferrable.

  • Multiple memoized methods for the same function can be defined across different modules (no warnings are generated).

  • You can choose the cache type, e.g.,

    @memoize Dict f(x) = ...
    @memoize LRU(maxsize=5) f(x) = ...      # using https://github.com/JuliaCollections/LRUCache.jl

    The specifier should be a type which can be called without arguments to create the cache, or an expression which creates an instance of a cache (note: cache creation is delayed until the first time a function is called, so it is not possible to pass a pre-instantiated cache).

    The default cache type is IdDict which counts arguments the same if they === each other. Another common choice is Dict which memoizes based on if they == each other (this is probably useful if you want to count e.g. vectors which contain the same entries as the same, but will lead to somewhat slower cache lookup).

  • You can clear the cache for a given function at any time with Memoization.empty_cache!(f). Defining new memoized methods for a function will also clear the cache.

  • You can also clear all caches for all functions with Memoization.empty_all_caches!().

  • You are free to memoize some methods of a function but not others, e.g.:

    julia> @memoize f(x) = (println("Computed $x"); x)
    f (generic function with 1 method)
    
    julia> f(x,y) = (println("Computed $x,$y"); f(x+y))
    f (generic function with 2 methods)
    
    julia> f(1,2)
    Computed 1,2
    Computed 3
    3
    
    julia> f(1,2)
    Computed 1,2
    3
    
    julia> f(1,2)
    Computed 1,2
    3
  • You can memoize individual instances of closures, e.g.:

    julia> function make_func(x)
               @memoize func(y) = (println("Computed $x,$y"); (x,y))
           end;
    
    julia> f = make_func(1);
    
    julia> f(3)
    Computed 1,3
    (1, 3)
    
    julia> f(3)
    (1, 3)
    
    julia> g = make_func(2);
    
    julia> g(3)
    Computed 2,3
    (2, 3)
    
    julia> g(3)
    (2, 3)
    
    julia> f(3) # note both f and g memoized separately at this point
    (1, 3)
  • You can memoize individual instances of "callables", e.g.,

    julia> struct Foo
               x
           end
    
    julia> @memoize (f::Foo)(x) = (println("Computed $(f.x), $x"); (f.x, x))
    
    julia> foo1 = Foo(1);
    
    julia> foo1(3)
    Computed 1,3
    (1,3)
    
    julia> foo1(3)
    (1,3)
    
    julia> foo2 = Foo(2);
    
    julia> foo2(3)
    Computed 2,3
    (2,3)
    
    julia> foo2(3)
    (2,3)
    
    julia> foo1(3) # note both foo1 and foo2 memoized separately at this point
    (1,3)

Limitations

  • This package is not thread-safe with either Dict or IdDict. However, if a thread-safe cache is used (e.g. ThreadSafeDicts.jl), then memoizing top-level functions is thread-safe. Memoizing closures and callables is not yet thread-safe with any cache type.

Notes

This package can be used as a drop-in replacement for Memoize.jl, and, as of this writing, has fewer limitations.

The design is partly inspired by both Memoize.jl and this Stack Overflow comment.

Required Packages