arr-reduce-gen

JavaScript performance comparison

Test case created by G. Lathoud

Preparation code


      
      <script>
Benchmark.prototype.setup = function() {
  var n = 10000,
    arr = new Array(n);
  for (var i = n; i--;) arr[i] = i;
  
  var e_cache = {};
  
  function alp_e( /*?number | string?*/ code)
  // string->string: Complete a code expression of one or two
  // variables (e.g. '!=null' -> 'v!=null', '+' -> 'v+w').
  // 
  // Default: "identity" code:  null -> 'v'
  //
  // guillaume.lathoud@alpstein.com
  {
    if (code == null)
      code = ''; // Default (empty code) -> return the identity function
  
    if (code in e_cache)
      return e_cache[code];
  
    var is_left_implicit = /^\s*(?:[+*\/%&|\^\.=<>\?]|!=|$)/.test(code),
      is_right_implicit = /[+\-*\/%&|\^\.=<>!]\s*$/.test(code) && !/(\+\+|\-\-)$/.test(code);
    if (is_left_implicit)
      code = 'v' + code;
  
    if (is_right_implicit)
      code = code + (is_left_implicit ? 'w' : 'v');
  
    return e_cache[code] = code;
  }
  
  
  function alp_reduce( /*Array-like*/ arr, /*function: v,w,i,arr -> c | string*/ f, /*?any?*/ initialValue)
  // Reduce an array `arr` to a single value, using `f`.
  // 
  // Example:
  // {{{
  // // Sum
  // console.log( alp.reduce( [1, 2, 3, 4, 5], function (a,b) { return a+b; } ) );
  // // 15
  //
  // // Sum, expressed in a shorter manner
  // console.log( alp.reduce( [1, 2, 3, 4, 5], '+' ) );
  // // 15
  //
  // Note: when `f` is a string, a single function call happens,
  // which brings better performance, than when `f` is function
  // (`arr.length` function calls).
  // }}}
  // 
  // guillaume.lathoud@alpstein.com
  {
    var has_initialValue = arguments.length > 2;
  
    if ('string' === typeof f) {
      // Speedup: single function call (instead of `arr.length`
      // function calls).
  
      var impl;
      // cached
      if (f in alp_reduce) {
        impl = alp_reduce[f];
      }
      // not cached yet, create it
      else {
        impl = new Function(
          'arr,v,i', 'var n=arr.length;for(var w;i<n;i++){v=(w=arr[i],' + alp_e(f) + ');}return v;'
        );
        alp_reduce[f] = impl;
      }
  
      return impl(arr, /*ret:*/ has_initialValue ? initialValue : arr[0], /*i:*/ has_initialValue ? 0 : 1);
    }
  
    // arr.length function calls
  
    if (arr.reduce)
      return has_initialValue ? arr.reduce(f, initialValue) : arr.reduce(f)
  
    var n = arr.length;
    if (!n && !has_initialValue)
      throw new TypeError("reduce of empty array with no initial value");
  
    var ret = has_initialValue ? initialValue : arr[0];
  
    for (var i = has_initialValue ? 1 : 0; i < n; i++)
      ret = f(ret, arr[i], i, arr);
  
    return ret;
  }

};
</script>

Test runner

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

Java applet disabled.

Testing in CCBot 2.0.0 / Other 0.0.0
Test Ops/sec
reduce
var sum = arr.reduce(function(a, b) {
  return a + b;
});
pending…
for
var sum = 0;
for (var i = n; i--;) sum += arr[i];
pending…
reduce-gen
var sum = alp_reduce(arr, "+");
pending…

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

Compare results of other browsers

3 Comments

G. Lathoud (revision owner) commented :

If you give up on automatic expression completion ("+" -> "v+w"), then similar code can be generated using a sweet.js macro:

