art with code

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.

6 comments:

Unknown said...

Woah, incredible gains!

Eli said...

Your "for (var i=0; i<imgs.length; i++)" loop can be optimized to "var i = imgs.length; while (i--)".

Ilmari Heikkinen said...

Eli: See CRAZY MICRO-OPTIMIZATIONS above.

Joonas said...

You are my hero. And from the same country. Interesting blog to follow.

Lon said...

Ilmari - Nicely done, it always feels good to sweeten code. Just having a quick look at your final code a few things come to mind.

First, you might consider moving the RegEx pattern instantiation outside the for loop.

Second, you may also want to create those strings ('origsrc' & '/transparent.gif') outside the loop. Depending on how smart the JS engine is, it may not realize to make those constants. Btw, if you're only targeting FF only you could actually use the 'const' keyword instead of 'var'.

Third, I think quite a few of the local variables you're using are unnecessary:

'e' (in loop) - It should be more efficient to directly use imgs[i] everywhere.

'ctop' - Why restore 'wsy' in this var? 'wsy' is already a local var.

'cbottom' - You could keep this for readibility, but it's not necessary. Actually, same for 'top' and 'bottom'

'etop' & 'ebottom' - For both, just just access the object property. There is no performance hit for accessing an object's property vs. a local var.

Consultant said...

"Maybe property access is super expensive, let's see if caching elem.offsetTop and elem.offsetHeight would help as well."

Not all property access is slow, but things like scrollX/Y and offsetXXX forces browser to flush the possible pending layout changes.

Blog Archive