A look at reverse loops

Let’s throw it in reverse and getting a bit loopy.

EDIT: This article is meant to explore underlying mechanisms and concepts. I’ve made some changes since the first version of this because I didn’t get my point across very well in the original edit. Hopefully it’s better now. I’d like to thank reddit for their feedback, their comments were… a learning experience. I especially want to thank ar down in the comments. He wrote a great article demonstrating why you should always benchmark. Remember, always code for readability first, trust your compiler, and if you attempt any of the following make sure you benchmark.

Reverse loops have been around a long time but have mostly been forgotten or ignored because these days nobody’s going to miss those extra few clock cycles and compilers have gotten pretty smart. But let’s see what happens when we reverse a for loop and see if we can determine when and if it ever matters. First we’re going to need some code in here to see what we’re dealing with. We’ll be looking at Java and bytecode but everything here should apply to your favorite language.

public class HelloWorld {
    public static void main(String[] args) {
        // Normal for loop we’re all familiar with
        for (int i = 0; i <= 10; i++) {
            System.out.println(i);
        }
        // Reverse for loop
        for (int i = 10; i >= 0; i--) {
            System.out.println(i);
        }
    }
}

Great. Amazing. A loop that counts from 0 to 10 and a loop that counts from 10 to 0. Seems the same. Going backwards seems silly. Why do that? The short answer is don’t bother if it makes it less readable or is going to add more code inside the loop. But if you’re just looping through everything and don’t care about order then you can get a little performance advantage sometimes.

Just like the syntactical sugar of modern languages the For Loop is also just short hand for a While Loop. Take the following two loops for example. They both get compiled down to the same bytecode.

for (int i = 0; i < 10; i++) {
    System.out.println(i);
}
int i = 0;
while (i < 10) {
    System.out.println(i);
    i++;
}

They both get compiled down to this.

0: iconst_0
1: istore_0
2: iload_0
3: bipush 10
5: if_icmpge 21
8: getstatic #2 // Field java/lang/System.out:Ljava/io/PrintStream;
11: iload_0
12: invokevirtual #3 // Method java/io/PrintStream.println:(I)V
15: iinc 0, 1
18: goto 2

A couple things to notice here. Starting at line 2 we load in the variable onto the stack then on line 3 we put the number 10 to the stack and finally line 5 is comparing if the variable is greater than or equal to 10. At the end we loop back up with a goto 2. What!? A goto!? Heck yeah a GoTo! Goto’s are fine at this level. They’ve been given a bad wrap but they’re not the demons we’ve been taught to avoid. They just can’t be trusted in the hands of high level language developers. While loops in ever language eventually get turned into a goto or some other similar branching instruction.

Okay great it loops. But lines 3 and 5 are slowing us down here. Every time we loop we have to put the number 10 back onto the stack again then we have to compare the two numbers. It’s even worse if you replace the 10 with a more complex action. Then you’re doing that action all over again at the top of every loop. Every. Single. Loop. Putting a number on the stack isn’t so bad but if you’re looping through a few hundred thousand elements then that’s a few hundred thousand times it has to put that number on the stack or whatever functionality you put there. Sure a few hundred thousand extra instructions probably isn’t the worst thing in the world, but if you put a function there that takes an extra millisecond then you’ve just added minutes to your code. And hey if you’re bothering to use a reverse For Loop then you care about those cycles.

So how is a reverse for any better? It’s a little clearer if we look at it in while loop form. Then we’ll jump into some bytecode in a bit again.

int i = 10;
while (i >= 0) {
    System.out.println(i);
    i--;
}

We’ve now moved the 10 out of the loop. We can even make it a function and it won’t matter. But you’re probably looking at that 0 and say to yourself, “yeah but you still have to push the 0 onto the stack every time and do a compare”. Well not exactly. 0 is a nice number to work with. It’s much easier to check that a number is not 0 especially at the binary level than it is to check if 4 is bigger than or the same as 10. That’s like real math stuff there. Okay let’s see how that works out in the bytecode.

