21

I got this idea from this question on stackoverflow.com

The following pattern is common:

final x = 10;//whatever constant value
for(int i = 0; i < Math.floor(Math.sqrt(x)) + 1; i++) {
  //...do something
}

The point I'm trying to make is the conditional statement is something complicated and doesn't change.

Is it better to declare it in the initialization section of the loop, as such?

final x = 10;//whatever constant value
for(int i = 0, j = Math.floor(Math.sqrt(x)) + 1; i < j; i++) {
  //...do something
}

Is this more clear?

What if the conditional expression is simple such as

final x = 10;//whatever constant value
for(int i = 0, j = n*n; i > j; j++) {
  //...do something
}
12
  • 47
    Why not just move it to the line before the loop, then you can give it a sensible name too.
    – jonrsharpe
    Dec 29, 2016 at 17:49
  • 2
    @Mehrdad: They're not equivalent. If x is large in magnitude, Math.floor(Math.sqrt(x))+1 is equal to Math.floor(Math.sqrt(x)). :-) Dec 30, 2016 at 1:19
  • 5
    @jonrsharpe Because that would widen the scope of the variable. I'm not necessarily saying that's a good reason not to do it, but that is the reason some people don't. Dec 30, 2016 at 7:29
  • 3
    @KevinKrumwiede If scope is a concern limit it by putting the code in its own block , e.g., { x=whatever; for (...) {...} } or, better yet, consider whether there's enough going on that it needs to be a separate function.
    – Blrfl
    Dec 30, 2016 at 14:51
  • 2
    @jonrsharpe You can give it a sensible name when declaring it in the init section too. Not saying I would put it there; it's still easier to read if it's separate.
    – JollyJoker
    Dec 30, 2016 at 15:50

5 Answers 5

62

What I'd do is something like this:

void doSomeThings() {
    final x = 10;//whatever constant value
    final limit = Math.floor(Math.sqrt(x)) + 1;
    for(int i = 0; i < limit; i++) {
         //...do something
    }
}

Honestly the only good reason to cram initializing j (now limit) into the loop header is to keep it correctly scoped. All it takes to make that a non issue is a nice tight enclosing scope.

I can appreciate the desire to be fast but don't sacrifice readability without a real good reason.

Sure, the compiler may optimize, initializing multiple vars may be legal, but loops are hard enough to debug as it is. Please be kind to the humans. If this really does turn out to be slowing us down it's nice to understand it enough to fix it.

4
  • Good point. I would assume not to bother with another variable if the expression is something simple, for example for(int i = 0; i < n*n; i++){...} you wouldn't assign n*n to a variable would you?
    – Celeritas
    Dec 29, 2016 at 18:13
  • 1
    I would and I have. But not for speed. For readability. Readable code tends to be fast on its own. Dec 29, 2016 at 22:35
  • 1
    Even the issue of scoping it goes away if you mark is as a constant (final). Who cares if a constant that has compiler enforcement preventing it from changing is accessible later in the function?
    – jpmc26
    Dec 30, 2016 at 9:08
  • I think a big thing is what you expect to happen. I know the example uses the sqrt but what if it was another function? Is the function pure? Are you always expecting the same values? Are there side effects? Are the sides effects something you intend to happen on every iteration?
    – Pieter B
    Dec 30, 2016 at 13:56
38

A good compiler will generate the same code either way, so if you are going for performance, only make a change if it is in a critical loop and you have actually profiled it and found it makes a difference. Even if the compiler can't optimize it, as people have pointed out in the comments about the case with function calls, in the vast majority of situations, the performance difference is going to be too small to be worth a programmer's consideration.

However...

We must not forget that code is primarily a medium of communication between humans, and both your options do not communicate to other humans very well. The first gives the impression that the expression needs to be calculated upon every iteration, and the second being in the initialization section implies it will be updated somewhere inside the loop, where it is really constant throughout.

I would actually prefer it be pulled out above the loop and made final to make that immediately and abundantly clear to anyone reading the code. That's not ideal either because it increases the scope of the variable, but your enclosing function should not contain much more than that loop anyway.

4
  • 5
    Once you start including function calls it gets much harder for the compiler to optimise. The compiler would have to have special knowlege that Math.sqrt has no side effects. Dec 30, 2016 at 0:21
  • @PeterGreen If this is Java, the JVM can figure it out, but it might take a while. Dec 30, 2016 at 3:08
  • The question is tagged both C++ and Java. I don't know how advanced Java's JVM is and when it can and cannot figure it out, but I do know that C++ compilers in general cannot figure it out yet a function is pure unless either it has a non-standard annotation telling the compiler so, or the body of the function is visible and all indirectly called functions can be detected as pure by the same criteria. Note: side-effect-free is not enough to move it out of the loop condition. Functions that depend on global state cannot be moved out of the loop either if the loop body may modify the state.
    – hvd
    Dec 30, 2016 at 7:37
  • It gets interesting once Math.sqrt(x) is replaced by Mymodule.SomeNonPureMethodWithSideEffects(x).
    – Pieter B
    Dec 30, 2016 at 14:30
9

As @Karl Bielefeldt's said in his answer, this is usually a non-issue.

