Tail call optimization (v5)

Revision 5 of this benchmark created by Paul Grenier on


Description

See https://gist.github.com/1697037.

Preparation HTML

<script>
function tco1(f) {
  var active = false, value, accumulated, args
  return function accumulator() {
    accumulated = arguments
    if (!active) {
      active = true
      while (accumulated) {
        args = accumulated
        accumulated = null
        value = f.apply(this, args)
      }
      active = false
      return value
    }
  }
}

function tco2(fn) {
  var active, nextArgs;
  return function() {
    var result;
    nextArgs = arguments;
    if (!active) {
      active = true;
      while (nextArgs) {
        result = fn.apply(this, [nextArgs, nextArgs = null][0]);
      }
      active = false;
    }
    return result;
  };
}

function tco3(fn) {
  var active, nextArgs;
  return function() {
    var args, result;
    nextArgs = arguments;
    if (!active) {
      active = true;
      while (nextArgs) {
        args = nextArgs;
        nextArgs = null;
        result = fn.apply(this, args);
      }
      active = false;
    }
    return result;
  };
}

function tco4(fn) {
  var queue;
  return function() {
    var args, result;
    if (queue) {
      queue.push(arguments);
    } else {
      queue = [arguments];
      while ((args = queue.pop())) {
        result = fn.apply(this, args);
      }
      queue = null;
    }
    return result;
  };
}

function tco5(fn) {
  var queue;
  return function() {
    var args, result, index = 0;
    if (queue) {
      queue[queue.length] = arguments;
    } else {
      queue = [arguments];
      while ((args = queue[index++])) {
        result = fn.apply(this, args);
      }
      queue = null;
    }
    return result;
  };
}

function tco6(f) {
  var value, active = false, accumulated = []
  return function accumulator() {
    accumulated.push(arguments)
    if (!active) {
      active = true
      while (accumulated.length) value = f.apply(this, accumulated.shift())
      active = false
      return value
    }
  }
}

function tco7(f) {
    return function () {
        var bounce = f.apply(this, arguments);
        while (bounce && bounce.call) {
            bounce = bounce();
        }
        return bounce;
    };
}

function nonRecursiveSum1(x, y) {
  var args, queue = [{ 'x': x, 'y': y }];
  do {
    args = queue.pop();
    x = args.x;
    y = args.y;
    if (y > 0) {
      queue.push({ 'x': x + 1, 'y': y - 1 });
    } else if (y < 0) {
      queue.push({ 'x': x - 1, 'y': y + 1 });
    } else {
      return x;
    }
  } while (true);
}

function nonRecursiveSum2(x, y) {
  var args, index = 0, queue = [{ 'x': x, 'y': y }];
  do {
    args = queue[index++];
    x = args.x;
    y = args.y;
    if (y > 0) {
      queue[queue.length] = { 'x': x + 1, 'y': y - 1 };
    } else if (y < 0) {
      queue[queue.length] = { 'x': x - 1, 'y': y + 1 };
    } else {
      return x;
    }
  } while (true);
}

function nonRecursiveSum3(x, y) {
  var args, index = 0, queue = [[x, y]];
  do {
    args = queue[index++];
    x = args[0];
    y = args[1];
    if (y > 0) {
      queue[queue.length] = [x + 1, y - 1];
    } else if (y < 0) {
      queue[queue.length] = [x - 1, y + 1];
    } else {
      return x;
    }
  } while (true);
}

function nonRecursiveSum4(x, y) {
  var args, queue = [[x, y]];
  do {
    args = queue.pop();
    x = args[0];
    y = args[1];
    if (y > 0) {
      queue.push([x + 1, y - 1]);
    } else if (y < 0) {
      queue.push([x - 1, y + 1]);
    } else {
      return x;
    }
  } while (true);
}
</script>

Setup

var sum1 = tco1(function(x, y) {
      return y > 0 ? sum1(x + 1, y - 1) :
             y < 0 ? sum1(x - 1, y + 1) :
             x
    });
    
    var sum2 = tco2(function(x, y) {
      return y > 0 ? sum2(x + 1, y - 1) :
             y < 0 ? sum2(x - 1, y + 1) :
             x
    });
    
    var sum3 = tco3(function(x, y) {
      return y > 0 ? sum3(x + 1, y - 1) :
             y < 0 ? sum3(x - 1, y + 1) :
             x
    });
    
    var sum4 = tco4(function(x, y) {
      return y > 0 ? sum4(x + 1, y - 1) :
             y < 0 ? sum4(x - 1, y + 1) :
             x
    });
    
    var sum5 = tco5(function(x, y) {
      return y > 0 ? sum5(x + 1, y - 1) :
             y < 0 ? sum5(x - 1, y + 1) :
             x
    });
    
    var sum6 = tco6(function(x, y) {
      return y > 0 ? sum6(x + 1, y - 1) :
             y < 0 ? sum6(x - 1, y + 1) :
             x
    });
    
    var sum7 = tco7(function sum(x, y) {
      return function () {
        return y > 0 ? sum(x + 1, y - 1) :
               y < 0 ? sum(x - 1, y + 1) :
               x
        };
    });
    
    var nonRecursiveSum1 = window.nonRecursiveSum1;
    var nonRecursiveSum2 = window.nonRecursiveSum2;
    var nonRecursiveSum3 = window.nonRecursiveSum3;
    var nonRecursiveSum4 = window.nonRecursiveSum4;

Test runner

Ready to run.

Testing in
TestOps/sec
tco1
sum1(20, 1000);
ready
tco2
sum2(20, 1000);
ready
tco3
sum3(20, 1000);
ready
tco4
sum4(20, 1000);
ready
tco5
sum5(20, 1000);
ready
tco6
sum6(20, 1000);
ready
nrs1
nonRecursiveSum1(20, 1000);
ready
nrs2
nonRecursiveSum2(20, 1000);
ready
nrs3
nonRecursiveSum3(20, 1000);
ready
nrs4
nonRecursiveSum4(20, 1000);
ready
tco7
sum7(20, 1000);
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.

  • Revision 1: published by John-David Dalton on
  • Revision 3: published by JeanHuguesRobert on
  • Revision 4: published by JeanHuguesRobert on
  • Revision 5: published by Paul Grenier on
  • Revision 6: published by Virasak Dungsrikaew on
  • Revision 7: published by L8D on
  • Revision 8: published on
  • Revision 9: published by Ingvar Stepanyan on
  • Revision 10: published by Ingvar Stepanyan on
  • Revision 11: published by Ingvar Stepanyan on
  • Revision 12: published by CM on
  • Revision 13: published by CM on
  • Revision 14: published by Ingvar Stepanyan on
  • Revision 15: published by Ingvar Stepanyan on
  • Revision 16: published by Ingvar Stepanyan on
  • Revision 17: published by Ingvar Stepanyan on