What are you doing with Sylvester?

Apparently some people are actually using Sylvester. Which comes as something of a surprise to me because I’ve had nobody (until today) email me or comment here about it at any length. It initially came out seven or eight months ago, and while I intented it to be a full 3D rendering environment, my day job took over more and more of my time and it never got beyond being a maths framework. Truth be told, I knew pretty much nothing about 3D rendering when I started (and that largely remains true), but I’d seen other people write 3D engines in JavaScript and wanted to learn (and I wanted to write something that wasn’t riddled with dozens of global functions). And, though it’s so far not fulfilled the ambitions I initially had for it, writing it has taught me a great deal about JavaScript performance.

Recently though, there’s been signs of OpenGL-backed 3D environments coming to various browsers, and however good a job I make of writing a 3D engine, it will never perform as well as native browser code. I still think it’s worth fleshing out the maths capabilities of the framework, though — there are various features I was working on for version 0.2 that have never seen the light of day. Stuff like line segments, polygons, and various useful algorithms for dealing with them. I’d be interested to know whether people would be interested in me finishing these features, and whether I should still push for a 3D rendering engine. So if you’re using Sylvester for any project, large or small, do get in touch and let me know what you think of it and how it should be improved.

for vs. do {} while

While developing Sylvester, I’ve read up a little on how to make JavaScript perform as best it can. One of the recommendations given in this Andy King article and elsewhere is that you should use do {} while instead of for for looping purposes. I’m not singling out King for criticism, but I want to clarify some of what he says.

He does point out that the use of this construct:

do {
  // Code goes here
} while (--i);

depends on the starting value of i being greater than zero. He doesn’t point out that by putting the while first, you can accommodate zero starting values and get exactly the same sequence of i values.

while (i--) {
  // Code goes here
}

Now the loop will not execute if i starts at zero and you won’t get an infinite loop. Note the switching of the position of the decrement operator to ensure the right values are passed into the loop. King does not clarify this and suggests that the following will do the same thing:

do {
  // Code goes here
} while (--i);    // pre-decrement
do {
  // Code goes here
} while (i--);    // post-decrement

Say i begins at 3 in both cases. The first will iterate the loop with the values 3, 2 and 1: pre-decrementing 1 evaluates to 0 and the loop stops. But, post-decrementing 1 evaluates to 1 so the loop will run one more time in the second case.

Finally, onto the issue of speed. (These findings are based on testing in Firefox 2.0 using Firebug.) Yes, while is faster than for if you can use the decrement operator as a conditional statement. The efficiency comes from the fact that you’re using the same command to change the iteration value and check whether we should loop again, so it’s only useful for situations where you can count down to zero rather than needing to count upwards. Also, if you need to use the iteration counter in the loop and you need to count forwards, you need to do something like this:

var n = 10, k = n, i;
do {
  i = k - n;
} while (--n);

which, it turns out, is slower than using a for loop to achieve the same thing:

for (var i = 0; i < n; i++) { ... }

So to sum up: if you can afford to count backwards to zero, use a while loop as this will involve the fewest commands to actually make the loop run. If you need to count forwards or end on anything other than zero, use a for loop and cache as many things as you can. For example, write

var n = someArray.length;
for (var i = 0; i < n; i++) { ... }

instead of putting the array length statement directly inside the for statement. Retrieving a property from an object takes longer than retrieving a primitive value, so this is the most efficient way to do things.

Writing a linked list in JavaScript

Before I get into the details of this, what exactly is a linked list? Well, it’s a type of data storage structure that has some similarities to the array data type. The key difference is that, rather than storing values using numeric indexes, it stores them by creating links between successive elements so that they form a chain. You can only traverse such a list by following the links between elements, rather than by specifying an index. The advantage of linked lists is that they make removing and re-ordering elements really easy and efficient.

For example, for Sylvester‘s next release, I’m implementing an algorithm that splits a polygon into a collection of its constituent triangles. It does this by recursively removing vertices from the polygon, chopping off one triangle each time. Managing the list of vertices using an array in this instance would quickly cause headaches, as you have to shuffle each element down a notch after removing an element from the list using a bunch of slice() and push() operations. As well as being inelegant, this is also really inefficient. Linked lists allow you to cleanly remove items from them, and all this operation has to do is change the links on the elements either side of the removed one.

JavaScript does not have a built-in linked list data type, so we need to implement our own. I’m going to show how to write a doubly-circularly-linked list, which sounds like the most complicated but is also the most versatile. It contains the functionality of linear and singly linked lists, and adds more features on top. If you want a more restricted type of list, this code should give you a good starting point.

I’ll start by specifying a base class that holds properties (and methods, later) shared between all types of linked list.

function LinkedList() {}
LinkedList.prototype = {
  length: 0,
  first: null,
  last: null
};

I’ve given it a length property that will work the same way as that for arrays. The properties first and last will be pointers to the first and last nodes in the list – we need somewhere to start traversing the list from! Throughout this, it’s important to remember that objects in JavaScript are pass-by-reference: setting myList.first = someObject means that myList.first is a reference to the object represented by someObject, not a copy of its value. In fact, the two variables are both references to the same data in memory – change one and you’ve automatically changed the other. This pass-by-reference feature is what makes linked lists possible.