http://sweetjs.org/browser/editor.html#//%20macro%20reducerfunction:%20%0A//%20Declare%20a%20reducer%20function,%0A//%20and%20generate%20fast%20code%20for%20it%20%28*no*%20repetitive%20function%20call%29.%0A//%20%0A//%20Background:%20http://glat.info/mlocjs2014/#15%0A//%20Performance:%20http://jsperf.com/arr-reduce-gen%0A//%0A//%20Thanks%20to%20Adam%20Peresztegi%20for%20the%20initial%20suggestion.%0A//%0A//%20Guillaume%20Lathoud%20-%20glathoud@yahoo.fr%0A%0Amacro%20reducerfunction%20{%0A%20%20%20%20case%20{%0A%20%20%20%20%20%20%20$rf_name%20$name:ident%20%28$expr:expr%29%0A%20%20%20%20}%20=%3E%20{%0A%09%0A%09var%20v%20=%20makeIdent%28%22v%22,%20#{$rf_name}%29;%0A%09letstx%20$v%20=%20[v];%0A%09%0A%09var%20w%20=%20makeIdent%28%22w%22,%20#{$rf_name}%29;%0A%09letstx%20$w%20=%20[w];%0A%09%0A%09return%20#{%0A%20%20%20%20%20%20%20%20function%20$name%28arr%29%20{%0A%20%20%20%20%20%20%20%20var%20n%20=%20arr.length;%0A%20%20%20%20%20%20%20%20var%20i%20=%200;%0A%20%20%20%20%20%20%20%20var%20$v%20=%200;%0A%20%20%20%20%20%20%20%20for%20%28var%20$w;%20i%20%3C%20n;%20i++%29%20{%0A%20%20%20%20%20%20%20%20%20%20%20%20$v%20=%20%28$w%20=%20arr[i],%20$expr%29;%0A%20%20%20%20%20%20%20%20}%0A%20%20%20%20%20%20%20%20return%20$v%20%0A%20%20%20%20%20%20%20}%0A%09%20%20%20}%0A%20%20%20%20}%0A}%0A%0Areducerfunction%20sum%28v+w%29;%0A%0Aalert%28sum%28[1,%202,%203]%29%29;%0A

G. Lathoud (revision owner) commented :

Typo... I meant this macro:

http://sweetjs.org/browser/editor.html#//%20macro%20reducerfunction:%20%0A//%20Declare%20a%20reducer%20function,%0A//%20and%20generate%20fast%20code%20for%20it%20%28no%20repetitive%20function%20call%29.%0A//%20%0A//%20Background:%20http://glat.info/mlocjs2014/#15%0A//%20Performance:%20http://jsperf.com/arr-reduce-gen%0A//%0A//%20Thanks%20to%20Adam%20Peresztegi%20for%20the%20initial%20suggestion.%0A//%0A//%20Guillaume%20Lathoud%20-%20glathoud@yahoo.fr%0A%0Amacro%20reducerfunction%20{%0A%20%20%20%20case%20{%0A%20%20%20%20%20%20%20$rfname%20$name:ident%20%28$expr:expr%29%0A%20%20%20%20}%20=%3E%20{%0A%09%0A%09var%20v%20=%20makeIdent%28%22v%22,%20#{$rfname}%29;%0A%09letstx%20$v%20=%20[v];%0A%09%0A%09var%20w%20=%20makeIdent%28%22w%22,%20#{$rfname}%29;%0A%09letstx%20$w%20=%20[w];%0A%09%0A%09return%20#{%0A%20%20%20%20%20%20%20%20function%20$name%28arr%29%20{%0A%20%20%20%20%20%20%20%20var%20n%20=%20arr.length;%0A%20%20%20%20%20%20%20%20var%20i%20=%200;%0A%20%20%20%20%20%20%20%20var%20$v%20=%200;%0A%20%20%20%20%20%20%20%20for%20%28var%20$w;%20i%20%3C%20n;%20i++%29%20{%0A%20%20%20%20%20%20%20%20%20%20%20%20$v%20=%20%28$w%20=%20arr[i],%20$expr%29;%0A%20%20%20%20%20%20%20%20}%0A%20%20%20%20%20%20%20%20return%20$v%20%0A%20%20%20%20%20%20%20}%0A%09%20%20%20}%0A%20%20%20%20}%0A}%0A%0Areducerfunction%20sum%28v+w%29;%0A%0Aalert%28sum%28[1,%202,%203]%29%29;%0A

G. Lathoud (revision owner) commented :

In case the link does not work, here is the sweet.js macro:

// macro reducerfunction: // Declare a reducer function, // and generate fast code for it (no repetitive function call). // // Background: http://glat.info/mlocjs2014/#15 // Performance: http://jsperf.com/arr-reduce-gen // // Thanks to Adam Peresztegi for the initial suggestion. // // Guillaume Lathoud - glathoud@yahoo.fr

macro reducerfunction { case { $rfname $name:ident ($expr:expr) } => {

var v = makeIdent("v", #{$rfname});
letstx $v = [v];

var w = makeIdent("w", #{$rfname});
letstx $w = [w];

return #{
    function $name(arr) {
    var n = arr.length;
    var i = 0;
    var $v = 0;
    for (var $w; i < n; i++) {
        $v = ($w = arr[i], $expr);
    }
    return $v 
   }
   }
}

}

reducerfunction sum(v+w);

alert(sum([1, 2, 3]));