Expression Templates in D

Question

The goal is to achieve the same effect as in this C++ example: avoid creating temporaries. I've tried translating the C++ example to D without success. I've also tried different approaches.

import std.datetime : benchmark;
import std.stdio    : writefln, writeln;

void bench(alias fun, string time = "msecs")(string msg, uint n = 1_000_000) {
  auto b = benchmark!fun(n);
  writefln(" %s: %s ms", msg, b[0].to!(time, int));
}

alias double Real;

struct Expression(string op, E1, E2) {
  E1 _v1;
  E2 _v2;
  alias _v1 v1;
  alias _v2 v2;

  auto opIndex(size_t i) {
    return mixin("v1[i]" ~ op ~ "v2[i]");
  }

  auto opBinary(string op, E)(auto ref E e) {
    return Expression!(op, typeof(this), E)(this, e);
  }
}

struct ExpVector {

  Real[40] _data = void;
  alias _data this;

  this(Real datum) pure nothrow { _data = datum; }

  auto opBinary(string op, T)(auto ref T other) {
    return Expression!(op, typeof(this), T)(this, other);
  }

  void opAssign(E)(auto ref E exp) {
    foreach(i, ref datum; _data)
      datum = exp[i];
  }
}

struct Vector {

  Real[40] _data = void;
  alias _data this;

  this(Real datum) pure nothrow { _data = datum; }

  auto opBinary(string op)(auto ref Vector other) {
    Vector ret;
    foreach(i, datum; _data)
      ret[i] = mixin("datum" ~ op ~ "other[i]");
    return ret;
  }
}

void main() {

  ExpVector e1 = ExpVector(1.5);
  ExpVector e2 = ExpVector(7.3);
  ExpVector ef;
  void T1() {
    ef = (e1 + e2) * (e1 + e2);
  }
  bench!T1(" vector operations using template expression");

  Vector v1 = Vector(1.5);
  Vector v2 = Vector(7.3);
  Vector vf;
  void T2() {
    vf = (v1 + v2) * (v1 + v2);
  }
  bench!T2(" regular vector operations");

  void T3() {
    for(int i = 0; i < vf.length; ++i)
      vf[i] = (v1[i] + v2[i]) * (v1[i] + v2[i]);
  }
  bench!T3(" what is expected if template expressions worked and temporaries were not created.");
}

The expression template version is slower than the non-expression template version. I was expecting the expression template version to be much faster and close to what is expected. So what is wrong with my expression templates? What's the correct way to do expression template in D?

Answer 1

In wikipedia's c++ example expression classes holds references to temporaries, and in case of expression...

Vec a, b;
double c;
Vec result = ( a - b ) * c

...right before assignment to result vector we have some sort of tree in memory:

a           b
 \        /
  \      /
   \    /
 VecDifference
      \
       \
        \
       VecScaled( has copy of 'c' embedded directly in object )

VecDifference hold just references to a and b, and VecScaled holds reference to temporary VecDifference (which, according to the c++ rules, will be alive until expression end). At the end we have no duplication of initial data and no unnecessary computations(if we will use just some components of vector, but not all of them as in simple assignment to Vec)
In your struct Expression(string op, E1, E2) initial and intermediate data simply copied to data members and at the end of previous expression you will have

Expression!( "*", Expression!( "-", Vec, Vec ), double )

where outer Expression will have copy of inner Expression( "-", Vec, Vec ) and double parameters and inner Expression will have copies of a and b vectors. So at the end of a day you avoided temporary Vec but made 4 copies of a and b (not counting final assignment to result vector). Though, don't know how nicely avoid copying in this situation in D. Maybe pointers to structres ?
(BTW, c++11's auto type inference and expression templates with references to temporaries has unfortunate interaction, which can lead to bugs: http://lanzkron.wordpress.com/2011/02/21/inferring-too-much/)