<가 <=보다 빠릅니까?

질문자 :snoopy

if (a <= 900) 보다 if (a < 901) 더 빠릅니까?

이 간단한 예제와 정확히 같지는 않지만 루프 복잡한 코드에서 약간의 성능 변화가 있습니다. 이것이 사실일 경우를 대비하여 생성된 기계어 코드와 관련이 있다고 생각합니다.

아니요, 대부분의 아키텍처에서는 더 빠르지 않습니다. 지정하지 않았지만 x86에서 모든 적분 비교는 일반적으로 두 가지 기계 명령어로 구현됩니다.

• EFLAGS 를 설정하는 test 또는 cmp
• 비교 유형(및 코드 레이아웃)에 따라 Jcc (점프) 명령:
  • jne - 같지 않으면 점프 --> ZF = 0
  • jz - 0이면 점프(같음) --> ZF = 1
  • jg - 크면 점프 --> ZF = 0 and SF = OF
  • (등...)

---

예제 (간결함을 위해 편집됨) $ gcc -m32 -S -masm=intel test.c

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

컴파일:

 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:

그리고

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

컴파일:

 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:

따라서 둘 사이의 유일한 차이점은 jg 대 jge 명령어입니다. 둘은 같은 시간이 걸립니다.

---

다른 점프 명령에 동일한 시간이 걸린다는 것을 나타내는 것은 없다는 의견을 말씀드리고 싶습니다. Jcc 만 제가 드릴 수 있는 것은 다음과 같습니다. Intel Instruction Set Reference 에서 모두 Jcc(조건이 충족되면 점프)라는 하나의 공통 명령 아래 함께 그룹화됩니다. 부록 C. 대기 시간 및 처리량 의 Optimization Reference Manual(최적화 참조 설명서 )에서 동일한 그룹이 함께 만들어집니다.

대기 시간 — 실행 코어가 명령어를 구성하는 모든 μop의 실행을 완료하는 데 필요한 클록 사이클 수입니다.

처리량 — 문제 포트가 동일한 명령을 다시 수락할 수 있기 전에 대기하는 데 필요한 클록 주기 수입니다. 많은 명령어의 경우 명령어의 처리량이 대기 시간보다 훨씬 적을 수 있습니다.

Jcc 의 값은 다음과 같습니다.

 Latency Throughput Jcc N/A 0.5

Jcc 에 대한 다음 각주와 함께 :

7) 조건부 점프 명령어의 선택은 섹션 3.4.1, “분기 예측 최적화”의 권장 사항을 기반으로 해야 분기 예측 가능성을 향상시킬 수 있습니다. 분기가 성공적으로 예측되면 jcc 의 대기 시간은 사실상 0입니다.

따라서 Intel 문서의 어떤 것도 Jcc 명령어를 다른 명령어와 다르게 취급하지 않습니다.

명령을 구현하는 데 사용되는 실제 회로에 대해 생각하면 EFLAGS 의 다른 비트에 간단한 AND/OR 게이트가 있다고 가정하여 조건이 충족되는지 여부를 결정할 수 있습니다. 따라서 2비트를 테스트하는 명령어가 1개만 테스트하는 것보다 더 많거나 더 적은 시간이 소요되어야 할 이유가 없습니다(클럭 주기보다 훨씬 짧은 게이트 전파 지연 무시).

---

편집: 부동 소수점

이것은 x87 부동 소수점에도 적용됩니다. (위와 거의 동일한 코드이지만 int 대신 double 사용합니다.)

 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

Jonathon Reinhart

역사적으로(우리는 1980년대와 1990년대 초를 말하고 있음) 이것이 사실인 일부 아키텍처가 있었습니다. 근본적인 문제는 정수 비교가 본질적으로 정수 빼기를 통해 구현된다는 것입니다. 이로 인해 다음과 같은 경우가 발생합니다.

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

A < B 일 때 뺄셈이 정확하려면 뺄셈에서 높은 비트를 빌려야 합니다. 손으로 더하고 뺄 때 나르고 빌리는 것과 같습니다. 이 "빌린" 비트는 일반적으로 캐리 비트 라고 하며 분기 명령으로 테스트할 수 있습니다. 0 비트라고 하는 두 번째 비트는 뺄셈이 동등함을 의미하는 동일하게 0인 경우 설정됩니다.

일반적으로 적어도 두 개의 조건부 분기 명령이 있었습니다. 하나는 캐리 비트에서 분기하고 다른 하나는 0 비트에서 분기합니다.