Next, I’m going to subclass this to write the specifics of my doubly circular list.

LinkedList.Circular = function() {};
LinkedList.Circular.prototype = new LinkedList();

We need a way of adding nodes to the list. I should point out that a linked list is only good for storing lists of objects, not primitive values like strings or numbers. We need to set properties on the list nodes themselves, and we can only do that with objects.

Our first method, append, takes an object and sticks on the end of the list. If the list is empty, the node’s prev and next pointers will point to itself – the list is circular. Otherwise, we just link it up to the previous node and the first node in the list by setting properties:

LinkedList.Circular.prototype.append = function(node) {
  if (this.first === null) {
    node.prev = node;
    node.next = node;
    this.first = node;
    this.last = node;
  } else {
    node.prev = this.last;
    node.next = this.first;
    this.first.prev = node;
    this.last.next = node;
    this.last = node;
  }
  this.length++;
};

Note how we set the last property last of all – if we did it sooner then it would point to the wrong node for the links we want to create.

The second useful method we need is insertAfter, which allows us to insert a node anywhere in the list. The logic for this follows the same pattern – everything is done by just setting some properties, rather than shuffling array elements around. This highlights another important distinction between arrays and linked lists – a linked list does not ‘contain’ its nodes in the same way that arrays contain their values. Linked lists emerge out of links between objects, and a LinkedList object is just a plain object with three properties – first, last and length.

For insertAfter, we don’t need to deal with the special case of the list being empty, as we need some pre-existing node to insert the new one after. We do have to deal with the case where the new node becomes the last node in the list:

LinkedList.Circular.prototype.insertAfter = function(node, newNode) {
  newNode.prev = node;
  newNode.next = node.next;
  node.next.prev = newNode;
  node.next = newNode;
  if (newNode.prev == this.last) { this.last = newNode; }
  this.length++;
};

Pay attention to the order in which properties are set – anything that needs to be retrieved in order to set a link cannot be modified until nothing else depends on it. We set the links on the incoming node first by retrieving properties from the list, then skip forward to link the node in front, then finally change the node we’re inserting after, after we’ve got all the information we need from it.

The remove method is a little more involved, as we need to handle what happens when there’s only one node remaining. Again, pay attention to the order of operations and how it avoids broken links.

LinkedList.Circular.prototype.remove = function(node) {
  if (this.length > 1) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
    if (node == this.first) { this.first = node.next; }
    if (node == this.last) { this.last = node.prev; }
  } else {
    this.first = null;
    this.last = null;
  }
  node.prev = null;
  node.next = null;
  this.length--;
};

That’s all you need to get a basic linked list going. I add some methods for iteration, searching etc. but the core is what’s written above. I’ve leave prepend and insertBefore as exercises for the reader they’re really not tricky.

One other useful class you might need is an explicit node class. Sometimes, you’ll need to allow objects to belong to several linked lists, but each object can only have one prev and one next pointer. The cleanest way to solve this is to create a class specifically for use as a linked list node, that can point to objects you want to list.

LinkedList.Node = function(data) {
  this.prev = null; this.next = null;
  this.data = data;
};

So then you’d write

myList.append(new LinkedList.Node(someObject));

which appends a new object with a pointer to the object to actually want to list as its data property.

It’s a little tricky to see how this is so different from an array at first, but one you start using it where it’s appropriate you’ll find it so much more useful. Later this week I’ll post some additional useful methods and a source file for you to download.

Sylvester 0.1.3

Rounding out today’s flurry of posts, a quick note to the effect that Sylvester is now at version 0.1.3. The 0.1.2 release missed a couple of bugs that I meant to fix with it. Well not bugs, as such, but places where value/reference ambiguity could have caused problems. I’m beginning work on 0.2 again, after a long break focusing on other projects and house hunting. This should be the final 0.1 release, unless I find any particularly catastrophic bugs.

Sylvester 0.1.2

Time for the once-a-month update to Sylvester, my JavaScript vector maths library. This release fixes some bugs to do with variables being passed by reference instead of value, and allows you to pass plain arrays to various Matrix methods as long as they are properly nested into rows and columns. If they take some other form, Matrix will attempt to convert them into matrix format as before; the difference is that it won’t bother converting to proper Matrix objects if it doesn’t need to, and this can speed things up significantly.

Progress on this has been a little slow given that I started this project nearly three months ago. The first release took a couple of weeks but progress after that slowed up as I realised I needed to optimise heavily if this library was going to do any computational geometry or graphics things fast enough. Also, a bunch of Rails projects and JavaScript UI stuff has cropped up since then to occupy my time. Life’s been a little hectic recently but hopefully I’ll be able to focus on this again soon.

And before anyone asks: yes, I know doing serious graphics in JavaScript is asking for trouble and poor performance. I’m doing this to teach myself a few things and find out what this language can do.

When to use plain arrays, or, know when you’re repeating yourself

