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.