Take the 2-minute tour ×
Electrical Engineering Stack Exchange is a question and answer site for electronics and electrical engineering professionals, students, and enthusiasts. It's 100% free, no registration required.

This question on StackOverflow goes like this which is faster - while(1) or while(2)? Asking which of two infinite loops is faster only makes sense if you ask it in sense "which can make more iterations per second".

The serious answers so far are "no difference".

Now suppose a compiler is dumb enough and generates a comparison instruction and so the code compares 1 versus zero in the first loop and 2 versus zero in the second loop.

Something like this for the first loop:

start:
    mov reg1, 1
    cmp reg1, 0
    je start

and something like this for the second loop:

start:
    mov reg1, 2
    cmp reg1, 0
    je start

This runs equally fast on some powerful chip like Intel Core i5 because the whole comparison is performed in hardware and effectively just compares any two 32-bit (or 64-bit) integer numbers in one operation and so any such comparison takes the same time.

What about some very low power very simple chips? I guess the comparison circuits on them could be designed simplified to be smaller at expense of speed.

Would comparing 2 against zero take same time as comparing 1 against zero on any reasonable chip?

share|improve this question
    
The OISC (One instruction set computer) architecture comes to mind, but that's more of a thought experiment then an actual device. –  Connor Wolf Jul 21 at 8:53
1  
I was about to jokingly comment it would be slower on a 1-bit computer but apparently they exist: en.wikipedia.org/wiki/1-bit_architecture - although for typical practical chips like the PIC10 and ATtiny etc it wouldn't make a diffence. –  PeterJ Jul 21 at 8:55
    
Surely someone could come up with a CPU architecture and a 'dumb enough' compiler such that while(2) takes longer than while(1) or vice-versa. Does it occur in practice? No. So? –  apalopohapa Jul 21 at 12:26
    
@apalopohapa: Do you know for sure that there exists no such chip design? Me not. –  sharptooth Jul 21 at 12:28
    
@sharptooth With a 'dumb enough' compiler it doesn't even matter. while(2) could be implemented in such a way that it takes an arbitrary number of cycles. The CPU doesn't even matter any more. If the dumb compiler casted 2 to 32 bits in an 8-bit CPU then you could get that effect. Because of the 'dumb enough' prerrogative, I find the question rather pointless (don't take offense though, I'm just trying to make a point). –  apalopohapa Jul 21 at 12:36

3 Answers 3

First you have to ask yourself what while(1) or while(2) actually means.

Now suppose a compiler is dumb enough and generates a comparison instruction and so the code compares 1 versus zero in the first loop and 2 versus zero in the second loop.

So your hypothetical compiler is then basically expanding those out to be while(1 != 0) and while(2 != 0), the results of which would be either a 1 (true), or a 0 (false). Is this dumb compiler then going to be comparing those with 0 as well, and if so, what is it going to do with the results of that comparison? I see an infinite recursion problem going on there.

Leaving that to one side, though, and we assume it only does the one comparison and takes the result of that comparison as a logical yes/no value, how would you expect the compiler to implement that as assembly language? Well, obviously that depends on the architecture. If you have a comparison operator then obviously it should use that. Something like, in pseudo-assembly:

_while:
    ld r0, 1
    ld r1, 0
    cmp r0, r1
    beq _while_finished // jump if the compare was equal
    // ... loop code in here
    bra _while
_while_finished:
    // ... continue with the code.

Replacing the 1 with a 2 there would leave it the exact same number of instructions.

Few small microcontrollers have a cmp or similar, so the most common way is to subtract one value from another and test to see if the result is zero. For instance:

_while:
    ld r0, 1
    ld r1, 0
    sub r0, r0, r1 // Subtract r1 from r0 and leave the result in r0
    beqz _while_finished // Branch if zero flag set by last math operation
    // ... loop code in here
    bra _while
_while_finished:
    // ... continue with the code.

Again, substituting the 1 with a 2 would leave the same number of instructions. So you have to ask yourself now, with that code, which part could potentially take longer with a 2 than with a 1? Only the sub instruction has the potential to do that, and then only if the chip design is incredibly poor. Typically a sub or add instruction is performed as one single operation by the ALU, and the values involved have no bearing on the time taken. Only if the ALU performs a sub a, b, c by first loading a with b and then decrementing it c times, would it have any possibility of the numbers involved having any bearing on the time taken - and I have never come across such a primitive way of doing it. Unless of course the chip were designed by the same person that designed the compiler ;)

