Will reassigning a variable in every iteration of a loop affect performance?

Question

Consider the following two ways of writing a loop in Java to see if a list contains a given value:

Style 1

boolean found = false;
for(int i = 0; i < list.length && !found; i++)
{
   if(list[i] == testVal)
     found = true;
}

Style 2

boolean found = false;
for(int i = 0; i < list.length && !found; i++)
{
   found = (list[i] == testVal);
}

The two are equivalent, but I always use style 1 because 1) I find it more readable, and 2) I am assuming that reassigning found to false hundreds of times feels like it would take more time. I am wondering: is this second assumption true?

Nitpicker's corner

• I am well aware that this is a case of premature optimization. That doesn't mean that it isn't something that is useful to know.
• I don't care which style you think is more readable. I am only interested in whether one has a performance penalty compared to the other.
• I know that style 1 has the advantage of allowing you to also put a break; statement in the if block, but I don't care. Again, this question is about performance, not style.

Answer 1

It depends on what compiler you use since different compilers might do different optimizations.

Answer 2

I would say that in 98% of systems, it does not matter. The difference, if there is any, is hardly noticeable unless that loop is the main portion of code and is running a mindnumbing number of times.

Edit: That is ofcourse assuming that it is not being already optimized by the compiler.

Answer 3

Actually, the "if" will slow your program down more than assignment due to the pipeline.

Answer 4

Any decent compiler would keep found in a register for a duration of the loop and so the cost is absolutely negligible.

If the second style is done without a branch then it would be preferable, since the CPU's pipeline will not get disrupted as much ... but that depends on how the compiler uses the instruction set.

Answer 5

I believe style 2 is ever-so-slightly faster - say 1 clock cycle or so.

I'd rewrite it into the following, though, if I were tackling it:

for(i=0; i<list.length && list[i]!=testval; i++);
boolean found = (i!=list.length);

Answer 6

This will only be measurable in code which is extremely performance-sensitive (simulators, emulators, video encoding software, etc.) in which case you probably want to manually inspect the generated code anyway to make sure that the compiler actually generates sensible code.

Answer 7

To be sure, you should compile both versions (say with latest compiler from Sun) and examine the generated bytecode with an appropriate tool... That's the only reliable way to know for sure, everything else is wild guess.

Answer 8

It seems to me that if you expect your value to be found before the end of the list, you'd be better off with #2 - as it short circuits the check with !found in the loop conditional. Assuming you put a break in, the 1st option (the only sensible thing, IMO), then pseudo assembly would look something like:

Option 1:

start:
  CMP i, list.length
  JE end
  CMP list[i], testval
  JE equal
  JMP start
equal:
  MOV true, found
end:

Option 2:

start:
  CMP i, list.length
  JE end
  CMP true, found
  JE end
  CMP list[i], testval
  JE equal
  JNE notequal
equal:
  MOV true, found
  JMP start
notequal:
  MOV false, found
  JMP start
end:

I'd say Option 1 is superior here, as it's about 1/3rd less instructions. Of course, this is without optimizations - but that'd be compiler and situation specific (what is found doing after this? can we just optimize it away all together?).

Answer 9

boolean found = false;
for(int i = 0; i < list.length && !found; i++)
{
   if(list[i] == testVal)
     found = true;
}

I don't see a break statement in the block.

Other than that, I prefer this style. It improves readability and thereby the chance that a maintainer mis-reading and mis-fixing it.

Answer 10

Comment about nitpicks corner:

If you're really concerned with absolute performance, putting a break in and removing the "&& !found" will give you theoretically better performance on #1. Two less binary ops to worry about every iteration.

If you wanted to get really anal about optimization without using breaks then

boolean notFound = true;
    for(int i = 0; notFound && i < list.length; i++)
    {
       if(list[i] == testVal)
         notFound = false;
    }

will run faster in the average case than the existing option #1.

And of course it's personal preference, but I prefer to never put any extra evaluations inside the head of a for loop. I find it can cause confusion while reading code, because it's easy to miss. If I can't get the desired behavior using break/continues I will use a while or do/while loop instead.

Answer 11

Here is another style

for(int i = 0; i < list.length; i++)
{
   if(list[i] == testVal)
     return true;
}

return false;

Answer 12

I think both alternatives leave something to be desired, from a performance point of view.

Think about how many tests (which are almost always jumps) you do per iteration, and try to minimize the amount.

The solution by Matt, to return out when the answer is found, reduces the number of tests from three (loop iterator, found-test in loop, actual comparison) to two. Doing the "found"-test essentially twice is wasteful.

I'm not sure if the classic, but somewhat obfuscating, trick of looping backwards is a win in Java, and not hot enough at reading JVM code to figure it out right now, either.