Yet More Benchmarking - Function Chains vs Object Chains
Wednesday, 15th August 2012, 13:34

Yesterday, I spent some time benchmarking different ways to deal with routing for my forthcoming Connect framework replacement for Node.js. Today I'm going to look at the stack side of things, where our matched route will be sent. I can think of a few ways this could be done, so time to put them to the test.

Iterating An Array

The most simple one this, our stack function runs through an array and calls every function in it with the request/response fields. I'm not expecting this to be the fastest method, but it will probably be quite close. Here is our code:

var runtimes = 1000000;

var stack = [ 
        doNothing,
        doNothing,
        doNothing,
        doNothing,
        doNothing,
        doNothing,
        doNothing,
        doNothing
    ];

var dtStart = new Date();

for (var runcount = 0; runcount < runtimes; runcount++)
    callStackArray();
    
var dtEnd = new Date();

console.log("Runs: " + runtimes + " Total Time: " + (dtEnd - dtStart) + "ms, Avg Time: " + (dtEnd - dtStart) / runtimes);

function doNothing()
{
    var x = Math.random();

    return true;
}

function callStackArray()
{
    var response = {};
    var request = {};
    
    for (var u = 0; u < stack.length; u++)
    {
        if (!stack[u](request, response))
            break;
    }
}

And our results are as follows:

Runs: 1000000 Total Time: 208ms, Avg Time: 0.000208

The immediate downside of this method, is every function in the stack needs to be blocking, async calls inside the stack are right out. This might not be a bad thing, as whilst perhaps it rules out middleware that does things like serve static objects, maybe that is best left to routing.

At the same time, form data may be a ruiner here, perhaps you don't want progress through your stack to continue until an entire file has been uploaded, perhaps you do so you can return a progress status? Maybe choice is the watch word.

Function Chaining

This method definitely allows for an async stack, leaving it entirely up to one middleware to call the next. In essence, this is how Connect does it, although there seems to be an awful lot of code involved in the process. For this to work we have to use a bit more code to build our function stack:

var funcstack = [
        doNothing
    ];

for (var p = 0; p < 8; p++)
    funcstack.unshift(getNothing(funcstack[0]));

function doNothing()
{
}

function getNothing(next)
{
    return function(request, response)
    {
        var x = Math.random();
    
        next(request, response);
    }
}

We start off with our doNothing() function from before, and then we add a list of functions to our stack, created by the getNothing() function. Because we have to pass it the function it should call upon completion, we have to build the array in reverse order.

Our testing function becomes simply this:

function callStackFuncChain()
{
    funcstack[0]();
}

Since all it has to do is call the first function in the stack, the remaining ones are just chained. And the results are as follows:

Runs: 1000000 Total Time: 141ms, Avg Time: 0.000141

Significantly faster than running through an array. I did a little further testing, making the doNothing() function return something, and that slowed things down a bit, but it was still faster than using an array:

Runs: 1000000 Total Time: 176ms, Avg Time: 0.000176

Object Chaining

If this proves as fast as function chaining, this would be very handy from a coding perspective. Whilst there is no reason why you couldn't create stacks dynamically (though you'd never want to do it often hopefully) with the function chaining method, if we could use chaining objects then we could do things like removing and adding an entry into a stack on the fly.

Log some data from a high volume site and then remove yourself from the stack so your impact post-log is zero. Maybe throttle connections at the start to give the database server time to get into full flow, then disappear. But let's stop thinking about it in case the performance is poor.

Our object and creation of our stack now look like this:

function StackFunction(previous, next)
{
    this.previous = previous;
    this.next = next;
}

StackFunction.prototype.doNothingIsh = function(request, response)
{
    var x = Math.random();
    
    this.next.doNothingIsh(request, response);
}

StackFunction.prototype.doNothingAfterIsh = function(request, response)
{
    var x = Math.random();
}

var objstack = [];

for (var p = 0; p < 8; p++)
    objstack.unshift(new StackFunction(null, objstack[0]));
for (p = 1; p < objstack.length; p++)
    objstack[p].previous = objstack[p - 1];
objstack[7].doNothingIsh = objstack[7].doNothingAfterIsh;

Note that here we do something a bit odd. Our stack function object is set up like a linked list, and we set the doNothingIsh function for our last entry in the list to one that doesn't call another.

Our test function just looks like this:

function callStackObjChain()
{
    var response = {};
    var request = {};
    
    objstack[0].doNothingIsh(request, response);
}

And our results are surprisingly good:

Runs: 1000000 Total Time: 115ms, Avg Time: 0.000115

Object chaining works really quickly! Faster than function chaining! Even adding a doNothing() call inside doNothingAfterIsh() has little to no effect. Further more, I made another change, inside doNothingIsh I went with:

if (this.next)
    this.next.doNothingIsh(request, response);

The hit is small as you can see, it still is more efficient than function chaining:

Runs: 1000000 Total Time: 131ms, Avg Time: 0.000131

So perhaps we'll be quite anally retentive about it all and stick with the previous method.

Conclusions

V8 appears to be very well optimised for object use, so we can go that route safe in the knowledge we have the fastest way of doing things, for now anyway.

The start of my framework now looks to be quite well set in stone. Simple string match or regexp match based routing, the choice being the users, which send requests via a stack to a destination function.

I'm probably going to scale back the benchmarking for a short while, because it is quite time consuming and much of what is to come can be written and then optimised later.