이제 문제의 핵심을 이해하기 위해 이전 테이블을 확장하여 캐리 및 0비트 결과를 포함하도록 하겠습니다.

 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

A < B 대한 분기를 구현하는 것은 하나의 명령어로 수행될 수 있습니다. 왜냐하면 이 경우 에만 캐리 비트가 명확하기 때문입니다. 즉,

 ;; 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

그러나 작거나 같음 비교를 수행하려면 같음의 경우를 포착하기 위해 0 플래그에 대한 추가 검사를 수행해야 합니다.

 ;; 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

따라서 일부 컴퓨터에서는 "보다 작음" 비교를 사용하면 하나의 기계 명령어를 저장할 수 있습니다 . 이것은 서브 메가헤르츠 프로세서 속도와 1:1 CPU 대 메모리 속도 비율의 시대와 관련이 있었지만 오늘날에는 거의 관련이 없습니다.

Lucas

내부 정수 유형에 대해 이야기하고 있다고 가정하면 하나가 다른 유형보다 빠를 수 있는 방법이 없습니다. 그것들은 분명히 의미적으로 동일합니다. 둘 다 컴파일러에게 정확히 동일한 작업을 수행하도록 요청합니다. 끔찍하게 망가진 컴파일러만이 이들 중 하나에 대해 열등한 코드를 생성할 것입니다.

일부 플랫폼 있었다면 < 보다 더 빨리했다 <= 간단한 정수 유형의 경우, 컴파일러는 항상 변환해야합니다 <= 으로 < 상수. (해당 플랫폼에 대한) 나쁜 컴파일러가 아닌 모든 컴파일러.

David Schwartz

나는 어느 쪽도 더 빠르지 않다고 본다. 컴파일러는 각 조건에서 다른 값으로 동일한 기계어 코드를 생성합니다.

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

내 예는 if 리눅스에 x86_64의 플랫폼에서 GCC에서입니다.

컴파일러 작성자는 꽤 똑똑한 사람들이며 이러한 것들을 생각하고 우리 대부분은 당연하게 여기는 많은 다른 사람들을 생각합니다.

상수가 아니면 두 경우 모두 동일한 기계어 코드가 생성된다는 것을 알았습니다.

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

Adrian Cornish

부동 소수점 코드의 경우 현대 아키텍처에서도 <= 비교가 실제로 (하나의 명령어로) 더 느릴 수 있습니다. 첫 번째 기능은 다음과 같습니다.

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

PowerPC에서 이것은 먼저 부동 소수점 비교( cr 업데이트)를 수행한 다음 조건 레지스터를 GPR로 이동하고 "비교된 미만" 비트를 제자리로 이동한 다음 반환합니다. 네 가지 지시가 필요합니다.

이제 이 함수를 대신 고려하십시오.

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

compare_strict 와 동일한 작업이 필요하지만 이제 "보다 작음" 및 "같음"이라는 두 가지 관심 사항이 있습니다. 이 두 비트를 하나로 결합하려면 추가 명령( cror - condition register bitwise OR)이 필요합니다. 따라서 compare_loose 에는 5개의 명령어가 필요하고 compare_strict 에는 4개가 필요합니다.

컴파일러가 다음과 같이 두 번째 함수를 최적화할 수 있다고 생각할 수도 있습니다.

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

그러나 이것은 NaN을 잘못 처리합니다. NaN1 <= NaN2 및 NaN1 > NaN2 는 둘 다 false로 평가되어야 합니다.

ridiculous_fish

아마도 그 이름 없는 책의 저자는 a > 0 a >= 1 보다 빠르게 실행된다는 것을 읽고 그것이 보편적으로 사실이라고 생각했을 것입니다.

그러나 0 이 관련되어 있기 때문입니다( CMP 는 아키텍처에 따라 예를 들어 OR 로 대체될 수 있기 때문에). < 때문이 아닙니다.

glglgl

최소한 이것이 사실이라면 컴파일러는 a <= b를 !(a > b)로 간단하게 최적화할 수 있으므로 비교 자체가 실제로 느리더라도 가장 순진한 컴파일러를 제외하고는 차이를 느끼지 못할 것입니다. .

Eliot Ball

