Saturday, October 11, 2014

JavaScript and the DOM, The Rent is Too Damn High!

Let x be a HTMLCollection of elements w/ a particular class name. Let's call it foo.

Let y be an Array of elements which need to have foo applied to it.

The algorithm is roughly:
  • For all elements in x remove the class name via Element.classList.remove().
  • For all elements in y add the class name via Element.classList.add().

Now let us assume that there is some overlap between the elements in x and y. It turns out that for some x and y it can be more than twice as fast to compute the intersection of x and y and to use that set to avoid adding and removing foo.

What makes this so weird and interesting is the fact that computing the intersection is O(x.length * y.length), while the algorithm w/o the intersection is O(x.length + y.length). In other words, the version of the algorithm where we don't compute the intersection should be faster than the version where we do. But that's not what actually happens. It's slower, 2x slower in my tests.

The only explanation I can come up w/ is that crossing the JavaScript/DOM divide remains extremely expensive compared to staying on the JavaScript side of the divide. Thus, the rent is too damn high!