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.

How to Make Your Programs Run Hundreds to Thousands Times Faster Without Giving up Reliability and Ease of Programming

Introduction

D programming language is the newest and the only technology that is both:

  • high performance
  • rapid development
  • reliable

High performance means that your software is expected to load at least about 10 times faster (for SSD disks) and run hundreds to thousands of times faster than most modern software and also use much less memory and produce less heat at the CPU.

Rapid development means that you do the project quickly. D programming is as easy for experienced programmers as Python or Ruby programming, if not easier thanks to higher reliability (see below) and thus less time to debug.

Reliable means that you use no less (maybe more) reliable technologies than in the atomic powerplant that powers your house and nuclear rockets and airplanes, not what other developers do.

Frequently Asked Questions

How can it be thousands of times faster?

  1. D compiler produces directly CPU machine code, not an intermediary code.
  2. D programming language is a statically typed language (see below).

These two features together allow programs to run hundreds to thousands of times faster.

Which reliability features D has?

  • strict identifiers
  • static types
  • both dynamic and static asserts
  • type traits checking
  • automatic memory deallocation
  • no pointer arithmetic when unnecessary
  • array range checking
  • complex program logic checking at compile time

What are the advantages of D?

  • advanced programming language (not less than to say Python or Ruby) allowing to easily solve almost all kinds of programming problems
  • very high speed (on par with C, C++, Ada, Rust)
  • reliable (not worse than Ada, comparable with Rust)
  • the reasoning at compile time

Is D the very best programming language?

Yes as of 2019. (Well, some people would argue that Rust is better.) Well, almost, D isn’t the best tool for proving the correctness of math theorems, in all other applications which I know D is the best one.

Is D open source?

Yes.

What are the debug and release modes?

In D there are basically two modes of created software: debug and release. Debug mode may be a few times slower, but release mode software may crash randomly in the case of errors rather than shut down the program more correctly. It is your choice, what you need more: reliability or speed.

Static vs dynamic typing

Introduction

Programming languages are of two categories:

  1. statically (or what is the same strongly) typed
  2. dynamically typed

The distinction is that in a dynamically typed language a variable can hold any object (and moreover the type of the variable can change while programs run), while in a statically typed language a variable can hold only an object of a certain type.

At first, it seems that dynamic typing makes programming easier, but it comes at a high cost:

  1. Programs in dynamic languages work much slower and use more memory. Moreover is too hard to write an optimizing compiler for a dynamic language, so programs work even slower.
  2. Dynamic languages don’t check value types what makes it very easy to make an error. Probably more than 50% of all programming errors are a wrong variable type in a dynamic language. Beware of unreliability.

In the past most languages used were static. It is understandable: Computers were slow and they needed fast languages.

In recent years dynamic languages gained popularity because they make programming easier.

But recently there was an unnoticed revolution: It was created D programming language, a static language which is as powerful (if not more) as dynamic languages. Now nothing prevents you to have both: high speed and reliability as well as a language with powerful features easy to use, to write short, understandable programs.

Dynamic languages now should mostly go to history. D is better.

Dynamic typing explained

Static typing is mostly simple: After compilation, a variable is either a word (such as a 64-bit integer) in computer memory or a group of nearby words or a set of such interrelated objects.

To make it even faster, variables can often be stored directly in a CPU register rather than in RAM.

Dynamic typing is more complex to implement (and it is, therefore, slower): A variable consists of:

  • a memory word specifying its type (remember, in a dynamic language a variable can have multiple types and even change its type)
  • a pointer to a memory location where the variable is placed
  • a word or sequence of words holding the actual value

You see, it takes more memory. But the main problem is that memory for the variable value needs to be allocated/deallocated (and it is a slow operation) while the variable is created, changed, or destroyed. Almost every operation requires memory allocation. Also, as I said above the complexity of doing this prevents optimizing the program to make it fast. For example, we cannot store a dynamic variable in a CPU register. This is the reasons why dynamic is sometimes hundreds or thousands of times slower.