Checking condition in loop

Question

I would like to ask more experienced developers about one simple, but for me not obvious, thing. Assume you have got such a code (Java):

for(int i=0; i<vector.size(); i++){
   //make some stuff here
}

I came across such statements very often, so maybe there is nothing wrong in it. But for me, it seems unnecessary to invoke a size method in each iteration. I would use such approach:

int vectorSize = vector.size();
for(int i=0; i<vectorSize; i++){
    //make some stuff here
}

The same thing here:

for(int i=0; i<myTreeNode.getChildren().size(); i++){
   //make some stuff here
}

I am definitely not an expert in programming yet, so my question is: Am I seeking a gap where the hedge is whole or it is important to take care of such details in professional code?

Thanks - I had some problems with finding answer for this question... — radekEm, Apr 25 '13 at 19:06
Sometimes, you modify the size of the Vector inside the loop. There's nothing wrong with getting the size beforehand, especially if the size call is expensive. Vector size is not an expensive call, however. Just understand why you would get the size before you start the loop and understand why you want to check the size after each iteration of the loop. — Gilbert Le Blanc, Apr 25 '13 at 19:07

score 8 · Accepted Answer · edited Apr 25 '13 at 19:21

A method invocation requires that the JVM does indeed do additional stuff. So what you're doing, at first view seems like an optimization.

However, some JVM implementations are smart enough to inline method calls, and for those, the difference will be nonexistent.

The Android programming guidelines for example always recommend doing what you've pointed out, but again, the JVM implementation manual (if you can get your hands on one) will tell you if it optimizes code for you or not.

Zim-Zam O'Pootertoot · Answer 2 · 2013-04-25T19:13:00.307

Usually size() is a small constant-time operation and so the cost of calling size is trivial compared to the cost of executing the loop body, and the just in time compiler may be taking care of this optimization for you; therefore, there may not be much benefit to this optimization.

That said, this optimization does not adversely affect code readability, so it isn't something to be avoided; often code optimizations that only affect speed by a small factor (as opposed to e.g. an optimization that changes a O(n) operation to a O(1) operation) should be avoided for this reason, for example you can unroll a loop:

int i;
int vectorSizeDivisibleBy4 = vectorSize - vectorSize % 4; // returns lowest multiple of four in vectorSize
for(i = 0; i < vectorSizeDivisibleBy4; i += 4) {
    // loop body executed on [i]
    // second copy of loop body executed on [i+1]
    // third copy of loop body executed on [i+2]
    // fourth copy of loop body executed on [i+3]
}
for(; i < vectorSize; i++) { // in case vectorSize wasn't a factor of four
    // loop body
}

By unrolling the loop four times you reduce the number of times that i < vectorSize is evaluated by a factor of four, at the cost of making your code an unreadable mess (it might also muck up the instruction cache, resulting in a negative performance impact). Don't do this. But, like I said, int vectorSize = vector.size() doesn't fall into this category, so have at it.

but of course, as the lad suspected, a constant time operation takes more than a no-time operation. nice contribution though;) cheers — vlad-ardelean, Apr 25 '13 at 19:12

score 0 · Answer 3 · answered Apr 25 '13 at 19:16

At the 1st sight the alternative you are suggesting seams an optimization, but in terms of speed it is identical to the common approach, because of:

the complexity time of the call of size() function in a java vector has a complexity of order O(1) since each vector has always stored a variable containing its size, so you don't need to calculate its size in each iteration, you just access it.

note: you can see that the size() function in: http://www.docjar.com/html/api/java/util/Vector.java.html is just returning a protected variable elementCount.

Checking condition in loop

3 Answers3