2009-11-14

Optimizing a small JavaScript loop

I recently had to optimize a visibility-checking loop, as it was causing some slowness when dealing with several hundreds of images. Executive summary: profile with Firebug, cache regex results and unchanging DOM properties.

I started with a loop like this:

imgs.forEach(function(e) {
if (isVisible(e)) {
if (e.src.match(/\/transparent\.gif$/)) {
e.src = e.getAttribute('origsrc');
}
} else if (!e.src.match(/\/transparent\.gif$/)) {
e.src = '/transparent.gif';
}
});

isVisible = function(e) {
var ctop = window.scrollY;
var cbottom = ctop + window.innerHeight;
var etop = elem.offsetTop;
var ebottom = etop + elem.offsetHeight;
var top = Math.max(ctop, etop);
var bottom = Math.min(cbottom, ebottom);
return (bottom - top) > -1200;
}

Runtime for 400 images: 35ms. Gah!

Profile says that a lot of time is spent in isVisible. But there's really nothing there that looks expensive. Let's try caching window.scrollY and window.innerHeight anyhow.

var wsy = window.scrollY;
var wih = window.innerHeight;

imgs.forEach(function(e) {
if (isVisible(e, wsy, wih)) {
...

isVisible = function(e, wsy, wih) {
var ctop = wsy;
var cbottom = ctop + wih;
...

Runtime came down to 23 ms. Whoah, that's a third off the execution time. Maybe property access is super expensive, let's see if caching elem.offsetTop and elem.offsetHeight would help as well.

isVisible = function(e, wsy, wih) {
...
if (e.cachedTop == null || !e.complete) {
e.cachedTop = e.offsetTop;
e.cachedBottom = e.cachedTop + e.offsetHeight;
}
var etop = e.cachedTop
var ebottom = e.cachedBottom
...
}

Runtime down to 15 ms. Excellent.

Profile says that the forEach loop is using a lot of time. Maybe it's the regexes. How about using RegExp.test instead of match. The docs say it should be faster.

if ((/\/transparent\.gif$/).test(e.src)) {
...
} else if (!(/\/transparent\.gif$/).test(e.src)) {


Runtime down to 12 ms. RegExp.test is indeed faster than String.match. Next, we could do away with the regexp altogether as we control which images are transparent and which are not...


imgs.forEach(function(e) {
if (e.trans == null)
e.trans = (/\/transparent\.gif$/).test(e.src);
if (isVisible(e, wsy, wih)) {
if (e.trans) {
e.src = e.getAttribute('origsrc');
e.trans = false;
e.cachedTop = e.cachedBottom = null;
}
} else if (!e.trans) {
e.src = '/transparent.gif';
e.trans = true;
e.cachedTop = e.cachedBottom = null;
}
});

Okay, now we're down to 5 ms. Finally, let's try replacing the forEach-loop with a plain for-loop.

for (var i=0; i<imgs.length; i++) {
var e = imgs[i];
...
}

Down to 3 ms. Not all that much in absolute terms, but relative to 5 ms it's 40% less. I wonder if CRAZY MICRO-OPTIMIZATIONS would do anything.

for (var i=0, l=imgs.length, e=imgs[0]; i<l; e=imgs[++i]) {
...
}

Down to ... 3 ms. No change. Well, it might be 0.3 ms faster but my measurements have a larger error than that. Ditch the micro-optimizations for readability.

And 'lo! The final code that is 10x faster than what we started with:

var wsy = window.scrollY;
var wih = window.innerHeight;

for (var i=0; i<imgs.length; i++) {
var e = imgs[i];
if (e.trans == null)
e.trans = (/\/transparent\.gif$/).test(e.src);
if (isVisible(e, wsy, wih)) {
if (e.trans) {
e.src = e.getAttribute('origsrc');
e.trans = false;
e.cachedTop = e.cachedBottom = null;
}
} else if (!e.trans) {
e.src = '/transparent.gif';
e.trans = true;
e.cachedTop = e.cachedBottom = null;
}
}

isVisible = function(e, wsy, wih) {
var ctop = wsy;
var cbottom = ctop + wih;
if (e.cachedTop == null || !e.complete) {
e.cachedTop = e.offsetTop;
e.cachedBottom = e.cachedTop + e.offsetHeight;
}
var etop = e.cachedTop
var ebottom = e.cachedBottom
var top = Math.max(ctop, etop);
var bottom = Math.min(cbottom, ebottom);
return (bottom - top) > -1200;
}

Does it work right? It seems to, at least. So maybe! Or maybe not! Isn't caching fun?

[Edit] The offsetTop and offsetHeight caching didn't work on my case, so I had to remove them. Final runtime 11 ms, or only 3x faster. Maybe some day I figure out why it didn't work...

[Edit] People have suggested using var l = imgs.length; while (l--) { ... }, which not only looks odd and reverses the iteration order, but also generates the same code as a for-loop would (on WebKit at least), according to Oliver Hunt. Well, the codegen test is for var i=0; while (i < imgs.length) i++; but i assume it also applies for for (var l=imgs.length; l--;).

[Edit] It's also somewhat strange to see suggestions that focus on optimizing all these weird things like "use object properties directly instead of local variables", instead of the possibly big things: inline isVisible, replace Math.max and Math.min with a > b ? a : b and a < b ? a : b. Well. I'll try them all and post a follow-up. Stay tuned!

[Edit] Follow-up.
Post a Comment