c++ - Is < faster than <=?

ID : 610

viewed : 201

Tags : c++cperformanceassemblyrelational-operatorsc++c





Top 5 Answer for c++ - Is < faster than <=?

vote vote

93

No, it will not be faster on most architectures. You didn't specify, but on x86, all of the integral comparisons will be typically implemented in two machine instructions:

  • A test or cmp instruction, which sets EFLAGS
  • And a Jcc (jump) instruction, depending on the comparison type (and code layout):
  • jne - Jump if not equal --> ZF = 0
  • jz - Jump if zero (equal) --> ZF = 1
  • jg - Jump if greater --> ZF = 0 and SF = OF
  • (etc...)

Example (Edited for brevity) Compiled with $ gcc -m32 -S -masm=intel test.c

    if (a < b) {         // Do something 1     } 

Compiles to:

    mov     eax, DWORD PTR [esp+24]      ; a     cmp     eax, DWORD PTR [esp+28]      ; b     jge     .L2                          ; jump if a is >= b     ; Do something 1 .L2: 

And

    if (a <= b) {         // Do something 2     } 

Compiles to:

    mov     eax, DWORD PTR [esp+24]      ; a     cmp     eax, DWORD PTR [esp+28]      ; b     jg      .L5                          ; jump if a is > b     ; Do something 2 .L5: 

So the only difference between the two is a jg versus a jge instruction. The two will take the same amount of time.


I'd like to address the comment that nothing indicates that the different jump instructions take the same amount of time. This one is a little tricky to answer, but here's what I can give: In the Intel Instruction Set Reference, they are all grouped together under one common instruction, Jcc (Jump if condition is met). The same grouping is made together under the Optimization Reference Manual, in Appendix C. Latency and Throughput.

Latency — The number of clock cycles that are required for the execution core to complete the execution of all of the μops that form an instruction.

Throughput — The number of clock cycles required to wait before the issue ports are free to accept the same instruction again. For many instructions, the throughput of an instruction can be significantly less than its latency

The values for Jcc are:

      Latency   Throughput Jcc     N/A        0.5 

with the following footnote on Jcc:

  1. Selection of conditional jump instructions should be based on the recommendation of section Section 3.4.1, “Branch Prediction Optimization,” to improve the predictability of branches. When branches are predicted successfully, the latency of jcc is effectively zero.

So, nothing in the Intel docs ever treats one Jcc instruction any differently from the others.

If one thinks about the actual circuitry used to implement the instructions, one can assume that there would be simple AND/OR gates on the different bits in EFLAGS, to determine whether the conditions are met. There is then, no reason that an instruction testing two bits should take any more or less time than one testing only one (Ignoring gate propagation delay, which is much less than the clock period.)


Edit: Floating Point

This holds true for x87 floating point as well: (Pretty much same code as above, but with double instead of int.)

        fld     QWORD PTR [esp+32]         fld     QWORD PTR [esp+40]         fucomip st, st(1)              ; Compare ST(0) and ST(1), and set CF, PF, ZF in EFLAGS         fstp    st(0)         seta    al                     ; Set al if above (CF=0 and ZF=0).         test    al, al         je      .L2         ; Do something 1 .L2:          fld     QWORD PTR [esp+32]         fld     QWORD PTR [esp+40]         fucomip st, st(1)              ; (same thing as above)         fstp    st(0)         setae   al                     ; Set al if above or equal (CF=0).         test    al, al         je      .L5         ; Do something 2 .L5:         leave         ret 
vote vote

82

Historically (we're talking the 1980s and early 1990s), there were some architectures in which this was true. The root issue is that integer comparison is inherently implemented via integer subtractions. This gives rise to the following cases.

Comparison     Subtraction ----------     ----------- A < B      --> A - B < 0 A = B      --> A - B = 0 A > B      --> A - B > 0 

Now, when A < B the subtraction has to borrow a high-bit for the subtraction to be correct, just like you carry and borrow when adding and subtracting by hand. This "borrowed" bit was usually referred to as the carry bit and would be testable by a branch instruction. A second bit called the zero bit would be set if the subtraction were identically zero which implied equality.

There were usually at least two conditional branch instructions, one to branch on the carry bit and one on the zero bit.

Now, to get at the heart of the matter, let's expand the previous table to include the carry and zero bit results.

Comparison     Subtraction  Carry Bit  Zero Bit ----------     -----------  ---------  -------- A < B      --> A - B < 0    0          0 A = B      --> A - B = 0    1          1 A > B      --> A - B > 0    1          0 

So, implementing a branch for A < B can be done in one instruction, because the carry bit is clear only in this case, , that is,

;; Implementation of "if (A < B) goto address;" cmp  A, B          ;; compare A to B bcz  address       ;; Branch if Carry is Zero to the new address 

But, if we want to do a less-than-or-equal comparison, we need to do an additional check of the zero flag to catch the case of equality.

;; Implementation of "if (A <= B) goto address;" cmp A, B           ;; compare A to B bcz address        ;; branch if A < B bzs address        ;; also, Branch if the Zero bit is Set 

So, on some machines, using a "less than" comparison might save one machine instruction. This was relevant in the era of sub-megahertz processor speed and 1:1 CPU-to-memory speed ratios, but it is almost totally irrelevant today.

vote vote

70

Assuming we're talking about internal integer types, there's no possible way one could be faster than the other. They're obviously semantically identical. They both ask the compiler to do precisely the same thing. Only a horribly broken compiler would generate inferior code for one of these.

If there was some platform where < was faster than <= for simple integer types, the compiler should always convert <= to < for constants. Any compiler that didn't would just be a bad compiler (for that platform).

vote vote

60

I see that neither is faster. The compiler generates the same machine code in each condition with a different value.

if(a < 901) cmpl  $900, -4(%rbp) jg .L2  if(a <=901) cmpl  $901, -4(%rbp) jg .L3 

My example if is from GCC on x86_64 platform on Linux.

Compiler writers are pretty smart people, and they think of these things and many others most of us take for granted.

I noticed that if it is not a constant, then the same machine code is generated in either case.

int b; if(a < b) cmpl  -4(%rbp), %eax jge   .L2  if(a <=b) cmpl  -4(%rbp), %eax jg .L3 
vote vote

50

For floating point code, the <= comparison may indeed be slower (by one instruction) even on modern architectures. Here's the first function:

int compare_strict(double a, double b) { return a < b; } 

On PowerPC, first this performs a floating point comparison (which updates cr, the condition register), then moves the condition register to a GPR, shifts the "compared less than" bit into place, and then returns. It takes four instructions.

Now consider this function instead:

int compare_loose(double a, double b) { return a <= b; } 

This requires the same work as compare_strict above, but now there's two bits of interest: "was less than" and "was equal to." This requires an extra instruction (cror - condition register bitwise OR) to combine these two bits into one. So compare_loose requires five instructions, while compare_strict requires four.

You might think that the compiler could optimize the second function like so:

int compare_loose(double a, double b) { return ! (a > b); } 

However this will incorrectly handle NaNs. NaN1 <= NaN2 and NaN1 > NaN2 need to both evaluate to false.

Top 3 video Explaining c++ - Is < faster than <=?







Related QUESTION?