which loop is faster?

[g.eckert]

Hi, i had this idea that one loop might be faster than another, in terms of binary operations or w/e, but im not sure so i will ask. Suppose you have high performance code and you want the best loop. The loops are doing the same thing but my thought was that there underlying structures that operate the loops, one must be more efficient. I dont have the tools to test the speed and memory/bit usage of these, i was looking for more of a theoretical explanation of which would be faster. Two Examples.

//While loop

int i=0;
while(i<1000000)
{
      i++;
}


//For loop

for(int i=0;i<1000000;i++){/**/}



//I did not compile this

[laserlight]

They only differ in the scope of i.

[Paul McKenzie]

Hi, i had this idea that one loop might be faster than another, in terms of binary operations or w/e, but im not sure so i will ask. Suppose you have high performance code and you want the best loop. The loops are doing the same thing but my thought was that there underlying structures that operate the loops, one must be more efficient.

Why do you say "must"? It all depends on what the compiler does with that code. The compiler could optimize one over the other or make the resulting code exactly the same.

It is pointless to ask "which loop is faster", "is using "else" faster than "switch", and questions like that when you're given a high-level language such as C++. What makes more sense to ask is "is this algorithm faster?" "is this sort faster than this sort?" "is this search technique faster than that search technique", etc.

Regards,

Paul McKenzie

[g.eckert]

I understand the question is somewhat pointless, i guess what i was asking is, when the compiler translates the C++ loops down into the machine language, is the resulting machine language the same for each loop or do they differ? Which you answered this.

I was also wondering where i could learn more about that. My programming classes rarely go into these topics, what is actually happening underneath the code. What would you suggest (reading) or classes that explain memory storage and ALU operations and things like that. My community college is very limited in CPS courses.

[JohnW@Wessex]

Once upon a time, when I was coding for 68000 microprocessors, I found that counting down to zero was slightly faster than counting up as the loop contained less instructions / clock cycles due to the decrement instruction also setting the flag bits.

Nowadays I would just try the different code and time it. That's assuming I'd identified that bit of the code was a speed bottleneck.

With modern compilers all you can assume is that they will produce a list of instructions that will produce the same effect as your source code. Otherwise they are free to re-interpret / re-order your code as they see fit. Also the micro-processor may do its own instruction re-ordering.

[treuss]

One more thing. Before you jump into testing which of the loops is faster, be aware that the compiler might actually optimize away the whole loop, as looping over doing doing nothing is the same as doing nothing. At least with small fixed numbers of loop iterations, "unrolling" those loops is a quite common optimization.

[Speedo]

I understand the question is somewhat pointless, i guess what i was asking is, when the compiler translates the C++ loops down into the machine language, is the resulting machine language the same for each loop or do they differ? Which you answered this.

You should be able to set your compiler to generate a file with the assembler output it produces when it compiles a file. Obviously it requires some knowledge of asm to understand what's going on, but if your compiler can include the original C++ source code as comments in the asm, it's not terribly hard to figure out.

In this case, MSVC9 compiling with /O2 generates identical asm for both loops, something like

xor esi esi
$LL2@main:

; code that deals with "i", to avoid having it optimized out

inc esi
cmp esi, 1000000
jl SHORT $LL2@main

[g.eckert]

Wow that is an interesting feature( writing the assembly to file) ill have to check that out. thanks. I am kind of used to Java where i can actually see the .class file which is some sort of assembly language, right? But for C++ all i get is my .cpp file and the .exe.

[Paul McKenzie]

Wow that is an interesting feature( writing the assembly to file) ill have to check that out. thanks. I am kind of used to Java where i can actually see the .class file which is some sort of assembly language, right?

That's the difference between a compiled language and Java, and the basic reason why I stated that it is kind of pointless to really think one loop is faster than the other.

In Java, you have the class files that when created, produce only one way to do a for() loop, while() loop, etc.. That's why Java class files can be "decompiled" back into Java source code, regardless of what platform the Java class file was created on. Each Java language construct has a "template" of how it must look in the class file, so that the JVM, regardless of platform, can interpret the class file.

This is not the case for a true compiled language. There is no determination as to what two pieces of similar code will boil down to at the object code level, since every compiler vendor has their way of optimizing (or not optimizing) the code. As long as the code works as expected, that's all that counts.

