Is a 1 < 10 comparison less expensive than 1 < 1000000?

Question

I just used ~1 billion as the count for a z-index in CSS, and was thinking about the comparisons that must go on. Is there a difference in performance on the ALU level in comparisons between very large numbers vs very small ones?

For example, would one of these two snippets be more expensive than the other?

snippet 1

for (int i = 0; i < 10000000; i++){
    if (i < 10000000000000) {
        //do nothing
    }
}

snippet 2

for (int i = 0; i < 10000000; i++){
    if (i < 1000) {
        //do nothing
    }
}

Answer 1

Every processor I've worked on does comparison by subtracting one of the operands from the other, discarding the result and leaving the processor's flags (zero, negative, etc.) alone. Because subtraction is done as a single operation, the contents of the operands don't matter.

The best way to answer the question for sure is to compile your code into assembly and consult the target processor's documentation for the instructions generated. For current Intel CPUs, that would be the Intel 64 and IA-32 Architectures Software Developer’s Manual.

The description of the CMP ("compare") instruction is in volume 2A, page 3-126, or page 618 of the PDF, and describes its operation as:

temp ← SRC1 − SignExtend(SRC2);
ModifyStatusFlags; (* Modify status flags in the same manner as the SUB instruction*)

This means the second operand is sign-extended if necessary, subtracted from the first operand and the result placed in a temporary area in the processor. Then the status flags are set the same way as they would be for the SUB ("subtract") instruction (page 1492 of the PDF).

There's no mention in the CMP or SUB documentation that the values of the operands have any bearing on latency, so any value you use is safe.

Answer 2

Is there a difference in performance on the ALU level in comparisons between very large numbers vs very small ones?

It's very unlikely, unless going from a small number to a large number changes your numeric type, say from an int to a long. Even then, the difference might not be significant. You're more likely to see a difference if your programming language silently switches to arbitrary precision arithmetic under the covers.

Nonetheless, your particular compiler might be performing some clever optimizations that you are not aware of. The way you find out is to measure. Run a profiler on your code; see which comparisons take the longest. Or simply start and stop a timer.

Answer 3

Many processors have "small" instructions which can perform arithmetic operations, including comparisons, on certain immediately-specified operands. Operands other than those special values must either use a larger instruction format or, in some cases, must use a "load value from memory" instruction. In the ARM Cortex-M3 instruction set, for example, there are at least five ways a value might be compared to a constant:

    cmp r0,#1      ; One-word instruction, limited to values 0-255

    cmp r0,#1000   ; Two-word instruction, limited to values 0-255 times a power of 2

    cmn r0,#1000   ; Equivalent to comparing value with -1000
                   ; Two-word instruction, limited to values 0-255 times a power of 2

    mov r1,#30000  ; Two words; can handle any value 0-65535
    cmp r0,r1      ; Could use cmn to compare to values -1 to -65535

    ldr r1,[constant1000000] ; One or two words, based upon how nearby the constant is
    cmp r0,r1
    ...

constant1000000:
    dd  1000000

The first form is the smallest; the second and third form may or may not execute as quickly, depending upon the speed of the memory from which code is fetched. The fourth form form will almost certainly be slower than the first three, and the fifth form even slower, but the latter can be used with any 32-bit value.

On older x86 processors, short-form compare instructions would execute faster than long-form ones, but many newer processors will convert both the long and short forms to the same representation when they are first fetched, and store that uniform representation in the cache. Thus, while embedded controllers (like those found on many mobile platforms) will have a speed difference, many x86-based computers won't.

Note also that in many cases where a constant is used heavily within a loop, a compiler will only need to load the constant into a register once--before the loop starts--rendering timing distinctions moot. On the other hand, there are some situations, even in small loops, where that won't always happen; if a loop is small but heavily-executed, there occasionally may be a major performance between comparisons involving short immediate values and those involving longer ones.

Answer 4

The short answer to this question is, no, there's no time difference to compare two numbers based on the magnitude of those numbers assuming they're stored in the same data type (e.g. both 32-bit ints or both 64-bit longs.)

Furthermore, up to the word size of the ALU, it's incredibly unlikely that comparing two integers to each other will ever take more than 1 clock cycle, as this is a trivial operation equivalent to a subtraction. I think every architecture I've ever dealt with had single-cycle integer comparison.

The only cases I can think of that I've encountered where a comparison of two numbers was not a single-cycle operation are the following:

• Instructions where there's actually a memory latency in fetching operands, but that has nothing to do with how the comparison itself works (and generally isn't possible on RISC architectures, though it is usually possible on CISC designs, like x86/x64.)
• Floating-point comparisons may be multi-cycle, depending on architecture.
• The numbers in question don't fit in the word size of the ALU and, thus, the comparison must be broken up into multiple instructions.

Answer 5

@RobertHarvey's answer is good; consider this answer a supplement to his.

---

You should also consider Branch Prediction:

In computer architecture, a branch predictor is a digital circuit that tries to guess which way a branch (e.g. an if-then-else structure) will go before this is known for sure. The purpose of the branch predictor is to improve the flow in the instruction pipeline. Branch predictors play a critical role in achieving high effective performance in many modern pipelined microprocessor architectures such as x86.

Basically, in your example, if the if statement inside the loop always returns the same answer, then the system can optimize it by guessing correctly which way it will branch. In your example, because the if statement in the first case always returns the same result, it will run slightly faster than the second case.

Excellent Stack Overflow question on the subject

Answer 6

It depends on the implementation, but it would be very, very unlikely.

I admit that I have not read through the implementation details of the various browser engines, and CSS does not specify any particular type of storage for numbers. But I believe that it is safe to assume that all of the major browsers are using 64-bit double-precision floating-point numbers ("doubles", to borrow a term from C/C++) to handle most of their numeric needs in CSS, because this is what JavaScript uses for numbers, and so using the same type makes integration easier.

From the computer's standpoint, all doubles carry the same amount of data: 64 bits, whether the value is 1 or -3.14 or 1000000 or 1e100. The amount of time it takes to do an operation on these numbers doesn't depend on the actual value of those numbers, because it's always working on the same amount of data. There's a tradeoff in doing things this way, in that doubles can't accurately represent all numbers (or even all numbers within their range), but they can get close enough for most matters, and the kinds of things CSS does aren't numerically-demanding enough to need more precision than that. Combine this with the benefits of straight-across compatibility with JavaScript, and you've got a pretty strong case for doubles.

It's not impossible that someone might implement CSS using a variable-length encoding for numbers. If someone used a variable-length encoding, then comparing against small numbers would be less expensive than comparing against large numbers, because large numbers have more data to crunch. These kinds of encodings can be more precise than binary, but they are also much slower, and for CSS in particular, the precision gains are probably not enough to be worth the performance hit. I would be very surprised to learn that any browser did things this way.

Now, in theory, there is one possible exception to everything I've said above: comparing against zero is often faster than comparing against other numbers. This isn't because zero is short (if that were the reason, then 1 should be just as fast, but it's not). It's because zero lets you cheat. It's the only number where all the bits are off, so if you know that one of the values is zero, you don't even have to look at the other value as a number: if any of the bits on then it's not equal to zero, and then you only have to look at one bit to see if it's greater than or less than zero.

Answer 7

If this code was being interpreted each time it ran, there'd be a difference as it takes longer to tokenise and interpret 10000000000000 compared to 1000. However, this is the obvious first optimisation of interpreters in this case: tokenise once and interpret the tokens.