Imperative and declarative

impdec.js

/*
 * Notes
 *
 * Make sure you know the size of your data and use proper functions or style
 * to not introduce bottlenecks by mistake.
 *
 * If we get inlined functions to Node/JS, using declarative programs will be
 * almost as fast as imperative ones by the magic of transducers. Transducers
 * will do a single pass (reduce) on the input with the composition of the
 * given transformation functions.
 *
 * As this simple example benchmark shows that the `imperative` and
 * `singlePassInlinedReduce` are performing almost at the same rate.
 *
 * Also it's worth to mention that the single pass reduce version isn't too
 * bad either; roughly ~6 times slower than the imperative one.
 *
 * Motivated by: https://jackmott.github.io/programming/2016/07/22/making-obvious-fast.html
 * Thanks Otto :)
 */

var _ = require('lodash');

/*
 * Helpers
 */

function withTime(f, ...args) {
  console.time(f.name);
  const x = f(...args);
  console.timeEnd(f.name);
  return x;
}

// Note: eager.
function range(from, until) {
  return Array
    .from(Array(until - from).keys())
    .map(x => x + from);
}

function map(f, xs) {
  const ys = [];
  for (let i = 0; i < xs.length; i++) {
    ys.push(f(xs[i]));
  }
  return ys;
}

function reduce(f, initial, xs) {
  let acc = initial;
  for (let i = 0; i < xs.length; i++) {
    acc = f(acc, xs[i]);
  }
  return acc;
}

/*
 * Implementations
 */
function imperative(values) {
  var sum = 0.0;
  for (var i = 0; i < values.length;i++){
    var x = values[i];
    sum += x*x;
  }
  return sum;
}

function declarative(values) {
  return values
    .map(x => x * x)
    .reduce((total, num) => total + num, 0);
}

function mydeclarative(values) {
  return reduce((total, num) => total + num, 0, map(x => x * x, values))
}

function twoPasses(values) {
  const ys = [];
  for (let i = 0; i < xs.length; i++) {
    ys.push(xs[i] * xs[i]);
  }

  let acc = 0;
  for (let i = 0; i < xs.length; i++) {
    acc = acc + xs[i];
  }

  return acc;
}

function singlePassNative(values) {
  return values.reduce((acc, elem) => acc + elem * elem, 0);
}

function singlePassOwn(values) {
  return reduce((acc, elem) => acc + elem * elem, 0, values);
}

function singlePassOwnInlinedReduce(values) {
  const f = (acc, elem) => acc + elem * elem
  let acc = 0;
  for (let i = 0; i < values.length; i++) {
    acc = f(acc, values[i]);
  }
  return acc;
}

function declarativeLodash(values) {
  return _.map(values, x => x * x).reduce((total, num) => total + num);
}

function singlePassLodash(values) {
  return _.reduce(values, (acc, elem) => acc + elem * elem);
}

/*
 * Run 'em.
 */
const xs = range(0, 1000000);

// call the functions a few times
// to make sure JIT kicks in
range(0, 4)
  .forEach(() => {
    [
      imperative,
      declarative,
      mydeclarative,
      twoPasses,
      singlePassNative,
      singlePassOwn,
      singlePassOwnInlinedReduce,
      declarativeLodash,
      singlePassLodash
    ].map(f => withTime(f, xs))
  });

[impdec] node -v
v8.11.3

[impdec] node impdec.js
imperative: 3.668ms
declarative: 151.109ms
mydeclarative: 25.174ms
twoPasses: 34.378ms
singlePassNative: 18.498ms
singlePassOwn: 6.514ms
singlePassOwnInlinedReduce: 4.029ms
declarativeLodash: 28.980ms
singlePassLodash: 4.072ms
imperative: 2.054ms
declarative: 150.190ms
mydeclarative: 49.298ms
twoPasses: 23.334ms
singlePassNative: 16.776ms
singlePassOwn: 9.668ms
singlePassOwnInlinedReduce: 2.077ms
declarativeLodash: 31.070ms
singlePassLodash: 15.308ms
imperative: 1.684ms
declarative: 143.548ms
mydeclarative: 52.270ms
twoPasses: 20.210ms
singlePassNative: 15.141ms
singlePassOwn: 10.253ms
singlePassOwnInlinedReduce: 2.091ms
declarativeLodash: 47.861ms
singlePassLodash: 12.131ms
imperative: 1.302ms
declarative: 142.199ms
mydeclarative: 50.875ms
twoPasses: 22.508ms
singlePassNative: 15.204ms
singlePassOwn: 9.591ms
singlePassOwnInlinedReduce: 1.349ms
declarativeLodash: 39.710ms
singlePassLodash: 12.567ms