When there were compiler wars going on a decade ago, you would constantly see computer ads saying "our compiler produces faster code than their compiler" with benchmarks to prove the advertiser's claim. It's the optimization that occurs within each compiler, given the same source code, that determines which piece of code will be faster.

The basic thing is that attempting to micromanage small, inconsequential things such as a speed of a for() over a while() loop, speed of an if/else over a switch(), or some other minor difference in two sets of syntax, is IMO (unless it's for academic or some really specific reason) a waste of time when it comes to C++. What counts are the big things -- a certain algorithm over another, inordinate usage of the free store (which can slow down an application), passing large objects by value where the object has an expensive copy operation, etc.

But for C++ all i get is my .cpp file and the .exe.

You also have the object files, which the compiler produces. The linker takes the object files and creates the final executable from them.

Regards,

Paul McKenzie

[treuss]

But for C++ all i get is my .cpp file and the .exe.

I believe most compilers allow you to create the intermediate files. Turning a .cpp int a .exe involves several steps:
- Preprocessor
- Compiler
- Assembler
- Linker
Have a read through your compiler documentation (for gcc, check the -E, -c and -S option) to see how you can have a look at intermediate files.

[_uj]

In Java, you have the class files that when created, produce only one way to do a for() loop, while() loop, etc.. That's why Java class files can be "decompiled" back into Java source code, regardless of what platform the Java class file was created on. Each Java language construct has a "template" of how it must look in the class file, so that the JVM, regardless of platform, can interpret the class file.

This is complete nonsense.

There are no "templates" a Java compiler must use when it lays down bytecode (the assembly language of the JVM). A Java compiler is free to use the available bytecode instructions anyway it likes to implement Java language constructs. It must follow the class file layout but that's another story.

And although JVM's are interpreters most JVM's today use compilation to native code in the interpretation process at runtime. So in effect Java is a compiled language to native machine language. The runtime compilation isn't required to lay down code according to some "templates" either.

So in no step of the Java compilation process (statically and dynamically) are there any "templates" that must be used.

[Paul McKenzie]

A Java compiler is free to use the available bytecode instructions anyway it likes to implement Java language constructs. It must follow the class file layout but that's another story.

I am strictly speaking at the class level. Of course the code has to eventually run on the CPU that's operating.

The difference is that the optimizations done in Java and C++ are in two different areas -- that was my point. The optimizations in C++ are done on the object code level. The equivalent or close to equivalent to object code in Java is the class file.

Regards,

Paul McKenzie

[_uj]

I am strictly speaking at the class level. Of course the code has to eventually run on the CPU that's operating.

The difference is that the optimizations done in Java and C++ are in two different areas -- that was my point. The optimizations in C++ are done on the object code level. The equivalent or close to equivalent to object code in Java is the class file.

Well you claimed this (about a "true" compiled language),

"There is no determination as to what two pieces of similar code will boil down to at the object code level, since every compiler vendor has their way of optimizing (or not optimizing) the code. As long as the code works as expected, that's all that counts."

The above is true also for Java compiled to bytecode. Java doesn't specify that the bytecode for say a for-loop or a while-loop must look a certain way. Different compiler vendors can do what they like including optimizations (as long as the result behaves according to the language specification).

What you said about Java just isn't true. There are no "templates" specified for how a compiler must lay down bytecode.

[Paul McKenzie]

The above is true also for Java compiled to bytecode. Java doesn't specify that the bytecode for say a for-loop or a while-loop must look a certain way. Different compiler vendors can do what they like including optimizations

By "compiler", are you refering to javac? Isn't there only one vendor (Sun)? If there is more than one vendor, I stand corrected

(his isn't the Java forum, so I don't want to keep this up.)

Regards,

Paul McKenzie

[_uj]

By "compiler", are you refering to javac? Isn't there only one vendor (Sun)? If there is more than one vendor, I stand corrected

(his isn't the Java forum, so I don't want to keep this up.)

There are more than one Java compiler vendor. IBM is one example. And Eclipse has it's own built-in Java compiler. But you would be wrong even if there were just one supplier of Java compilers. This is because also a Java compiler from the same vendor can differ between versions.

Well, this isn't a Java forum but that doesn't mean you can spread bullshit about Java without being corrected.