UPDATE: since writing this, Sylvester continues to be tweaked for performance. Some of the below may no longer apply, and you should always do your own testing for performance to find out what works for you. I’m leaving this article up to illustrate the broader points it has to make.

Now that Sylvester allows you to use plain old arrays pretty much anywhere you can use a vector as an argument, how do you decide which one to use? The trick is to know what the the method you’re passing the array/vector to is going to do with it. In the vast majority of cases where vectors are used as arguments, the method is only interested in the vector’s elements. In fact, what often happens is something like this:

someVectorMethod: function(vector) {
  var elements = vector.elements || vector;
  // ...
}

So elements ends up being an array, whether you pass an array or a vector. You’ll find passing a vector is slightly faster due to the nature of the || operator, and that might lead you to do the following:

// Bad bad code:
var foo = myVector.add($V([2,9,4]));

As well as being ugly, this is really inefficient. You’re calling $V for no reason at all, and the time that takes to run far outweighs the time saving of passing a vector. In this situation,

// Much nicer:
var bar = myVector.add([2,9,4]);

is both cleaner and faster.

It’s only sensible to pass a vector if you’ve already got one in memory as the result of another calculation:

var somePoint = lineA.intersectionWith(PlaneB);

// This is faster...
var foo = myVector.add(somePoint);

// than this...
var bar = myVector.add(somePoint.elements);

For matrices, the reverse is true. Because the Matrix class is written to be able to cope with accepting vectors and matrices as arguments, and to treat vectors as column matrices for multiplication, its methods can’t just use arg.elements || arg to get the necessary array of elements. Matrix arrays are nested, whereas vector ones aren’t. If arg is [9,2,6] (a vector), it must be converted to [[9],[2],[6]] to behave as a column matrix. So, most matrix methods call Matrix.create if they receive a non-matrix argument, and this sorts out the conversion. This means that, if you’ve got a vector you’re going to subject to lots of matrix methods, you’re better off converting it to a matrix beforehand to save all those conversion calls. Even if you’re only calling one matrix method, you’ll find that converting the argument to a matrix before passing it over will save you some time overall. Strange but true.

Sylvester 0.1.1 released

As I’m sure I’ve mentioned before, Sylvester 0.1.0 was slow. Very very slow in fact. With that in mind, today sees the release of version 0.1.1. Here’s what’s changed.

First and foremost: the vast majority of the framework has got much faster. Some notable highlights (speed comparisons are approximate and may depend on your computer):

  • Matrix.Rotation in 3D is 50 times (yes, fifty, as in 5000%) faster than in 0.1.0. As a result, Vector#rotate is about 60 times faster, and Line#rotate and Plane#rotate are 20 to 30 times faster. 0.1.0 was using some mighty stupid routines to work out rotation matrices; the new implementation uses a quick closed-form algorithm.
  • Reflection in planes is now around 10 times faster for vectors, lines and planes.
  • Matrix equality testing is now 20 times faster and multiplication is 6 times faster (based on 3×3 matrices). Trace calculation is 100 times faster.
  • Many other routines are between 2 and 6 times faster than before.

One change that really helped to speed the whole thing up was removing value-checking from the vector and matrix setElements methods. If you pass non-numeric values to the vector and matrix constructors, you will not get null any more, but you’ll find that method calls on the objects you get back probably break. Why you’d be using non-numeric values I don’t know, but you might find it useful, maybe for doing searches.

There are a couple of new methods:

  • Vector#each can be used to iterate over the elements of a vector.
  • Plane#isPerpendicularTo can be used to test whether two planes are at right angles to each other. I’ve not implemented this for lines, as skew lines make the definition of ‘at right angles’ a little fuzzy.

A bug has been fixed: Matrix#augment was chopping columns off due to some row/column indexes being writted the wrong way round.

And finally, 0.1.0 has some ambiguity regarding use of vectors versus plain arrays. In 0.1.1, any method that takes a vector as an argument will also accept an array. There are situations when you’ll get faster code by taking advantage of this. Methods that take matrices as arguments also accept plain arrays but you need to be careful with this feature. I’ll be writing more about use of arrays shortly.

Go and download Sylvester and let me know how you get on.

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.

Announcing Sylvester

So, after a couple of weeks beavering away on this of an evening, I’m pleased to announce the initial release of Sylvester, a vector and matrix mathematics library for Javascript. The project site has a bunch more information, and API docs for about half the code. My plan is to build this up into a 3D geometry and rendering framework over time, but I’m trying to make all the classes as generally useful as possible. I’ve seen a bunch of 3D renderers around the web and they seem to mostly be proofs of concept without a more general-purpose API. The one exception to this would be Matt Westcott’s Canvastastic, which I like a lot, but it doesn’t expose its core building blocks – vectors, matrices and the like. It has methods for multiplying specific types of matrices, but no general-purpose classes for doing this type of maths.

I want Sylvester to expose as much as possible of its functionality as useful classes so people can take the bits they like and go and write maths code for whatever they want to do. Each release will add new components that are built on top of the existing ones, so you’ll be able to take away as much or as little of the library as you need.

As always, I’d love to hear what people think – shoot suggestions and bug reports to james@jcoglan.com.