21: bipush 10
23: istore_0
24: iload_0
25: ifle 41
28: getstatic #2 // Field java/lang/System.out:Ljava/io/PrintStream;
31: iload_0
32: invokevirtual #3 // Method java/io/PrintStream.println:(I)V
35: iinc 0, --1
38: goto 24

Woooo! Only 9 instructions instead of 10! 10% improvement! /s

That’s neat there’s less bytecode, but how did we save an instruction just by reversing the loop? Start at the beginning there. Out the gate we throw 10 onto the stack. Or potentially some function call. Then at the end we see the loop starts on line 24. So if an instruction is getting taken out of the loop, then what are we putting in the loop to compare to 0? Nothing. On line 25 we just check if the counter is less than or equal to 0. Zeros are easy. Bigger numbers gotta be remembered and you gotta do math to compare them. It’s just awful. We’ve not just removed an instruction. We’ve removed an instruction from inside the loop and replaced it with another one that’s more efficient. An interesting note here is that we’ve moved work outside the loop. And this works the same way in just about every language. But you’ll probably never notice a difference unless you’re doing 100’s of thousands or millions of loops. Usually nested loops are a good place to look where it might be needed. Also if you have to do extra code in your loop to adjust for it being backwards you’ll end up putting slowdowns back in sometimes.

Let’s keep looking at moving things outside the loop. Just to drive the point home a bit, how often have you seen this? Looping through an array and doing something for each element using the length of the array.

String[] someWords = {“Hello”, “World”};
for (int i = 0; i < someWords.length; i++) {
    System.out.println(someWords[i]);
}
15: iconst_0
16: istore_2
17: iload_2
18: aload_1
19: arraylength
20: if_icmpge 38
23: getstatic #5 // Field java/lang/System.out:Ljava/io/PrintStream;
26: aload_1
27: iload_2
28: aaload
29: invokevirtual #6 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
32: iinc 2, 1
35: goto 17

After looping back to line 17, the array object has to get loaded back onto the stack at line 18, and the length has to be retrieved again on line 19. And it does this for every loop. Over and over and over… When doing something like this you can save the computer some work by dumping the results into a variable first. If we take anything away from this whole post, it’s to at least move complex actions out of the loop condition.

String[] someWords = {“Hello”, “World”};
int arrLen = someWords.length;
for (int i = 0; i < arrLen ; i++) {
    System.out.println(someWords[i]);
}
15: aload_1
16: arraylength
17: istore_2
18: iconst_0
19: istore_3
20: iload_3
21: iload_2
22: if_icmpge 40
// do stuff code removed for compactness.
34: iinc 3, 1
37: goto 20

Here we’ve added 2 lines overall, but we’ve moved two expensive instructions and replaced them with 1 cheaper one. Demonstrating less code is not always better code. Now we’re just reloading an int value onto the stack instead of loading an array object onto the stack and then getting its length property.

Here we can benefit somewhat by using a reverse for loop. It does the same value caching but without adding more code.

for (int i = someWords.length - 1; i >= 0; i--) {
    System.out.println(someWords[i]);
}
15: aload_1
16: arraylength
17: iconst_1
18: isub
19: istore_2
20: iload_2
21: iflt 39
// do stuff code removed for compactness. 
33: iinc 2, -1
36: goto 20

Again the biggest take away from all of this is always avoid complex actions in the condition or inside the loop in general.

Now let’s have a little fun. We’ve shown for loops are just pretty do/while loops, but we can also play around with do/while loops a little too. Check this little bit of code.

int i = 11;
while (i --> 0) {
   System.out.println(i);
}

A few things should stick out here. What’s the arrow? Where’s the decrement? No seriously what’s that arrow!? Don’t look it up it doesn’t exist. This works in a surprising amount of C type languages. It’s actually normal code with the spacing moved around. Here look again.

int i = 11;
while (i-- > 0) {
   System.out.println(i);
}

The bytecode comes out the same except the decrement is at the top of the loop instead of the bottom. Visually it’s actually kinda nice if you know to look for it. It’s looks like it’s showing the variable is going down to 0. Other developers that don’t know what it is are going to be confused by it though. So avoid it for the sake of readability and maintainability. But it also shows we can put the decrement in the while loop condition to save a line of code and not get penalized in the bytecode later.

Happy looping!