However, it was at one time a common issue in C and C++, and a trick came about to side-step the issue without reducing code readability— iterate backwards, down to 0.

final x = 10;//whatever constant value
for(int i = Math.floor(Math.sqrt(x)); i >= 0; i--) {
  //...do something
}

Now the conditional in every iteration is just >= 0 which every compiler will compile into 1 or 2 assembly instructions. Every CPU made in the last few decades should have basic checks like these; doing a quick check on my x64 machine I see this predictably turns into cmpl $0x0, -0x14(%rbp) (long-int-compare value 0 vs. register rbp offsetted -14) and jl 0x100000f59 (jump to the instruction following the loop if the previous comparison was true for “2nd-arg < 1st-arg”).

Note that I removed the + 1 from Math.floor(Math.sqrt(x)) + 1; in order for the math to work out, the starting value should be int i = «iterationCount» - 1. Also worth noting is that your iterator must be signed; unsigned int won't work and will likely compiler-warn.

After programming in C-based languages for ~20 years I now only write reverse-index-iterating loops unless there's a specific reason to forward-index-iterate. In addition to simpler checks in the conditionals, reverse-iteration often also side-steps what would otherwise be troublesome array-mutations-while-iterating.

8
  • 1
    Everything you write is technically correct. The comment about instructions may be misleading though, since all modern CPUs have also been designed to work well with forward iterating loops, regardless of whether they have a special instruction for them. In any case, most of the time is usually spent inside the loop, not performing iteration. Dec 30, 2016 at 15:09
  • 4
    It should be noted that modern compiler optimizations are designed with "normal" code in mind. In most cases, the compiler will generate code that is just as fast regardless of whether you use optimization "tricks" or not. But some tricks may actually hinder optimization depending on how complicated they are. If using certain tricks makes your code more readable or helps catch common bugs, that's great, but don't trick yourself into thinking "if I write code this way it will be faster." Write code how you normally would, then profile to find places where you need to optimize.
    – 0x5453
    Dec 30, 2016 at 15:30
  • Also note that unsigned counters will work here if you modify the check (the easiest way is to add the same value to both sides); for example, for any decrement Dec, the check (i + Dec) >= Dec should always have the same result as signed check i >= 0, with both signed and unsigned counters, as long as the language has well-defined wraparound rules for unsigned variables (specifically, -n + n == 0 has to be true for both signed and unsigned). Note, however, that this may be less efficient than a signed >=0 check, if the compiler doesn't have an optimisation for it. Dec 30, 2016 at 18:31
  • 1
    @JustinTime Yeah, the signed requirement is the toughest part; adding a Dec constant to both the starting value and ending value works but makes it much less intuitive, and if using i as an array index then you'd also need to do a unsigned int arrayI = i - Dec; in the loop body. I just use forward-iteration when stuck with an unsigned iterator; often with a i <= count - 1 conditional to keep the logic parallel to the reverse-iteration loops. Dec 30, 2016 at 20:24
  • 1
    @SlippD.Thompson I didn't mean adding Dec to the starting and ending values specifically, but shifting the condition check up by Dec on both sides. for (unsigned i = N - 1; i + 1 >= 1; i--) /*...*/ This allows you to use i normally within the loop, while guaranteeing that the lowest possible value on the left side of the condition is 0 (to prevent wraparound from interfering). It's definitely a lot simpler to use forward iteration when working with unsigned counters, though. Dec 30, 2016 at 21:18
3

It gets interesting once Math.sqrt(x) is replaced by Mymodule.SomeNonPureMethodWithSideEffects(x).

Basically my modus operandi is: if something is expected to always give the same value, then only evaluate it once. For example List.Count, if the list is supposed to not change during operation of the loop, then get the count outside the loop into another variable.

Some of these "counts" can be surprisingly expensive especially when you're dealing with databases. Even if you're working on a dataset that is not supposed to change during iteration of the list.

2
  • When count is expensive, you shouldn't be using it at all. Instead you should be doing the equivalent of for( auto it = begin(dataset); !at_end(it); ++it )
    – Ben Voigt
    Dec 30, 2016 at 16:10
  • @BenVoigt Using an iterator is definitely the best way for those operations.I merely mentioned it to illustrate my point about using non-pure methods with side-effects.
    – Pieter B
    Dec 30, 2016 at 16:57
0

In my opinion this is highly language specific. For example, if using C++11 I would suspect that if the condition check was a constexpr function the compiler would be very likely to optimise out the multiple executions as it knows it will yield the same value each time.

However if the function call is a library function which is not constexpr the compiler is almost certainly going to execute it on every iteration as it cannot deduce this (unless it is inline and can therefore be deduced as pure).

I know less about Java but given that is JIT compiled I would guess the compiler has enough information at runtime to likely inline and optimise out the condition. But this would rely on good compiler design and the compiler deciding this loop was an optimisation prioroty which we can only guess at.

Personally I feel it is slightly more elegant to put the condition inside the for loop if you can, but if it is complex I will write it into a constexpr or inline function, or your languages equivalant to hint that the function is pure and optimisable. This makes the intent obvious and maintains the idiomatic loop style without creating a huge unreadable line. It also gives the condition check a name if it is its own function so readers can immediately see logically what the check is for without reading it if complex.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.