Fastest JavaScript summation

Question

What is the fastest way to sum up an array in JavaScript? A quick search turns over a few different methods, but I would like a native solution if possible. This will run under SpiderMonkey.

Thinking very inside-the-box I have been using:

var count = 0;
for(var i = 0; i < array.length; i++)
{
    count = count + array[i];
}

I'm sure there is a better way then straight iteration.

Answer 1

You should be able to use reduce.

var sum = array.reduce(function(pv, cv) { return pv + cv; }, 0);

Source

And with arrow functions introduced in ES6, it's even simpler:

sum = array.reduce((pv, cv) => pv + cv, 0);

Answer 2

Improvements

Your looping structure could be made faster:

---

   var count = 0;
   for(var i=0, n=array.length; i < n; i++) 
   { 
      count += array[i]; 
   }

This retrieves array.length once, rather than with each iteration. The optimization is made by caching the value.

If you really want to speed it up:

---

   var count=0;
   for (var i=array.length; i--;) {
     count+=array[i];
   }

This is equivalent to a while reverse loop. It caches the value and is compared to 0, thus faster iteration.

For a more complete comparison list, see my JSFiddle.
Note: array.reduce is horrible there, but in Firebug Console it is fastest.

---

Compare Structures

I started a JSPerf for array summations. It was quickly constructed and not guaranteed to be complete or accurate, but that's what edit is for :)

Answer 3

While searching for the best method to sum an array, I wrote a performance test.

In Chrome, "reduce" seems to be vastly superior

I hope this helps

// Performance test, sum of an array
  var array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
  var result = 0;
// Eval
  console.time("eval");
  for(var i = 0; i < 10000; i++) eval("result = (" + array.join("+") + ")");
  console.timeEnd("eval");
// Loop
  console.time("loop");
  for(var i = 0; i < 10000; i++){
    result = 0;
    for(var j = 0; j < array.length; j++){
      result += parseInt(array[j]);
    }
  }
  console.timeEnd("loop");
// Reduce
  console.time("reduce");
  for(var i = 0; i < 10000; i++) result = array.reduce(function(pv, cv) { return pv + parseInt(cv); }, 0);
  console.timeEnd("reduce");
// While
  console.time("while");
  for(var i = 0; i < 10000; i++){
    j = array.length;
    result = 0;
    while(j--) result += array[i];
  }
  console.timeEnd("while");

eval: 5233.000ms

loop: 255.000ms

reduce: 70.000ms

while: 214.000ms

Answer 4

Or you could do it the evil way.

var a = [1,2,3,4,5,6,7,8,9];

sum = eval(a.join("+"));

;)

Answer 5

The fastest loop, according to this test is a while loop in reverse

var i = arr.length; while (i--) { }

So, this code might be the fastest you can get

Array.prototype.sum = function () {
    var total = 0;
    var i = this.length; 

    while (i--) {
        total += this[i];
    }

    return total;
}

Array.prototype.sum adds a sum method to the array class... you could easily make it a helper function instead.

Answer 6

For your specific case, just use the reduce method of Arrays:

var sumArray = function() {
    // Use one adding function rather than create a new one each
    // time sumArray is called
    function add(a, b) {
        return a + b;
    }

    return function(arr) {
        return arr.reduce(add);
    };
}();

alert( sumArray([2, 3, 4]) );

Answer 7

Based on this test (for-vs-forEach-vs-reduce) and this (loops)

I can say that:

1# Fastest: for loop

var total = 0;

for (var i = 0, n = array.length; i < n; ++i)
{
    total += array[i];
}

2# Aggregate

For you case you won't need this, but it adds a lot of flexibility.

Array.prototype.Aggregate = function(fn) {
    var current
        , length = this.length;

    if (length == 0) throw "Reduce of empty array with no initial value";

    current = this[0];

    for (var i = 1; i < length; ++i)
    {
        current = fn(current, this[i]);
    }

    return current;
};

Usage:

var total = array.Aggregate(function(a,b){ return a + b });

Inconclusive methods

Then comes forEach and reduce which have almost the same performance and varies from browser to browser, but they have the worst performance anyway.

Answer 8

