One loop is enough

Sylvester has been out for a few days now, and seems to be drawing, ahem, mixed reactions over on Ajaxian (mostly for variable naming rather than its actual functionality). It’s nice that a few people seem to be checking it out, even if it is a little rough-round the edges.

One thing I’m really pleased with is that I’ve got the library’s syntax to be as natural as it is. The maths reads like maths, and your conditions read like sentences: if (A.isPerpendicularTo(B)) { ... }. Nothing staggering, I know, but I’m glad the library works just as I intended. However, while beginning work on a future version, one with polygons and line segments and algorithms like this (PDF), I found out that version 0.1.0 is a little on the slow side. But, I thought, other people have built 3D rendering in JavaScript that goes at a decent clip and has to do the same maths that I’m doing, so why is my test page taking half a second to rotate a bunch of triangles?

The answer is that all the syntactic niceties hide a whole bunch of loops, and lots of unnecessary looping slows code down. If you’re only interested in doing a few one-off vector/matrix calculations that’s fine, but if you want to move dozens of polygons around at once you’re going to run into trouble. So, I’ve been rewriting sections of code to speed the library up, and almost paradoxically that involves making some sections of code much longer.

An example: the rotate method of the Vector class, which rotates a point about a line. This is the code for rotating a 3-vector in version 0.1.0:

var C = line.pointClosestTo(this);
var R = Matrix.Rotation(t, line.direction);
return C.add(R.x(this.subtract(C)));

That all looks rather elegant and very legible. So what’s the problem? The add method loops over the vector’s elements, as does subtract. (Actually, subtract involves two loops in 0.1.0 as it multiplies the argument by -1 and then adds it to the receiver. This is much shorter to code but runs half as fast.) x is a matrix multiplication, which is two loops. All these invoke either Vector.create or Matrix.create, which involves even more loops, although these will go in future versions as they do over-paranoid things like checking that all the arguments are numeric.

So how do we improve things? In this case, we know that all the vectors involved are 3-dimensional – the Line class only works in 3D. This knowledge means we can work out the result explicitly without any unnecessary loops. The code becomes:

var C = line.pointClosestTo(this);
var R = Matrix.Rotation(t, line.direction);
x = this.elements[0] - C.elements[0];
y = this.elements[1] - C.elements[1];
z = this.elements[2] - C.elements[2];
return C.map(function(a, i) {
  return a + R.elements[i-1][0] * x +
      R.elements[i-1][1] * y + R.elements[i-1][2] * z;
});

We’ve rewritten the result all in one map loop, and that means it will run much faster. We could even go one step further and write out all the elements of the result by hand without using map. So far, I’ve managed to get some methods to run up to four times faster by not relying on Sylvester’s API to work things out. Does this make Sylvester seem unnecessary? Quite the opposite: its methods are being rewritten to make them perform better and save you a lot of coding.

Before anyone chimes in about filesize, I should point out that with this project, given where I want to take it, execution speed is number one priority. You can always pack your JS, and a few extra lines in the source won’t blow up the packed version much. And maybe just to annoy the filesize fanatics, here’s what’s happened in Line#pointClosestTo lately:

Before (version 0.1.0):

var A = P.subtract(this.anchor);
return P.add(this.direction.cross(
  this.direction.cross(A)
).toUnitVector().x(this.distanceFrom(P)));

After:

var A = this.anchor, D = this.direction;
var D1 = D.elements[0], D2 = D.elements[1], D3 = D.elements[2];
var A1 = A.elements[0], A2 = A.elements[1], A3 = A.elements[2];
var P1 = P.elements[0], P2 = P.elements[1], P3 = P.elements[2];
var V = Vector.create([
  D2 * (D1 * (P2-A2) - D2 * (P1-A1)) -
      D3 * (D3 * (P1-A1) - D1 * (P3-A3)),
  D3 * (D2 * (P3-A3) - D3 * (P2-A2)) -
      D1 * (D1 * (P2-A2) - D2 * (P1-A1)),
  D1 * (D3 * (P1-A1) - D1 * (P3-A3)) -
      D2 * (D2 * (P3-A3) - D3 * (P2-A2))
]);
var k = this.distanceFrom(P) / V.modulus();
return Vector.create([
  P.elements[0] + V.elements[0] * k,
  P.elements[1] + V.elements[1] * k,
  P.elements[2] + V.elements[2] * k
]);

That runs about four times faster than the 0.1.0 version.

If you’ve enjoyed this article, you might enjoy my recently published book JavaScript Testing Recipes. It’s full of simple techniques for writing modular, maintainable JavaScript apps in the browser and on the server.