do/while Vs For: is there a real difference in performance?

[RobG]

A little while ago I opined that do/while loops are harder to
read than for loops, and therefore I preferred using for loops.

However, it was pointed out that do/while has significant
performance benefits as evidenced by:

<URL:http://www.websiteoptimization.com/speed/10/10-2.html>

(There's a bug in the page, testLoop is both a function name
and the name of the form but if you download the page & rename
the function and the call, all is OK)

So having written a poorly performing 'getElementsByClassName'
(gEBCN) function using for, I re-wrote the function using
do/while reversed which the above link would have me believe
provides a huge benefit in speed.

Using do/while reversed provides about 23% reduction in time
(averaged over 20 or so runs).

It has also been said that testing the length of an array or
collection each iteration is slower than storing it in a variable
and testing against that, i.e.

for (var i=0; i<anArray.length; i++)

is slower than:

for (var i=0, j=anArray.length; i<j; i++)

So I tested that too. Remarkably, that provides almost as big a
saving as do/while loop, 22%.

Finally, I tried a reversed for, but it was slower than a forward
loop probably because it had to evaluate i>=0 rather than i<n.

So it seems to me that for most purposes, users will not tell any
difference between a for loop and the most optimised do/while,
provided the test parameter is a constant and not some evaluated
value (as per the second for example above).

Comments?

Note: uncommenting the alerts makes the scripts report
slower times, even though the alerts are after the timed
script has finished.

--
Rob


<script type="text/javascript">

// Standard for loop
function getElementsByClassNameA(c) {
var cArray = [];
var n = document.getElementsByTagName('body')[0];
var z = new RegExp('\\b' + c + '\\b');

function doTree(n) {
if (n.className && z.test(n.className)){
cArray.push(n);
}
// Standard (slowest) loop
// for (var i=0; i<n.childNodes.length; i++) {

// using a constant forward (fastest)
for (var i=0, nLen=n.childNodes.length; i<nLen; i++) {

// using a constant and reversed loop
// for (var i=n.childNodes.length-1; i>=0; --i) {
doTree(n.childNodes);
}
}
doTree(n);
return cArray;
}

// do/while reversed
function getElementsByClassNameB(c) {
var cArray = [];
var n = document.getElementsByTagName('body')[0];
var z = new RegExp('\\b' + c + '\\b');

function doTree(n) {
if (n.className && z.test(n.className))
cArray.push(n);
var i = n.childNodes.length;
if (i) {
do {
doTree(n.childNodes[--i]);
} while (i)
}
}
doTree(n);
return cArray;
}

// just counts elements in document
function countElements() {
var c = '0';
var n = document.getElementsByTagName('body')[0];
function doCount(n) {
for (var i=0; i<n.childNodes.length; i++) {
c++;
}
}
doCount(n);
return c;
}

</script>

<table><tr><td>
<button onclick="
var s = new Date();
var classArray = getElementsByClassNameA('rob');
var f = new Date();
var t = f-s;
var c = countElements();
var u = Math.floor(t/c*1000);
/*
alert('That took ' + t + 'ms\n\n'
+ 'Element count: ' + c
+ '\nPer element: ' + u + ' microsecond');
*/
document.getElementById('A').value += '\n' + t;
">Standard for</button>
</td>
<td>
<input type="button" value="do/while reversed" onclick="
var s = new Date();
var classArray = getElementsByClassNameB('rob');
var f = new Date();
var t = f-s;
var c = countElements();
var u = Math.floor(t/c*1000);
/*
alert('That took ' + t + 'ms\n\n'
+ 'Element count: ' + c
+ '\nPer element: ' + u + ' microsecond');
*/
document.getElementById('B').value += '\n' + t;
">
</td></tr>
<tr>
<td><textarea rows="20" cols="10" id="A"
value=""></textarea></td>
<td><textarea rows="20" cols="10" id="B"
value=""></textarea></td>
</tr>
</table>

 

[bumbleguppy]

I thought I was the only one that actually saw that article. It is a
bookmark in my browser now. I also noticed the form name/function name
error lol.

It seems to me that any single isolated optimization will result in
negligable performance from the user's perspective.

My opinion is that "no single drop of water thinks it is responsible
for the flood" applies to this subject. No ONE loop optimized will make
a noticeable performance difference, but when faced with a larger
program, the milliseconds saved by multiple loops and recurring loops
COULD be perceived.

IMO, it seems that every beginning javascript programmer learns forward
"for" loops, so that is a familiar pattern. If we had learned "do"
loops first, would they be easier to read?

Either way, I use only do loops in all my javascript as per that
article. I even implemented the duff super loop 8.

 

[Dr John Stockton]

JRS: In article <[email protected]>, dated Fri, 4
Mar 2005 05:48:17, seen in RobG

A little while ago I opined that do/while loops are harder to
read than for loops, and therefore I preferred using for loops.

However, it was pointed out that do/while has significant
performance benefits
...

I did not see you testing anything matching the first loop below, which
seems to me quite readable after one has seen the construction a couple
of times :


N = 1e6
D1 = new Date()
j = N ; while (j--) {}
D2 = new Date()
for (j=0 ; j<N ; j++) {}
D3 = new Date()
for (j=N-1 ; j>=0 ; j--) {}
D4 = new Date()
x = [D2-D1, D3-D2, D4-D3] // gets 2480,4990,3850

Note - two are backwards, one forwards.

In the two FOR loops, j>=0 seems faster than j<N, as is reasonable.

Most loops will be dominated by the body of the loop; but the simplest
WHILE takes half the time of the obvious FOR ... for me.

Then
j = N ; while (j--) {}
for (j=N ; j-- ; ) {}
have similar high speeds - not surprisingly - and the second looks like
a FOR loop.


Perhaps the important point is that the increment and the test should be
combined.

 

[Lee]

Dr John Stockton said:

Perhaps the important point is that the increment and the test should be
combined.

That's my impression. The value remains in the register, rather than
having to deal with symbol tables to load it back in again for the
comparison.

I like the look of:

while (j-->0) {}

even though it's probably not as efficient as it might be.