memoization2-dlang.md

Memoization in the D Programming Language, part 2

In continuation of the article Memoization in the D Programming Language, this article describes new features of my D library 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 standard library Phobos (implemented differently in some very little details, namely using string mixins (autogenerated code) to implement all of memoize, noLockMemoize, synchronizedMemoize (see below) based on a common template). memoize template without maxSize argument is implemented in a quite simple way (see below). memoize with maxSize argument is implemented in a rather complex obscure way (which I even don't understand due to lack of comments in Phobos).

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 = 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, what is a rather slow operation.