Memoization in the D Programming Language, part 2

D Language

In continuation of the article “Memoization in the D Programming Language”, this article describes new features of my D library memoize-dlang (https://github.com/vporton/memoize-dlang).

I remind that memoization is automatically not calling a function again when called with the same parameters (usually to reduce the amount of computations).

memoize functions

memoize is the same as memoize from std.functional module from the standard library (implemented differently in some very little details).

See “Memoization in the D Programming Language” on how to use memoize.

The new library contains first the following templates:

  • memoize
  • noLockMemoize
  • synchronizedMemoize

noLockMemoize is like memoize but uses global (not thread-local like memoize) storage for the cache. noLockMemoize usually should not be used in multi-threaded programs, because it is not safe to call it from multiple threads at once.

synchronizedMemoize is noLockMemoize wrapped into synchronized { } to be executed at most in one thread at once and so safe to be used in multi-threaded programs. Namely synchronizedMemoize is the variant of memoize usually to be used in multi-threaded programs, because it uses only one cache for all threads but is nevertheless thread-safe.

memoizeMember

The template memoizeMember memoizes a non-static member of function of struct or class instances.

The usage (the meaning is a straightforward modification of the usage of memoize from the standard library Phobos) is like this:

import memoize;
struct S {
  int f(int a, int b) {
    return a + b;
  }
}
alias f2 = memoizeMember!(S, "f");
alias f3 = memoizeMember!(S, "f", 10); // caching maximum 10 parameter combinations
S s;
assert(f2(s, 2, 3) == 5);

As you see the member function name (“f” in the example) is passed as a string. This is very unnatural, but I found no other way to do it.

Here is the complete implementation of the memoizeMember template (I present only the two-arguments template variant for brevity):

template memoizeMember(S, string name) {
  alias Member = __traits(getMember, S, name);
  ReturnType!Member f(S s, Parameters!Member others) {
    return __traits(getMember, s, name)(others);
  }
  alias memoizeMember = std.functional.memoize!f;
}

The above does not compile with DMD v2.081.2 but compiles well with v2.084.1. Apparently it was a bug in the compiler.

As you see, the implementation is straightforward. We first get the nonstatic function member of S, then generate the function f to memoize, and finally memoize it with the standard library memoize function.

noLockMemoizeMember and synchronizedMemoizeMember are related to memoizeMember in the same way as noLockMemoize and synchronizedMemoize are related to memoize.

Now I will consider how memoize is implemented in Phobos (as of 2.085.0):

template memoize(alias fun)
{
  import std.traits : ReturnType;
  // alias Args = Parameters!fun; // Bugzilla 13580

  ReturnType!fun memoize(Parameters!fun args)
  {
    alias Args = Parameters!fun;
    import std.typecons : Tuple;

    static ReturnType!fun[Tuple!Args] memo;
    auto t = Tuple!Args(args);
    if (auto p = t in memo)
      return *p;
    return memo[t] = fun(args);
  }
}

The main idea of this implementation is that the cache is stored as an associative array indexed by tuples of arguments of the memoized function.

Also, note that memoizeMember is less effective than CachedProperty (see “Memoization in the D Programming Language”), because memoize uses access to associative array elements, which is a rather slow operation.