Do you really know how for-loops work? How to speed up your for loops

10

Did you know that the second parameter of a three parameter for loop gets executed on every loop? When this parameter is an expensive operation this could slow down your application. Of course I knew the second parameter gets executed every time, but I didn’t realize what kind of impact this had until I read an article and ran some tests. This ‘theory’ applies to every programming language with for-loops so it may be useful to every programmer/scripter.
When I ran some tests on Javsascript I discovered some for loops could be a 100 times faster!
....

Probably every programmer knows the second parameter is executed on every loop. But I think a lot of developers don’t realize the impact of this. I recently read an article about improving Javascript that opened my eyes. The tip in the article had something to do with assigning function pointers to local variables when you use them a lot, with a for-loop as an example.
Let me demonstrate what happens with a simple java example. I know everybody knows the outcoume, but you can’t see it enough.

public void testLoop() {<br />    for (int i = 0; i &lt; getLength(); i++) {<br />        // do nothing<br />    }<br />}<br /><br />private int getLength() {<br />    System.out.println(&quot;Are we there yet?&quot;);<br />    return 10;<br />} <br />

“Are we there yet?” is printed 10 times. In this case (and most cases for for-loops) we only need to execute the getLength() method 1 time because we know it’s value stays the same. When the getLength() method was a very expensive operation it was executed 9 times too much (with a cheap operation too, but you wouldn’t have noticed)

I ran some test on Javascript and that really scared me. I created a table with 72 cells and looped through every cell with:

document.getElementById('t').getElementsByTagName('td')

Stupid as I am my for loop looks like this:

for (var i = 0; i &lt; document.getElementById('t').getElementsByTagName('td').length; i++) {<br />     }<br />

And it should like this:

var l = document.getElementById('t').getElementsByTagName('td').length;<br />for (var i = 0; i &lt; l; i++) {<br />}<br />

So let’s cut to the case. These two snippets produce exactly the same result, the second example though runs about a 160 times faster in my FireFox and about 100 times faster in Internet Explorer. Wow! And this doesn’t look like an expensive operation in my opinion. Note that I ran the test several times and the for-loops were nested inside another for loop (the first set ran 5000 times and the second set 50000 to get a good idea of how long it took)

In java I created an ArrayList with about 40 Strings in it and did the same for-loop test. The list.size(); test was about 6 times slower than assinging a local variable.

Don’t think you can speed up every for loop 6 times (or 100 times), usually for loops are not empty, but assigning a local variable might improve things a bit, especially for a huge load of loops. The slow empty for-loop in Javascript took 1.6ms each time, with 72 cells this is already noticable.

Conclusion

So what should you do know? Search for for-loops throughout your application and search for expensive operations in your for loop. When you’re a Javascripter check al DOM-operations in for-loops, these operations are relatively slow and you usually need the operation only once. It’s also a good idea to read the Javscript article, it might help you. Look for .length in Javascript, .length seems innocent, but it might just give you the performance boost you need.
It’s code-wise also better to assign the second parameter to a local variable, it makes your code more readable and why make unnecessary method calls?
I know this article wan’t rocket science, but a lot of people forget the impact of a method call in a for-loop.

Source

IEBlog : IE + JavaScript Performance Recommendations – Part 1

Share.

About Author

10 Comments

  1. This is such basic stuff, that it should not need a blog article, but I see so many idiots do this!

    Much like the frequent and painful abuse of String in Java, like:
    String s = “”
    for (int i=0; i=0; ) {} //Note that i does not go negative inside the loop.

  2. You could also do:

    for (var i = 0, len = document.getElementById(‘t’).getElementsByTagName(‘td’).length; i

  3. Even in java:

    for (int i=0; i=0; i--) {} // comparing with 0 is faster but it leads to slightly not very clean code and the difference is not big ;)<br />&nbsp;

    and sure most of the time iterators and enhanced for loops are being used anyway

  4. The JVM _can_ actually determine if the value could change… but since you’re probably using unsynchronized collections the size of a collection can actually change during your for loop. I’ve seen this latter happening inside Hibernate where they use your proposed construction; it’s faster but with a trade-of.

  5. “And this doesn’t look like an expensive operation in my opinion.”

    Well, “document.getElementById(‘t’).getElementsByTagName(‘td’).length” is quite an expensive operation, particularly in JavaScript. It’s about as expensive an operation as you’re likely to find on the end of a for loop! Remember that even looking up an identifier in JavaScript needs to consult a hash table. So, the above expression would have to:

    * Lookup “document” in the global identifiers.
    * Lookup “getElementById” in the document object’s dictionary.
    * Execute the “getElementById” function, passing ‘t’ as an argument.
    * Look throughout the document for an element with the id ‘t’. This is rather expensive, depending on how the browser indexes element IDs (could be cheap).
    * Check to make sure the returned object is not null; if so throw an exception.
    * Lookup “getElementsByTagName” on the returned object’s dictionary.
    * Execute the “getElementsByTagName” function, passing ‘td’ as an argument.
    * The killer: Search the entire document tree, doing a string comparison against _every_ element’s tag name, and doing a list insert for all successful elements. The browser could intelligently hash tag names but I don’t think they do.
    * Finally lookup “length” in the returned list object’s dictionary.
    * And execute the “length” function, which cheaply returns the length as an integer.

    So it is rather a good example then, of the perfect expression which deserves to be thrown with great vigour out of the loop body!

  6. Jeroen van Wilgenburg on

    Thanks prashant.
    >> sezgin: How can the JVM know that value of the method you’re calling never changes? And when the JVM optimizes this I should’ve got other test results. I’m sure the JVM optimizes certain things, but it is better when you optimze the for loops yourself, because the JVM doesn’t know everything.

  7. Hi,

    Good simple article.I liked it and am also not aware of this till now having almost 3.7 yrs experience. :-)

    Thanks
    Prashant

  8. JVM optimizes this kind of things .So I don’t worry about that for Java.But worry for javascript.