So the answer is:

In any normal system no, the operands to the comparison would have no bearing on the time taken to do the comparison.

share|improve this answer
    
I know that typically an integer subtraction or comparison takes constant time. This is outlined in the question. The question is whether there're other designs. –  sharptooth Jul 21 at 10:55
    
While it would be possible to design a slower, inferior, system no one in their right mind would, since no one would use it. –  Majenko Jul 21 at 11:01
1  
Suppose you need to design a very small chip for something like a calculator which must be very energy efficient and you don't really care of how much time those operations take under the condition that any computation requested by the user completes in say 50 milliseconds - why would this be inferior? –  sharptooth Jul 21 at 11:48
    
Because time = energy. Each switching of a gate consumes energy. The more clock cycles, the more energy used. You won't save any gates by having a decrementer, counter, and comparer instead of a single subtractor, it's needless complication with no added benefit. Power is saved by reducing the clock speed, not increasing the number of clocks needed. –  Majenko Jul 21 at 11:53
    
What if the circuit that needs variable number of clocks contains much less gates compared to one that can subtract anything from anything in the same number of clocks? –  sharptooth Jul 21 at 12:04

In most modern computers, the compiler (and in reality it's the linker that generates the machine code - although with LLVM I'm not sure) will end up testing the conditional to see if it is zero. Other answers assume there is a subtraction or a comparison with two registers, most optimizing compilers won't do that.

Load count value

Load "count value" -> Register
Brz  pointer to next block of code    ; Branch if zero
Bra  pointer back to top of loop      ; else

This code is identical for each of your options, therefore the loops are identical.

But if you look at the code, most compilers know that "2" and "1" are not variables and won't even assign memory for it. They will just produce

Bra  pointer back to top of loop      ; branch always

for both scenarios.

share|improve this answer
1  
I'm not asking about "most compilers" - the compiler is assumed to be "dumb enough", otherwise the question would make no sense. –  sharptooth Jul 21 at 9:36
    
@sharptooth a compiler has to have at least some level of smarts or you'd just code directly in asssembly. These are not hard decisions to make, so the overall determining factor is where or not there is support in the op-codes for the these types of branches, branch if zero, branch if not zero and branch always. Even 4 bit micros have some of these branch instructions (and not much else) partially Branch always. Even compliers of 20 years ago would map your while to a branch always. –  placeholder Jul 21 at 14:39
1  
No, smarts are not the only reason to have a compiler. Code in C (or similar language) is much more maintainable and portable and so you have good chances of having a ready solution in C - then it makes a big difference between "it compiles but runs rather slow" and "I can't compile it and have to write it in assembly". –  sharptooth Jul 21 at 14:45
    
@placeholder, doesn't a typical CMP instruction work by having the ALU do a subtraction, but without storing the result? –  The Photon Jul 21 at 16:14
    
@ThePhoton why would you assume that? That is possible but most op-codes I've read tell you when certain flags are set and upon what operation, so a BNZ (Branch Non Zero) just reads the zero flag, and the zero flag can be set by a comparison or even just a read/fetch from the previous operand. –  placeholder Jul 21 at 16:22

If you can find a compiler that is stupid enough not to optimize this case it would do the run-time comparison while( 2 != 0 ) or while( 1 != 0 ). In C, this is by definition a comparison between two int values, which have a minimum size of 16 bits. Hence at run time (at least) 16 bits must be compared, using the appropriate instructions on the target machine. It does not matter whether the value in one of the int values is 1 or 2.

The question sort-of assumes that a compiler might somehow optimize for the fact that 1 can be represented in 1 bit, while 2 requires 2 bits, yet at the same time NOT do the constant folding that removes the comparison altogether. IMO this is so bizarre that such a compiler might as well generate extra code for the while(1) case top make this case larger than the while(2) case.

share|improve this answer
    
Nope. Having any of the bits non-zero is enough to satisfy the condition, so an architecture which evaluates bits serially is free to quit evaluating once it finds a non-zero value. The C standard governs behavior not implementation and so an implementation which always provides the required behavior is sufficient. –  Chris Stratton Jul 21 at 15:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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