그들은 같은 속도를 가지고 있습니다. 어쩌면 어떤 특별한 아키텍처에서는 그가 말한 것이 옳았을 수도 있지만 적어도 x86 제품군에서 나는 그것들이 동일하다는 것을 알고 있습니다. 이를 위해 CPU는 빼기(a - b)를 수행한 다음 플래그 레지스터의 플래그를 확인합니다. 그 레지스터의 두 비트를 ZF(제로 플래그) 및 SF(부호 플래그)라고 하며 하나의 마스크 작업으로 수행하기 때문에 한 사이클에서 수행됩니다.

Masoud

이것은 C가 컴파일되는 기본 아키텍처에 크게 의존합니다. 일부 프로세서 및 아키텍처에는 같음 또는 작음 및 같음에 대한 명시적 명령이 있을 수 있으며, 이는 다른 수의 주기로 실행됩니다.

컴파일러가 이 문제를 해결하여 관련이 없도록 만들 수 있기 때문에 이는 매우 이례적인 일입니다.

Telgin

TL;DR 답변

대부분의 아키텍처, 컴파일러 및 언어 조합의 경우 < <= 보다 빠르지 않습니다.

전체 답변

다른 답변은 x86 아키텍처 에 집중되어 있으며 생성된 코드에 대해 구체적으로 언급할 만큼 ARM 아키텍처(귀하의 어셈블러 예제인 것 같습니다)를 잘 모르지만 이것은 아키텍처가 매우 뛰어난 마이크로 최적화의 예입니다. 구체적이며 최적화와 마찬가지로 반최적화일 가능성이 높습니다 .

따라서 이러한 종류의 미세 최적화 는 최고의 소프트웨어 엔지니어링 사례라기보다는 화물 숭배 프로그래밍의 한 예라고 제안합니다.

반례

이이 최적화 일부 아키텍처는 아마도,하지만 난 그 반대가 사실 일 수도 적어도 하나의 아키텍처 알고있다. 유서 깊은 Transputer 아키텍처에는 같음 및 크거나 같음에 대한 기계어 코드 명령만 있으므로 모든 비교는 이러한 기본 요소에서 작성해야 했습니다.

그럼에도 불구하고 거의 모든 경우에 컴파일러는 실제로 어떤 비교도 다른 어떤 것보다 이점이 없는 방식으로 평가 명령을 주문할 수 있습니다. 최악의 경우 피연산자 스택 의 상위 두 항목을 교환하기 위해 역방향 명령어(REV)를 추가해야 할 수도 있습니다. 이것은 실행하는 데 단일 주기가 필요한 단일 바이트 명령이므로 가능한 가장 작은 오버헤드가 있었습니다.

요약

이와 같은 미세 최적화가 최적화 인지 반 최적화인지는 사용 중인 특정 아키텍처에 따라 다르므로 아키텍처별 미세 최적화를 사용하는 습관을 갖는 것은 일반적으로 좋지 않습니다. 그렇지 않으면 본능적으로 그렇게 하는 것이 부적절할 때 하나를 사용하십시오. 그리고 이것이 바로 당신이 읽고 있는 책이 옹호하는 것과 같습니다.

Mark Booth

차이가 있더라도 그 차이를 알아차릴 수 없어야 합니다. 게다가, 실제로, 어떤 마법 상수를 사용하지 않는 한 조건을 유지하기 위해 a + 1 또는 a - 1

shinkou

추가 문자로 인해 코드 처리 속도가 약간 느려지므로 대부분의 스크립팅 언어에서 행이 정확하다고 말할 수 있습니다. 그러나 최고 답변이 지적했듯이 C++에서는 영향을 미치지 않아야 하며 스크립팅 언어로 수행되는 모든 작업은 아마도 최적화에 대해 그다지 걱정하지 않을 것입니다.

Ecksters

a < 901 vs. a <= 900 의 특정 예가 아니라 일반적으로 < vs. <= 에 대한 제목 질문만 보고 있었습니다. < 와 <= 사이를 변환하여 항상 상수의 크기를 줄입니다. 예를 들어 x86 직접 피연산자가 -128..127에 대해 더 짧은 1바이트 인코딩을 갖기 때문입니다.

ARM의 경우 즉시로 인코딩할 수 있는지 여부는 좁은 필드를 단어의 임의 위치로 회전할 수 있는지 여부에 달려 있습니다. 따라서 cmp r0, #0x00f000 은 인코딩할 수 있지만 cmp r0, #0x00efff 는 인코딩할 수 없습니다. 따라서 컴파일 시간 상수와 비교를 위한 더 작게 만들기 규칙이 ARM에 항상 적용되는 것은 아닙니다. AArch64는 32비트 ARM 및 Thumb 모드와 달리 cmp 및 cmn 과 같은 명령어에 대해 임의 회전 대신 12만큼 시프트하거나 그렇지 않습니다.

