numeric-sum-benchmark.js

var Benchmark = require('benchmark');
var ndarray = require('ndarray');
var sums = require('./numeric-sums.js');

// var mean = 2;
var k = 0.1;
var mag = 100000;
function randomVector (n) {
  var v = new Float64Array(n);
  var i = n;
  while (i--) {
    v[i] = k;
  }
  return ndarray(v, [n]);
}
var n = 1000000;
var A = randomVector(n);

var suite = new Benchmark.Suite('Vector Summation');
suite.add('Pairwise summation', function () {
  var sum = sums.asumPair(A);
})
.add('Kahan summation', function () {
  var sum = sums.asumKahan(A);
})
.add('Naive summation', function () {
  var sum = sums.asumSerial(A);
})
.on('cycle', function (event) {
  console.log(String(event.target));
})
.on('complete', function () {
  console.log(' ');
  console.log('Fastest function is ' + this.filter('fastest').map('name') + '.');
  console.log(' ');
  var serialSum = sums.asumSerial(A);
  var pairSum = sums.asumPair(A);
  var kahanSum = sums.asumKahan(A);
  var trueSum = n / 10;
  console.log('True value: ' + trueSum);
  console.log('Serial error: ' + Math.abs(trueSum - serialSum));
  console.log('Pairwise error: ' + Math.abs(trueSum - pairSum));
  console.log('Kahan error: ' + Math.abs(trueSum - kahanSum));
})
.run({
  'async': false
});

numeric-sums.js

function recursiveSum (x, start, steps) {
  if (steps === 1) {
    return x.data[x.offset + start * x.stride[0]];
  }
  var n = Math.floor(steps / 2);
  var m = steps - n;
  return recursiveSum(x, start, n) + recursiveSum(x, start + n, m);
}

module.exports.asumSerial = function (x) {
  var sum = 0;
  var dx = x.data;
  var px = x.offset;
  var ox = x.stride[0];
  var i = x.shape[0];
  while (i--) {
    sum += dx[px];
    px += ox;
  }
  return sum;
};

module.exports.asumPair = function (x) {
  return recursiveSum(x, x.offset, x.shape[0]);
};

module.exports.asumKahan = function (x) {
  var sum = 0.0;
  var c = 0.0;
  var i = x.shape[0];
  var y = 0;
  var t = 0;
  while (i--) {
    y = x.get(i) - c;
    t = sum + y;
    c = (t - sum) - y;
    sum = t;
  }
  return sum;
};

They always make a note that you must ensure the compiler doesn't optimize away the kahan summation. Can't imagine that's an issue here. Is the accuracy actually what's expected for kahan?

I have yet to come up with a really good test to see if it finds error. Originally, I was trying to make it vary with large and small numbers both positive and negative. Later, I summed up 0.1 n times naively and with Kahan summation. The thinking was that the truncation error would reveal more about what's happening (still not sure if it's a good test though). For n > 100000, the Kahan result started to diverge away from the true value, but it was more accurate than pairwise summation and much more accurate than simple summation.

See: https://github.com/rreusser/summation-algorithms

There's more to untangle here, but seems like maybe the answer is just that function calls aren't that bad, but they're not that great either.