TCO for fibonacci

JavaScript performance comparison

Revision 7 of this test case created by Brandon Benvie

Info

"loop" is a hand-optimized version of fibonacci. "recursion" is a tail-recursion. "tco" (tail-call-optimization) is a machine-translated version of "recursion".

Preparation code

 
<script>
Benchmark.prototype.setup = function() {
    var BOXED = {};
   
    // the max number of intermediate stack frames before dumping them
    var UNWIND_DEPTH = (function _(n){
      try { return _(n + 1) } catch (e) { return n  }
    })() / 2;
   
    /**
     * Creates a new Trampoline. These objects contain the state necessary to
     * do tail call elimination.
     *
     * @constructor
     */

    function Trampoline() {
      var self = this;
      this.unwinding = false;
      this.entered = false;
      this.depth = 0;
      this.f = null;
      this.args = null;
      this.thisArg = null;
      /**
       * The external interface for the trampoline. This function does a tail
       * eliminated call and must be used from tail position (as defined in the ES6
       * spec.) or it will break.
       * @param  {function} parent     The caller function.
       * @param  {function} f          The function to execute.
       * @param  {array}    args       The arguments to call it with.
       * @param  {any}      [thisArg]  Optional |this| to call the function with.
       * @return {any}                 The result of calling the function.
       */

      this.tailCall = function(parent, f, args, thisArg) {
        if (!self.entered) {
          return self.enter(f, args, thisArg);
        }
        self.depth = parent.depth;
        self.f = f;
        self.args = args;
        self.thisArg = thisArg;
        return BOXED;
      };
    }
   
    /**
     * Create a new Trampoline and return its `tailCall` function.
     * @return {function}  The tailCall function.
     */

    Trampoline.create = function() {
      return new Trampoline().tailCall;
    };
   
    /**
     * Start a new trampolined call stack and return the result.
     * @param  {function} f          The function to execute.
     * @param  {array}    args       The arguments to call it with.
     * @param  {any}      [thisArg]  Optional |this| to call the function with.
     * @return {any}                 The result of calling the function.
     */

    Trampoline.prototype.enter = function(f, args, thisArg) {
      if (this.entered) {
        throw new Error("Cannot enter the same Trampoline twice.");
      }
      this.depth = 0;
      this.f = f;
      this.args = args;
      this.thisArg = thisArg;
      this.entered = true;
      var result = this.execute();
      this.entered = false;
      this.depth = 0;
      this.f = null;
      this.args = null;
      this.thisArg = null;
      return result;
    };
   
    /**
     * Call a function with the given arguments and |this| and its value. This
     * handles the intricate calling interface used to allow unwinding the stack
     * at arbitrary points.
     * @param  {function} f          The function to execute.
     * @param  {array}    args       The arguments to call it with.
     * @param  {any}      [thisArg]  Optional |this| to call the function with.
     * @return {any}                 The result of calling the function.
     */

    Trampoline.prototype.execute = function() {
      var f = this.f;
      var result = f.apply(this.thisArg, this.args);
      f.depth = 0;
      if (result !== BOXED) {
        return result;
      }
   
      if (!this.depth) {
        do {
          this.f.depth = 1;
          var result = this.execute();
        } while (result === BOXED)
        this.f.depth = 0;
        return result
      }
   
      if (this.depth > UNWIND_DEPTH) {
        return BOXED;
      }
   
      this.f.depth = this.depth + 1;
      return this.execute();
    };
   
   
   
    function Frame(depth, f, args, thisArg) {
      this.depth = depth;
      this.f = f;
      this.args = args;
      this.thisArg = thisArg;
    }
   
    /**
     * Creates a new Trampoline. These objects contain the state necessary to
     * do tail call elimination.
     *
     * @constructor
     */

    function Trampoline2() {
      var self = this;
      this.entered = false;
      this.frame = null;
      /**
       * The external interface for the trampoline. This function does a tail
       * eliminated call and must be used from tail position (as defined in the ES6
       * spec.) or it will break.
       * @param  {function} parent     The caller function.
       * @param  {function} f          The function to execute.
       * @param  {array}    args       The arguments to call it with.
       * @param  {any}      [thisArg]  Optional |this| to call the function with.
       * @return {any}                 The result of calling the function.
       */

      this.tailCall = function(parent, f, args, thisArg) {
        if (!self.entered) {
          return self.enter(f, args, thisArg);
        }
        this.frame = new Frame(parent.depth, f, args, thisArg);
        return BOXED;
      };
    }
   
    /**
     * Create a new Trampoline and return its `tailCall` function.
     * @return {function}  The tailCall function.
     */

    Trampoline2.create = function() {
      return new Trampoline2().tailCall;
    };
   
    /**
     * Start a new trampolined call stack and return the result.
     * @param  {function} f          The function to execute.
     * @param  {array}    args       The arguments to call it with.
     * @param  {any}      [thisArg]  Optional |this| to call the function with.
     * @return {any}                 The result of calling the function.
     */

    Trampoline2.prototype.enter = function(f, args, thisArg) {
      if (this.entered) {
        throw new Error("Cannot enter the same Trampoline twice.");
      }
      this.frame = new Frame(0, f, args, thisArg);
      var result = this.execute();
      this.frame = null;
      return result;
    };
   
    /**
     * Call a function with the given arguments and |this| and its value. This
     * handles the intricate calling interface used to allow unwinding the stack
     * at arbitrary points.
     * @param  {function} f          The function to execute.
     * @param  {array}    args       The arguments to call it with.
     * @param  {any}      [thisArg]  Optional |this| to call the function with.
     * @return {any}                 The result of calling the function.
     */

    Trampoline2.prototype.execute = function() {
      var f = this.frame.f;
      var result = f.apply(this.frame.thisArg, this.frame.args);
      f.depth = 0;
      if (result !== BOXED) {
        return result;
      }
   
      if (!this.frame.depth) {
        do {
          this.frame.f.depth = 1;
          var result = this.execute();
        } while (result === BOXED)
        this.frame.f.depth = 0;
        return result
      }
   
      if (this.frame.depth > UNWIND_DEPTH) {
        return BOXED;
      }
   
      this.frame.f.depth = this.frame.depth + 1;
      return this.execute();
    };
   
   
    var n = 20;
   
    function makeTester(Ctor) {
      var tailCall = Ctor.create();
   
      function fib(n, a, b) {
        if (n === 0 || n === 1) {
          return a;
        }
        return tailCall(fib, fib, [n - 1, a + b, a]);
      }
   
      return function(n) {
        return fib(n, 1, 0);
      };
    }
   
   
    var fib_a = makeTester(Trampoline);
    var fib_b = makeTester(Trampoline2);
   
   
    function _recursive(n, a, b) {
      switch (n) {
        case 0:
        case 1:
          return a;
        default:
          return _recursive(n - 1, a + b, a);
      }
    }
   
    function recursive(n) {
      return _recursive(n, 1, 0);
    }
   
   
    var expected = recursive(10);
   
    [fib_a, fib_b].forEach(function(fib, index) {
      if (fib(10) !== expected) {
        throw index + " found " + fib(10);
      }
    });
   
};
</script>

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in unknown unknown
Test Ops/sec
recursive
recursive(n)
pending…
a
fib_a(n);
pending…
b
fib_b(n);
pending…

Compare results of other browsers

Revisions

You can edit these tests or add even more tests to this page by appending /edit to the URL. Here’s a list of current revisions for this page:

0 comments

Add a comment