I tried using performance.now() to analyze the performance of the different types of loops. I took a very large array and found the sum of all elements of the array. I ran the code three times every time and found forEach and reduce to be a clear winner.

// For loop

let arr = [...Array(100000).keys()]
function addUsingForLoop(ar){
  let sum = 0;
  for(let i = 0; i < ar.length; i++){
    sum += ar[i];
  }
   console.log(`Sum: ${sum}`);
   return sum;
}
let t1 = performance.now();
addUsingForLoop(arr);
let t2 = performance.now();
console.log(`Time Taken ~ ${(t2 - t1)} milliseconds`)

// "Sum: 4999950000"
// "Time Taken ~ 42.17500000959262 milliseconds"
// "Sum: 4999950000"
// "Time Taken ~ 44.41999999107793 milliseconds"
// "Sum: 4999950000"
// "Time Taken ~ 49.845000030472875 milliseconds"

// While loop

let arr = [...Array(100000).keys()]
function addUsingWhileLoop(ar){
let sum = 0;
let index = 0;
while (index < ar.length) {
  sum += ar[index];
  index++;
}
  console.log(`Sum: ${sum}`)
  return sum;
}
let t1 = performance.now();
addUsingWhileLoop(arr);
let t2 = performance.now();
console.log(`Time Taken ~ ${(t2 - t1)} milliseconds`)

// "Sum: 4999950000"
// "Time Taken ~ 44.2499999771826 milliseconds"
// "Sum: 4999950000"
// "Time Taken ~ 44.01999997207895 milliseconds"
// "Sum: 4999950000"
// "Time Taken ~ 41.71000001952052 milliseconds"

// do-while

let arr = [...Array(100000).keys()]
function addUsingDoWhileLoop(ar){
let sum = 0;
let index = 0;
do {
   sum += index;
   index++;
} while (index < ar.length);
   console.log(`Sum: ${sum}`);
   return sum;
}
let t1 = performance.now();
addUsingDoWhileLoop(arr);
let t2 = performance.now();
console.log(`Time Taken ~ ${(t2 - t1)} milliseconds`)

// "Sum: 4999950000"
// "Time Taken ~ 43.79500000504777 milliseconds"
// "Sum: 4999950000"
// "Time Taken ~ 43.47500001313165 milliseconds"
// "Sum: 4999950000"
// "Time Taken ~ 47.535000019706786 milliseconds"

// Reverse loop

let arr = [...Array(100000).keys()]
function addUsingReverseLoop(ar){
   var sum=0;
   for (var i=ar.length; i--;) {
     sum+=arr[i];
   }
   console.log(`Sum: ${sum}`);
   return sum;
}
let t1 = performance.now();
addUsingReverseLoop(arr);
let t2 = performance.now();
console.log(`Time Taken ~ ${(t2 - t1)} milliseconds`)

// "Sum: 4999950000"
// "Time Taken ~ 46.199999982491136 milliseconds"
// "Sum: 4999950000"
// "Time Taken ~ 44.96500000823289 milliseconds"
// "Sum: 4999950000"
// "Time Taken ~ 43.880000011995435 milliseconds"

// Reverse while loop

let arr = [...Array(100000).keys()]
function addUsingReverseWhileLoop(ar){
    var sum = 0;
    var i = ar.length; 
    while (i--) {
        sum += ar[i];
    }
    console.log(`Sum: ${sum}`);
    return sum;
}
var t1 = performance.now();
addUsingReverseWhileLoop(arr);
var t2 = performance.now();
console.log(`Time Taken ~ ${(t2 - t1)} milliseconds`)

// "Sum: 4999950000"
// "Time Taken ~ 46.26999999163672 milliseconds"
// "Sum: 4999950000"
// "Time Taken ~ 42.97000000951812 milliseconds"
// "Sum: 4999950000"
// "Time Taken ~ 44.31500000646338 milliseconds"

// reduce

let arr = [...Array(100000).keys()]
let t1 = performance.now();
sum = arr.reduce((pv, cv) => pv + cv, 0);
console.log(`Sum: ${sum}`)
let t2 = performance.now();
console.log(`Time Taken ~ ${(t2 - t1)} milliseconds`)

