/ functional programming

RxJs - Loop Fusion

Whether I am programming in Javascript or another language I have found that the practicing the principles of functional programming to be tremendous fun. So no matter what language or project which I am working in/on I am always trying to understand and apply new things from the world of functional programming.

Today I stumbled into the term 'Loop Fusion'. It turns out to be a wonderfully succinct way to describe a readily understood best practice. Put simply loop fusion is the act of optimizing by replacing many loops with one loop.

Anyone working in Javascript should be familiar with this already.

const a = [1, 2, 3].map(addOne).map(timesFour);
// [8, 12, 16]

The above process of transforming an array, while simple and understandable, will run slower at scale than an implementation which performs all three actions in one loop.

const a = [1, 2, 3].map((val) => {
  return timesFour(addOne(val));
});

The reason for the performance difference is the fact that there is an operational cost in moving to the next item in the array. So the second implementation calls the transforms addOne and timesFour the same number of times but benefits from moving over the array only once.

So how much of a difference does this actually make? Take a look:

// Setup an array with 1 million items
var arr = [];
for(var i = 0; i < 1000000; i++) {
  arr[i] = i;
}
// Two loops
var startTimeA = Date.now();
var a = arr.map(addOne).map(timesFour);
console.log(Date.now() - startTimeA);

// Single loop
var startTimeB = Date.now();
var b = arr.map(function(val) {
  return timesFour(addOne(val));
});
console.log(Date.now() - startTimeB);

function addOne(val) {
  return val+1;
}
function timesFour(val) {
  return val*4;
}
Loops: Two One
Milliseconds: 457 115

The single loop takes less than 25% of the time of the two loops! That's huge!

Loop Fusion in RxJs

Now, we all knew this already. Maybe not that it would be that much faster, which is arguably irrelevant as this is such a contrived example, but we knew that the single loop would be faster. So why do I bring it up today? Well obviously because loop fusion is an awesome name! But, much more importantly because when I first started looking at RxJs alarm bells were going off in my head looking at all the chained functions.

var subject = Rx.Observable.from([1,2,3]);
subject.map(addOne).map(timesFour).subscribe();

On sight this looks identical to the two loop process we looked at up above. But it's not! Certainly this simple example is just working over an array but that's not how RxJs is made to operate.

An Rx observable is built to emit one value at a time from a finite or infinite series. This value is then run through the chain of operations called on that observable. So above looks like it will loop over the array two times to accomplish the transformation but in practice it will take each value and run it through each transformation and then move on to the next. Just like the one loop method above, it's efficient.

In essence you can imagine each Observable as behaving like this:

[...arr].forEach((val) => {
  // lets imagine the chained Rx operators
  // were contained in an array-like
  return pipe(...chainedOperators);
});