Hacker News Reader

Comment by harto | Hacker News Reader

The section "The Slow Loop" posits that many for-loops in the library are much slower than they could be because they "[look] up the .length property of the array ... each time through the loop".

I wonder what the performance difference is in terms of referencing a local var vs. referencing an object property? Surely it's negligible?

View on HN

I wondered that too. I wonder if they just don't notice it because the modern VMs they mainly use would cache or inline it, but older implementations do a search for the property each time? (I'm speculating on both those points)

I think it's an oversight. The coding conventions I work with ban that form of a for-loop, precisely because the .length access can potentially be very costly. (I'm in a different part of the company, one that doesn't use Closure, but our latency constraints are even tighter than theirs are.) If you're iterating over a NodeList and not just an array, it can actually turn an O(N) loop into an O(N^2) one.

Interesting, thanks.

Checking the length of an array on each iteration of a loop is an amateur mistake, in any language. Some of these points were pretty nitpicky, but I thought this was a valid complaint.

In compiled languages it's usually not worth breaking convention to factor it out, because the compiler will apply loop-invariant code motion and pull it out of the loop body anyway. The exception is if you're calling a function that the compiler can't prove to be referentially transparent, eg. strlen.

Really interesting, thanks. I don't spend a lot of time with compiled languages these days.

Question: how can the compiler be sure an array's length wouldn't have changed? I suppose it could examine the code within the loop, but then the same could be said for strlen. What's the difference?

Most languages don't have functionality to resize an array in place. If you realloc in C, you get back a pointer that may or may not be the same as what you passed in. If you 'new' in Java, you must assign that pointer to your initial variable. If the loop body never assigns to the array, the compiler can be sure that it still points to the same block of memory, and its length will be the same.

This is a specific example of dataflow analysis, which is a fascinating area of compiler design. Usually you'll use something like a use-def chain to figure out all the points where a variable might've been defined. If all of those are outside of the loop, then the computation itself may be moved outside of the loop too, and the loop just refers to the temporary that's the result. I'd encourage you to pick up a book on compiler design if you're interested; here's the Wikipedia article:

http://en.wikipedia.org/wiki/Use-define_chain

This explicitly doesn't apply to "smart" containers like Vectors, which automatically resize themselves. If you were to inline these methods, you'd see that the internal buffer pointer may change inside the loop (assuming that you call functions that mutate the object; if you don't, and the language has a notion of const-correctness, a sufficiently smart compiler could probably optimize them too), and so the compiler can't move any code outside. Same with strlen; its return value depends upon the contents of the memory buffer pointed to, so unless the compiler can prove that that memory buffer never changes (hard; any function may reach in through a pointer and set a character to null), it can't optimize the call away.

Brilliant, thank you for the explanation and the Wikipedia link. I'm going to stop by the library this weekend to see if they have any books on compiler design, do you have any recommendations there?

Thanks again, its great to learn something new.

The classic is the "Dragon Book":

http://www.amazon.com/Compilers-Principles-Techniques-Alfred...

I'm also partial to Appel's "Modern Compiler Implementation in ML", because it goes into more detail about techniques for compiling functional languages:

http://www.amazon.com/Modern-Compiler-Implementation-Andrew-...

Great, thanks. I'll check these out.

No, because accessing a object property requires a hash table lookup.

But just stating why a more performant option exists doesn't tell us how much performance you'll squeeze out just by making this change.

In other words, it's not very helpful to say "this is so slow, you should do this instead" without at least trying to quantify the difference somehow.

I just tried it.

With 10M entries in the array, the "slow" way takes 509 ms and the "faster" way takes 362 ms. So we can save roughly 15 nanoseconds per iteration. Or a 30% speedup - assuming nothing happens inside the loop.

(Of course the numbers may vary wildly per browser.)

Somehow I doubt this is the performance problem behind slow web pages.

Agreed - which makes pointing this out as the first problem in a "gee Google can't write JavaScript article" seems a bit overblown.

In a case like this, it doesn't really matter how much of a performance benefit you get because it's ridiculously trivial to inmplement. This in particular is one of those optimizations that I remember being told back in CS101.

Reply on news.ycombinator.com