65

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
    }
}
  • 9
    are you aware about how branch prediction works? – gnat Feb 2 '15 at 14:55
  • 12
    OP isn't asking how much time the branching will take. Clearly, the example is intended to ensure that it takes exactly the same time in both snippets. The question is about whether the individual CMP machine instruction will be slower if i is larger. – Kilian Foth Feb 2 '15 at 15:08
  • 18
    Since this is done in CSS, converting a string to an integer will likely dominate the comparison operation itself in terms of time spent executing. – user22815 Feb 2 '15 at 20:13
  • 58
    If you needed to use 1000000000 as a z-index in a CSS file, you have done something wrong. – Bergi Feb 2 '15 at 21:08
  • 6
    For CSS, the overhead of converting text into an integer will depend on the number of digits being converted (where a 6 digit number like 1000000 may be approximately 6 times as expensive as a 1 digit number like 1); and this overhead may be orders of magnitude larger than the overhead of integer comparisons. – Brendan Feb 3 '15 at 10:11
82

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.

  • 5
    What if the number gets too big for 32-bit arithmetic? Would it then not be split to slower computation? – Falco Feb 2 '15 at 17:44
  • 3
    @Falco Not on a CPU with a 64-bit ALU (which is pretty much all of them except in the embedded space these days.) – reirab Feb 2 '15 at 17:52
  • 8
    @Falco: Yes, but since the question asks about ALU performance, the implication is that the values fit within the CPU's word size or the abilities of any SIMD instructions it might have. Operating on larger numbers than that would have to be implemented with multiple instructions outside the CPU. That was very common 30 years ago when you just had 8- or 16-bit registers to work with. – Blrfl Feb 2 '15 at 17:58
  • 6
    @Falco How would that require debugging? It's not a bug; it's just a bit slower to do 64-bit ops on a CPU that doesn't natively support 64-bit ops. Suggesting that one should never use a number above 2^31-1 seems a bit ridiculous. – reirab Feb 2 '15 at 21:19
  • 2
    @Falco Having said that, do the rendering engines in browsers even use integers to represent z-indices? Most rendering engines I'm familiar with use single-precision floats for everything (until the final rasterization stage,) but I haven't really studied browser rendering engines. – reirab Feb 3 '15 at 14:57
25

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.

  • It should be mentioned, that the proposed Numbers in the Question are of different numeric type in a typical 32-bit integer type... – Falco Feb 3 '15 at 16:43
19

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.

  • On MIPS you can only have 16-bit immediates, so definitely comparison with 1 will be shorter and (probably) faster than 1000000. Maybe the same to Sparc and PowerPC. And I think I have read from some sources that Intel also optimizes operations on small immediates in several cases but I'm not sure for comparison or not – phuclv Feb 3 '15 at 5:28
  • @LưuVĩnhPhúc: A register can be loaded before the loop. At that point, the actual comparison will be the same number of instructions in either case. – cHao Feb 3 '15 at 15:26
  • As the Loop was just an example by the op and the question was for example an z-index, if you have 1000 objects, each with its own z-index and you set them to 100000000...1000000999 or to 10000...10999 and you loop over them for sorting before rendering, there are many compares and many load instructions. There it could make a difference! – Falco Feb 3 '15 at 16:49
  • @Falco: In that case, immediates wouldn't even factor in; loading and comparing against a register seems pretty much inevitable. – cHao Feb 4 '15 at 9:10
  • @cHao: If one is comparing Z indices against each other, they'd be in registers. If one is handling certain ranges of indices differently that might entail immediate comparisons. Normally constants would get loaded before a loop starts, but if e.g. one had a loop that needed to read pairs of values from memory and compare the first value of each pair with with five different (non-uniformly-spaced) constants in the range 100000 to 100499, and the other value with five other such constants, it may be much faster to subtract 100250 (kept in a register) and then compare with values -250 to 250... – supercat Feb 4 '15 at 16:48
5

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.
4

@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

  • Branch prediction affects the branching time, but not the comparison time itself. – reirab Feb 2 '15 at 17:48
3

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.

0

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.

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