---

< 대 <= 일반적으로 런타임 변수 조건 포함

대부분의 머신의 어셈블리 언어에서 <= < 대한 비교와 비용이 같습니다. 이것은 분기를 하든, 0/1 정수를 생성하기 위해 불리언화하든, 또는 x86 CMOV와 같은 분기 없는 선택 작업의 술어로 사용하든 적용됩니다. 다른 답변은 질문의 이 부분만 다루었습니다.

그러나 이 질문은 옵티마이저에 대한 입력인 C++ 연산자에 관한 것입니다. 일반적으로 둘 다 똑같이 효율적입니다. 컴파일러는 항상 asm에서 구현하는 비교를 변환할 수 있기 때문에 책의 조언은 완전히 가짜처럼 들립니다. <= 사용하면 컴파일러가 최적화할 수 없는 것을 실수로 생성할 수 있는 예외가 적어도 하나는 있습니다.

루프 조건으로 컴파일러가 루프가 무한하지 않다는 것을 증명하지 못하게 할 때 <= 가 < 와 질적으로 다른 경우가 있습니다. 이것은 자동 벡터화를 비활성화하여 큰 차이를 만들 수 있습니다.

부호 없는 오버플로는 부호 있는 오버플로(UB)와 달리 base-2 랩 어라운드로 잘 정의됩니다. 부호 있는 루프 카운터는 일반적으로 부호 있는 오버플로 UB가 발생하지 않는 것을 기반으로 최적화하는 컴파일러를 사용하여 이것으로부터 안전합니다. ++i <= size 는 항상 결국 false가 됩니다. ( 모든 C 프로그래머가 정의되지 않은 동작에 대해 알아야 할 사항 )

 void foo(unsigned size) { unsigned upper_bound = size - 1; // or any calculation that could produce UINT_MAX for(unsigned i=0 ; i <= upper_bound ; i++) ...

컴파일러는 정의되지 않은 동작으로 이어지는 값을 제외하고 가능한 모든 입력 값에 대해 C++ 소스의 (정의되고 법적으로 관찰 가능한) 동작을 보존하는 방식으로만 최적화할 수 있습니다.

(간단한 i <= size 도 문제를 일으킬 수 있지만 상한을 계산하는 것이 당신이 신경 쓰지 않지만 컴파일러가 고려해야 하는 입력에 대해 무한 루프의 가능성을 실수로 도입하는 보다 현실적인 예라고 생각했습니다. )

이 경우 size=0 은 upper_bound=UINT_MAX 로 연결되고 i <= UINT_MAX 는 항상 true입니다. 따라서 이 루프는 size=0 대해 무한하며 컴파일러는 프로그래머로서 아마도 size=0을 전달하지 않으려는 경우에도 이를 존중해야 합니다. 컴파일러가 size=0 이 불가능하다는 것을 증명할 수 있는 호출자에 이 함수를 인라인할 수 있다면 i < size 대해 가능한 것처럼 최적화할 수 있습니다.

if(!size)와 같은 Asm if(!size) skip the loop; do{...}while(--size); i 의 실제 값이 필요하지 않은 for( i<size ) 루프를 최적화하는 일반적으로 효율적인 방법 중 하나 입니다( 루프가 항상 "do...while" 스타일(꼬리 점프)로 컴파일되는 이유는 무엇입니까? ).

하지만{}무한할 수는 없습니다. size==0 입력하면 2^n회 반복됩니다. ( for 루프 C에서 모든 unsigned 정수에 대해 반복 하면 0을 포함한 모든 unsigned 정수에 대한 루프를 표현할 수 있지만 asm에서와 같이 carry 플래그가 없으면 쉽지 않습니다.)

루프 카운터의 랩어라운드가 가능하기 때문에 최신 컴파일러는 종종 "포기"하고 거의 공격적으로 최적화하지 않습니다.

예: 1에서 n까지의 정수의 합

i <= n 사용하면 Gauss의 n * (n+1) / 2 공식을 기반으로 하는 닫힌 형식 sum(1 .. n) 루프를 최적화하는 clang의 관용구 인식이 무효화됩니다.

 unsigned sum_1_to_n_finite(unsigned n) { unsigned total = 0; for (unsigned i = 0 ; i < n+1 ; ++i) total += i; return total; }

Godbolt 컴파일러 탐색기의 clang7.0 및 gcc8.2에서 x86-64 asm

 # clang7.0 -O3 closed-form cmp edi, -1 # n passed in EDI: x86-64 System V calling convention je .LBB1_1 # if (n == UINT_MAX) return 0; // C++ loop runs 0 times # else fall through into the closed-form calc mov ecx, edi # zero-extend n into RCX lea eax, [rdi - 1] # n-1 imul rax, rcx # n * (n-1) # 64-bit shr rax # n * (n-1) / 2 add eax, edi # n + (stuff / 2) = n * (n+1) / 2 # truncated to 32-bit ret # computed without possible overflow of the product before right shifting .LBB1_1: xor eax, eax ret

그러나 순진한 버전의 경우 clang에서 멍청한 루프를 얻습니다.

 unsigned sum_1_to_n_naive(unsigned n) { unsigned total = 0; for (unsigned i = 0 ; i<=n ; ++i) total += i; return total; }

 # clang7.0 -O3 sum_1_to_n(unsigned int): xor ecx, ecx # i = 0 xor eax, eax # retval = 0 .LBB0_1: # do { add eax, ecx # retval += i add ecx, 1 # ++1 cmp ecx, edi jbe .LBB0_1 # } while( i<n ); ret

---

GCC는 어느 쪽이든 닫힌 형식을 사용하지 않으므로 루프 조건을 선택해도 문제가 되지 않습니다 . SIMD 정수 추가로 자동 벡터화하여 XMM 레지스터의 요소에서 i

 # "naive" inner loop .L3: add eax, 1 # do { paddd xmm0, xmm1 # vect_total_4.6, vect_vec_iv_.5 paddd xmm1, xmm2 # vect_vec_iv_.5, tmp114 cmp edx, eax # bnd.1, ivtmp.14 # bound and induction-variable tmp, I think. ja .L3 #, # }while( n > i ) "finite" inner loop # before the loop: # xmm0 = 0 = totals # xmm1 = {0,1,2,3} = i # xmm2 = set1_epi32(4) .L13: # do { add eax, 1 # i++ paddd xmm0, xmm1 # total[0..3] += i[0..3] paddd xmm1, xmm2 # i[0..3] += 4 cmp eax, edx jne .L13 # }while( i != upper_limit ); then horizontal sum xmm0 and peeled cleanup for the last n%3 iterations, or something.

n 및/또는 무한 루프의 경우에 사용하는 일반 스칼라 루프가 있습니다.

BTW, 이 두 루프 모두 루프 오버헤드에 대한 명령(및 Sandybridge 계열 CPU의 경우 uop)을 낭비합니다. add eax,1 /cmp/jcc 대신 sub eax,1 / jnz 가 더 효율적입니다. 2 대신 1 uop(sub/jcc 또는 cmp/jcc의 매크로 융합 후). 두 루프 이후의 코드는 무조건 EAX를 작성하므로 루프 카운터의 최종 값을 사용하지 않습니다.

Peter Cordes

컴퓨터를 만든 사람이 부울 논리로 나쁜 경우에만. 그들이 있어서는 안 될 것입니다.

모든 비교( >= <= > < )는 동일한 속도로 수행될 수 있습니다.

모든 비교는 단지 빼기(차이)와 그것이 양수/음수인지 확인하는 것입니다.
( msb 가 설정되면 숫자는 음수입니다)

a >= b 를 확인하는 방법? Sub ab >= 0 ab 가 양수인지 확인합니다.
a <= b 를 확인하는 방법? Sub 0 <= ba ba 가 양수인지 확인합니다.
a < b 를 확인하는 방법? Sub ab < 0 ab 가 음수인지 확인합니다.
a > b 를 확인하는 방법? Sub 0 > ba ba 가 음수인지 확인합니다.

간단히 말해서, 컴퓨터는 주어진 작업에 대해 후드 아래에서 이 작업을 수행할 수 있습니다.

a >= b == msb(ab)==0
a <= b == msb(ba)==0
a > b == msb(ba)==1
a < b == msb(ab)==1

==0 또는 ==1 을 수행할 필요가 없습니다.
==0 경우 회로 msb 를 반전시킬 수 있습니다.

a >= b a>b || a==b 로 계산하지 않았을 것입니다. a>b || a==b ㅋㅋㅋㅋ

Puddle

출처 : http:www.stackoverflow.com/questions/12135518/is-faster-than