JavaScript: Direct code vs CPS styled generated code performance comparison

Question

In my application i am generating JavaScript code which is following CPS style. I am 'not' using any 'continuations' as such. No async behavior, No pause and resume, and No callbacks.

Just that the code is following a continuation passing style of programming.

There are many stages to the functionality, each stage does its processing and passes the result to its continuation.

What i find is that performance of CPS styled code is very poor. Code written in direct style is almost 150 times faster than the CPS styled code.

Please check the below code.
Both below codes are equivalent to

var res = data.store.bookshelf.book.author;

Direct Styled Code :

var data = { store : { bookshelf : {book : {author:"Douglas Crockford"}}}};
var t1 = new Date().getTime();
for(var i = 0; i < 1000*1000*100; i+=1){      
  var temp0 = data;
  var temp1 = temp0.store;
  var temp2 = temp1.bookshelf;
  var temp3 = temp2.book;
  var temp4 = temp3.author;
  var res = temp4;
}
var t2 = new Date().getTime();
console.log(t2-t1);

The above code runs in almost 95 ms.

CPS Styled Code:

var data = { store : { bookshelf : {book : {author:"Douglas Crockford"}}}};

// return the variable to the continuation
function cps_VARREF(x,f){
  return f(x);
}
// get the value of the property from the variable and pass it to the continuation
function cps_CHILD(x,child,f){
  return f(x[child]);
}
// simply return the input value, essentially closing the continuation chain
function ret_(x){
  return x;
}

var t1 = new Date().getTime();
for(var i = 0; i < 1000*1000*100; i+=1){
 var res = function(c_){
    return cps_VARREF(data,function(x1){
    return cps_CHILD(x1,"store",function(x2){
    return cps_CHILD(x2,"bookshelf",function(x3){
    return cps_CHILD(x3,"book",function(x4){
    return cps_CHILD(x4,"author",c_);});});});});}(ret_);
}
var t2 = new Date().getTime();
console.log(t2-t1);

The above CPS styled code runs in 15000 ms

Is there anything i can do to improve the CPS styled code? OR JavaScript is inherently not suitable for CPS styled code?

The above tests are done on node.js version 0.6.12

Can someone please throw some light on this issue?

Thanks,

Answer 1

There are at least two potential causes for the dramatic slowdown. The first is that you're replacing "native" property lookups with dynamic lookups.

V8 optimizes objects whenever it can so accessing properties is faster. Instead of using a hash table to look up properties by name, it keeps track of an internal "class" so it can look up properties from a known address. So data.store is just a quick pointer comparison to make sure the object is the expected type and an indexed pointer load.

In the cps_CHILD function though, it can't do that optimization because it doesn't know what property is going to be accessed ahead of time (and it changes each time you call it). The dynamic lookup forces V8 to fall back to a hash table lookup, which is slower than the optimized, static lookup.

The other problem is overhead from the function calls. Each nested function has to be recreated every time it's passed on to the next function. They shouldn't need to be compiled each time, but it still needs to be created in its new context.

Answer 2

You should know that some things are parsed at runtime, like those anonymous functions you entered in loop. On each new "i" again new "constructor" will be created and its prototype for each anonymus function. That's why it is slower. Here is new test. Try to define actual function for each anonymous function, nest them outside loop, it should improve performance of your program.

Here is code, it goes deep as in your CPS styled code but only once functions are defined

var data = { store : { bookshelf : {book : {author:"Douglas Crockford"}}}};

function getValueFrom(data){
    return data;
}

function getAuthorFrom(data){
    return getValueFrom(data);
}

function getBookFrom(data){
    return getAuthorFrom(data["book"]);
}

function getBookShelfFrom(data){
    return getBookFrom(data["bookshelf"]);
}

function getStoreFrom(data){
    return getBookShelfFrom(data["store"]);
}

function getAuthor(data){
    return getAuthor(data);
}

var t1 = new Date().getTime();
for(var i = 0; i < 1000*1000*100; i+=1){
 var res = getStoreFrom(data);
}
var t2 = new Date().getTime();
console.log(t2-t1);

it runs 4-5 times faster. It is still slower since JS engine need to seek for function prototype, so it can be putted on heap for execution. In your first case (non CSP style) when you use dot acces to property JS engine only queries hash by key (JS object property) to get its value. It works much quicker since it only need to deal with memory references.