Understanding the Javascript Event Loop. (And using it in interesting, powerful ways, outside of Node.js)

People new to Javascript get tripped up by it’s ‘strange’ Event Loop. It may feel like that Javascript is inconsistent, slow and inefficient. SetTimeouts, take a time, but animations based on SetTimeouts can be unreliable, and it doesn’t have predictable time.

What gives?

Well, it is well understood with the idea of a giant infinite loop wrapping your entire javascript program. It goes down executing each statement and expression in your code. Anything wrapped in a setTimeout is skipped however, and marked to be executed ‘later’.

setTimeout(<some function>,1000);

I use an ambiguous word like ‘later’ on purpose. Even though we put in 1000 milliseconds, the function may not be executed exactly 1000 milliseconds later. But it will take at least 1000 milliseconds for it to start executing. The idea is that the javascript event loop checks back after every iteration, and if the given time has not elapsed it may not come back to it on time. It’s almost like a baker occasionally checking back on the oven, while doing other things. The baker will almost never take out an unbaked cake, but may often leave the cake in the oven a few extra seconds (or minutes) after it’s done.

Let’s consider Trees.

On second thoughts, let’s just limit ourselves to binary trees.

A binary tree can be represented as an object in Javascript, with a value, left and right properties.

var BinarySearchTree = function(value){
    this.value = value;
    this.left = null; //pointer to another binary tree
    this.right = null; //pointer to another binary tree
};

I’ll skip over the part on inserting and removing values from the array and keep it only about traversal.

There are two ways a tree can be traversed. Depth-First and Breadth-First. Depth-First, it turns out, is pretty simple to understand, if you can understand recursion.

BinarySearchTree.prototype.breadthFirstLog = function(func){
    func(this.value);
    if(!!this.left){
        this.left.breadFirstTraversal(func);
    }
    if(!!this.right){
        this.right.breadFirstTraversal(func);
    }
};

The logic is simple. The first the value of the head of the tree is passed. Then each value in left tree and finally each value in the right tree. It is important to note that this algorithm works because the traversal of this.right doesn’t even start before the traversal of this.left is done. That’s what makes it depth-first. And that is the same thing that makes breadth-first an interesting problem. The synchronous way to do that is to use an array to store the values and then later call it in order.

BinarySearchTree.prototype.breadthFirstLog = function(func) {
  var levelwise = [];
  var subroutine = function(tree, level){
      if(!levelwise[level]){
        levelwise[level] = [];
      }
      levelwise[level].push(tree.value);
      subroutine(tree.left, level+1);
      subroutine(tree.right, level+1);
  };
  subroutine(this, 0);
  levelwise.forEach(function(level, index){
    if(Array.isArray(level)){
      level.forEach(func);
    }
  });
};

Here, we are still traversing the tree in a depth-first manner, but we are keeping track of how deep we are, storing the values, categorised by level in a scoped array. Then, we can go and call the given function on all of the elements in the tree in the correct order.

This approach works, and works great in most cases. But imagine if the tree was humongous. Wouldn’t the fact that we’re creating a whole new data structure be quite wasteful?

There is, in fact, a better way. And the solution is to use the Event Loop, with SetTimeout.

BinarySearchTree.prototype.breadthFirstLog = function(func) {
  func(this.value);
  var that = this;
  setTimeout(function(){
    that.left && that.left.BFSelect(func);
    that.right && that.right.BFSelect(func);
  }, 1);
};

And just like that with 1 millisecond delays, things start working in the correct order.

As you can see, by putting 1 millisecond delays, things are now happening in the correct order. But now, we have all this delay. We don’t want to wait an entire millisecond to move to the next depth-level, we want to move to the next level, as soon as we are done with the current level. Turns out that’s pretty easy. Just eliminate the 1 millisecond delay.

BinarySearchTree.prototype.breadthFirstLog = function(func) {
  func(this.value);
  var that = this;
  setTimeout(function(){
    that.left && that.left.BFSelect(func);
    that.right && that.right.BFSelect(func);
  }, 0);
};

Problem Solved.

Except. There’s one more problem. Since this process is now asynchronous, we can’t do something like this anymore:

var array = [];
myTree.breadthFirstLog(function(value){
    array.push(value);
});
console.log(array);
//=>single value.

In this case, the array will only have a single value in it, the head of the tree. Everything else will happen later. So, the only way around that is to have a callback function that needs to be called when the process is ‘done’.

BinarySearchTree.prototype.breadthFirstLog = function(callback, done){
  var that = this;
  callback(this.value);
  var callDone = (function(obj, done){
    var called = 0;
    return function(){
      called ++;
      if(called === 2){
        done(obj);
      }
    };
  })(this, done);
  setTimeout(function(){
    if(!!that.left){
      that.left.breadthFirstLog(callback, callDone);
    } else {
      callDone();
    }
    if(!!that.right){
      that.right.breadthFirstLog(callback, callDone);
    } else {
      callDone();
    }
  }, 0)
};

Problem Solved. Again.
Except now when we use this function, it looks like this:

var array = [];
myTree.breadthFirstLog(function(value){
    array.push(value);
}, function(){
    console.log(array);
    //... everything else here that depends on this code.
});

But that’s what promises are for …