How to make the fastest possible bottom-up tree transformer in JavaScript? Should I manage memory on my own?

Question

I am implementing a bottom-up tree transformer in JavaScript. It will be used for an interpreter for a supercombinator reducer, so this algorithm has to be as fast as possible, as it affects every program built on top of it. This is my current implementation:

function transform(tree,fn){
    var root = tree,
        node = tree,
        child,
        parent,
        is_node,
        dir;
    root.dir = 0;
    while(true) {
        is_node = typeof(node)==="object";
        dir = is_node ? node.dir : 2;
        if (dir < 2)
            child = node[dir],
            node.dir++,
            child.parent = parent = node,
            child.dir = 0,
            node = child;
        else if ((changed = fn(node))!==undefined)
            changed.parent = parent,
            changed.dir = 0,
            node = changed;
        else
            if (!parent)
                return node;
            else
                parent[parent.dir-1] = node,
                node = parent,
                parent = node.parent;
    };
};

// TEST
var tree = [[1,2],[[3,4],[5,6]]];
console.log(
    JSON.stringify(transform(tree,function(a){
        if (a[0]===1) return [3,[5,5]];
        if (a[0]===5) return 77;
    })) === "[[3,77],[[3,4],77]]");

This is obviously far from optimal. How do I make the transformer the fastest possible? Maybe instead of looking for a faster algorithm, I could manage the memory by myself, and use asm.js.

Answer 1

You have a couple of options, going from easiest-but-slowest to fastest-but-trickiest.

Using regular JavaScript

This is pretty much what you are doing at this point. Looking at your algorithm, I don't see anything that can really be suggested that would show anything more than an insignificant increase in speed.

Using asm.js

Using asm.js might be an option for you. This would offer a speed increase. You don't go in to a lot of details of where this system will be used, but if it works, it shouldn't be terribly difficult to implement something like this. You would likely see performance increases, but depending on how you are planning to use this, it might not be as substantial as you would like (for something like this, you'd probably see somewhere between 50%-500% increase in speed, depending how efficient the code is).

Build it in a different, compiled, typed language.

If speed is really at a premium, depending on your use case, it might be best to write this program (or at least this function) in a different language which is compiled. You could then run this compiled script on the server and communicate with it via web services.

If the number of times you need to transform the tree in a short amount of times is huge, it won't be much of a boost because of the time it would take to send and receive the data. However, if you are just doing relatively few but long-running tree transformation, you could see a huge benefit in performance. A compiled, typed language (C++, Java, etc) will always have better performance than an interpreted, typeless language like JavaScript.

The other benefit of running it on a server is you can generally throw a lot more horsepower at it, since you could write it to be multi-threaded and even run on a cluster of machines instead of just one (for a high-end build). With JavaScript, you are limited to generally one thread and also by the end-users computer.