// "Sum: 4999950000"
// "Time Taken ~ 4.654999997001141 milliseconds"
// "Sum: 4999950000"
// "Time Taken ~ 5.040000018198043 milliseconds"
// "Sum: 4999950000"
// "Time Taken ~ 4.835000028833747 milliseconds"

// forEach

let arr = [...Array(100000).keys()]
function addUsingForEach(ar){
  let sum = 0;
  ar.forEach(item => {
    sum += item;
  })
    console.log(`Sum: ${sum}`);
    return sum
}
let t1 = performance.now();
addUsingForEach(arr)
let t2 = performance.now();
console.log(`Time Taken ~ ${(t2 - t1)} milliseconds`)

// "Sum: 4999950000"
// "Time Taken ~ 5.315000016707927 milliseconds"
// "Sum: 4999950000"
// "Time Taken ~ 5.869999993592501 mienter code herelliseconds"
// "Sum: 4999950000"
// "Time Taken ~ 5.405000003520399 milliseconds"

Answer 9

one of the simplest, fastest, more reusable and flexible is:

Array.prototype.sum = function () {
    for(var total = 0,l=this.length;l--;total+=this[l]); return total;
}

// usage
var array = [1,2,3,4,5,6,7,8,9,10];
array.sum()

Answer 10

What about summing both extremities? It would cut time in half. Like so:

1, 2, 3, 4, 5, 6, 7, 8; sum = 0

2, 3, 4, 5, 6, 7; sum = 10

3, 4, 5, 6; sum = 19

4, 5; sum = 28

sum = 37

One algorithm could be:

function sum_array(arr){
    let sum = 0,
        length = arr.length,
        half = Math.floor(length/2)

    for (i = 0; i < half; i++) {
        sum += arr[i] + arr[length - 1 - i]
    }
    if (length%2){
        sum += arr[half]
    }
    return sum
}

It performs faster when I test it on the browser with performance.now(). I think this is a better way. What do you guys think?

Answer 11

Here is a jsPerf for all variations from @Ankur´s answer with some minor modifications:

https://jsben.ch/J6ywV

Changes:

1. There is performance difference between summing up an array of [1,2,3,..,n] or [n,n-1,n-2,..,1].

   Tests labeled with (reversed array) run the same test-fn with a reversed test array. They always outperform their counterpart.

2. console.log(`Sum: ${sum}`) has a negativ impact for the measurement and were removed (it takes time to render the output).

3. I added bench for reduceRight().

For more relyable results you might want to run each test several times, with different arrays to get an average runtime.

// Test functions
let fn_reduce = a => a.reduce((pv, cv) => pv + cv, 0);
let fn_reduceRight = a => a.reduceRight((pv, cv) => pv + cv, 0);
let tests = [fn_reduce, fn_reduceRight];

// Test config
let runs = 8;     // test runs
let length = 100000; // array length
// .. test with "array" and "reversed array"
let arr1 = Array.from({length}, (_, i) => i);
let arr2 = Array.from({length}, (_, i) => length - i - 1);

let out = [];
let outGrouped = {};
for(let i = 0; i < runs; i++){
  tests.forEach(fn => {
    (i % 2 ? [arr1, arr2] : [arr2, arr1]).forEach(arr => {
        let isArrayReverse = arr !== arr1;
        let sum = 0;
        let t1 = performance.now();

        sum = fn(arr);

        let t2 = performance.now();
        let duration = t2 - t1;
        out.push({run: i, fn: fn.name, isArrayReverse, duration});

        let group = `${fn.name}_${isArrayReverse}`;
        outGrouped[group] ??= {fn: fn.name, isArrayReverse, duration: 0, runs: 0};
        outGrouped[group].duration += duration;
        outGrouped[group].runs++;
    });
  });
}

//console.log('out'); // detailed output

console.log('OPEN DEV-TOOLS for console.table()!');
console.log('Sort by "avg" column.');

console.table(Object.fromEntries(Array.from(Object.entries(outGrouped), ([group, {duration, runs, ...rest}]) => [group, {...rest, avg: duration / runs, duration, runs}])));