Memoizer

Memoizer is an application that enables memoization of functions (that is, it stores the results of expensive function calls and returns the cached result when the same input occur again).

This is an optimization technique known in Dynamic Programming.

Installation

The package can be installed as:

1. Add memoizer to your list of dependencies in mix.exs.

   def deps do [ ... {:memoizer, "~> 0.0.1"}, ... ] end

2. Ensure memoizer is installed into your application.

   mix deps.get

Usage

Simply define a module and use Memoizer in it. Then you can define functions with the defmemo macro, just like with def. Feel free to mix def and defmemo to indicate what to memoize and what not.

defmodule MemoExample do
  use Memoizer

  def     fib(0), do: 0
  def     fib(1), do: 1
  defmemo fib(n), do: fib(n - 1) + fib(n - 2)
end

You can use guards just like with normal functions. It is even possible to control which part to memoize. Here's a fib() variant that only memoizes every 5th value:

def     sparse_fib(0), do: 0

def     sparse_fib(1), do: 1

defmemo sparse_fib(n) when rem(n, 5) == 0,
                do: sparse_fib(n - 1) + sparse_fib(n - 2)

def     sparse_fib(n),
                do: sparse_fib(n - 1) + sparse_fib(n - 2)

use Memoizer turns the MemoExample module into an OTP worker that needs to be started before you can apply the functions in it. MemoExample.start_link is the simplest way to do that in iex, or you can use a supervisor to take care of it for you:

children = [
  ...
  worker(MemoExample, []),
  ...
]
...
supervise children, strategy: ...

If you need to normalize, typecast, map, etc. some of the paramters or the return value of a memoized function, just create a wrapper function for it. You can use defmemop if you want to hide the non-wrapped version of your function.

def age(birth) do
  birth
  |> Timex.parse("{YYYY}-{0M}-{0D}")
  |> age_and_horoscope
  |> pretty_format_age_and_horoscope
end

defmemop age_and_horoscope({:ok, date_time}) do
  ...
end

Advanced usage

It is possible to manually put values into the cache or ask the cache to forget certain cached values stored in it. It's also possible to create a separate module in the Erlang runtime with the memoized function clauses in it in order to speed up further calculations. If you are interested in any of these, have a look at the functions

• Memoizer.learn/4
• Memoizer.memoized?/3
• Memoizer.forget/1,2,3
• Memoizer.compile/1,2

How it works

There's a server process started, but the function results are stored in a protected, read optimized ETS table. This allows processes to check for existing results very quickly. defmemo wraps the function in some additional code that makes this checking transparently from the caller process.

The server process is responsible for filling in data to the ETS table and also for owning the table. Checking for already existing results happens in the same process where the function gets called, while putting in new data to the cache is the responsibility of the server process.

Calling MemoExample.fib(10) fills in the ETS table with entries like the followings. The tuples contain the function name, the argument list and the result.

{{:fib,  [2]},  2}   # MemoExample.fib(2)  ==  2
{{:fib,  [3]},  3}   # MemoExample.fib(3)  ==  3
{{:fib,  [4]},  5}   # MemoExample.fib(4)  ==  5
{{:fib,  [5]},  8}   # MemoExample.fib(5)  ==  8
{{:fib,  [6]}, 13}   # MemoExample.fib(6)  == 13
{{:fib,  [7]}, 21}   # MemoExample.fib(7)  == 21
{{:fib,  [8]}, 34}   # MemoExample.fib(8)  == 34
{{:fib,  [9]}, 55}   # MemoExample.fib(9)  == 55
{{:fib, [10]}, 89}   # MemoExample.fib(10) == 89

In memoization implementatios that use GenServers for storing the result cache, the GenServer can become a bottleneck when all read and write operations go trough the server process. In our case Memoizer does all writes to the cache trough a separate gen server process, while read operations happen in the client processes. This enables read optimized ETS tables and takes off the burden of managing the writes from the clients.

In your use case this may be the wrong approach. It's on my TODO list to add different store types to Memoizes. For example, it makes sense sometimes to store the calcualted values in a DETS or Mnesia table. In other cases the simply putting them into the process dictionary is fine. In other cases ETS can be the right solution but with a publicly writeable, serverless design.

Please let me know if you need any of these and I'll gladly do them.