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
}
  • 47
    Why not just move it to the line before the loop, then you can give it a sensible name too. – jonrsharpe Dec 29 '16 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)). :-) – R.. Dec 30 '16 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. – Kevin Krumwiede Dec 30 '16 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 '16 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 '16 at 15:50
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.

  • 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 '16 at 18:13
  • 1
    I would and I have. But not for speed. For readability. Readable code tends to be fast on its own. – candied_orange Dec 29 '16 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 '16 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 '16 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.

  • 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. – Peter Green Dec 30 '16 at 0:21
  • @PeterGreen If this is Java, the JVM can figure it out, but it might take a while. – chrylis Dec 30 '16 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 '16 at 7:37
  • It gets interesting once Math.sqrt(x) is replaced by Mymodule.SomeNonPureMethodWithSideEffects(x). – Pieter B Dec 30 '16 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.

  • 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. – Jørgen Fogh Dec 30 '16 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 '16 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. – Justin Time Dec 30 '16 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. – Slipp D. Thompson Dec 30 '16 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. – Justin Time Dec 30 '16 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.

  • 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 '16 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 '16 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, privacy policy and cookie policy

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