DailyJS

ES6 Generator Performance in V8

Daishi Kato

Subscribe

@dailyjs

Facebook

Google+

node modules npm ES6

ES6 Generator Performance in V8

Posted by Daishi Kato on .
Featured

node modules npm ES6

ES6 Generator Performance in V8

Posted by Daishi Kato on .
This is a guest post written by Daishi Kato.

Node's getting ES6 generators -- otherwise known as the yield keyword. For those who are not familiar with generators, here is a simple example that will yield a value up to five times when onetofive is called.

function* onetofive() {  
  yield 1;
  yield 2;
  yield 3;
  yield 4;
  return 5;
}

It's hard to see why that's useful until we introduce a loop. We can call onetofive repeatedly like this:

function run() {  
  var iterator = onetofive();
  obj = {};
  // Assuming obj.done is a boolean
  while (!obj.done) {
    obj = iterator.next();
    // do something with obj.value
    // ex. console.log(obj.value);
  }
}

See what's happening? We're able to use a standard loop keyword yet provide an asynchronous API.

When I ran this a million times, it took 360ms. Now, I know yield is much more descriptive and you can even send a value back, but we should compare it to the equivalent hand-written generator code.

function onetofive() {  
  var array = [1, 2, 3, 4, 5];
  var index = 0;
  var iterator = {
    next: function() {
      return { value: array[index++], done: array.length <= index };
    }
  };
  return iterator;
}

Running this version with the previous condition took 265ms, which is comparable or a little faster.

The reason why I was investigating generators is because I am interested in how yield can be used to write tail-recursive code.

Let's look at this idea in more detail. The following is a factorial function in a tail-recursive manner.

function fact_tail(x) {  
  var fact_tail_sub = function(x, r) {
    if (x === 0) {
      return r;
    } else {
      return fact_tail_sub(x - 1, x * r);
    }
  };
  return fact_tail_sub(x, 1);
}

It's relatively easy to follow, but it will consume a call stack for each sub function call. TCO (Tail Call Optimization) avoids such consumption, and we can use yield for TCO like the following:

function fact_tail_loop(x) {  
  var fact_tail_sub = function* (x, r) {
    if (x === 0) {
      return r;
    } else {
      yield fact_tail_sub(x - 1, x * r);
    }
  };
  var c = fact_tail_sub(x, 1);
  var d = {};
  while (!d.done) {
    d = c.next();
    c = d.value;
  }
  return d.value;
}

Here there is no recursive call and it doesn't exhaust the call stack. Note the similarity of fact_tail_sub with the previous example.

When I ran it several times with different values of x, it took 217ms. That isn't bad, but I can do it a little differently without yield:

function fact_tail_loop2(x) {  
  var LoopCont = function(f) {
    this.f = f;
  };

  var fact_tail_sub = function(x, r) {
    if (x === 0) {
      return r;
    } else {
      return new LoopCont(function() {
        return fact_tail_sub(x - 1, x * r);
      });
    }
  };

  var c = fact_tail_sub(x, 1);
  while (c instanceof LoopCont) {
    c = c.f();
  }

  return c;
}

This is harder to understand, but the behavior is similar to the previous code. When I ran it with the same condition as the previous example, it took 63ms, which is much faster. By the way, this transformation is exactly what is done in https://github.com/dai-shi/continuation.js.

My observation at this point is that the code using yield doesn't improve performance compared to the code which is carefully written like a generator. However, the performance characteristics might change if the optimization of generators goes well in V8 -- and I hope it will.

* The evaluation is done with node-v0.11.5 on Intel Core2 Duo@3GHz PC.