x<1과 x<10 중 어느 쪽이 빠릅니까?

x<1과 x<10 중 어느 쪽이 빠릅니까?

저는 아무것도 최적화하고 싶지 않습니다. 맹세코 호기심에서 이 질문을 하고 싶습니다.시프트(bit-shift)의 있습니다.shl,shr을 사용하다 시프트하는 수단위 단위)는요? 중 에서도 고속입니까?또는 「CPU」의 어느 입니까?

x << 1;

그리고.

x << 10;

그리고 이 질문 때문에 저를 미워하지 마세요.:)

CPU에 따라 다를 수 있습니다.

단, 현대의 모든 CPU(x86, ARM)는 일정한 시간에 임의의 시프트를 실행하도록 특별히 설계된 하드웨어 모듈인 "배럴 시프터"를 사용합니다.

그러니까 결론은...아뇨, 차이가 없어요

조립식 프로세서에 따라서는, 「시프트 바이 원」의 명령만 있는 경우가 있습니다.된다.x << 3((x << 1) << 1) << 1.

Motorola MC68HCxx는 이러한 제한이 있는 가장 인기 있는 패밀리 중 하나라고 생각합니다.다행히 지금은 이러한 아키텍처는 매우 드물며, 대부분 변속 크기가 가변적인 배럴 시프터를 포함하고 있습니다.

많은 최신 파생 모델을 탑재한 인텔 8051은 또한 임의의 수의 비트를 이동할 수 없습니다.

여기에는 많은 사례가 있다.

1. 많은 고속 MPU에는 일정한 시간 동안 변속을 하는 배럴 시프터, 멀티플렉서 같은 전자 회로가 있습니다.

2. 시프트 MPU가 인 경우x << 10보통 10교대 또는 2교대 바이트 복사에 의해 처리되기 때문에 속도가 느려집니다.

3. 흔히 있습니다.x << 10보다 더 빠를 것이다x << 1 모든 되기 대한 가 있습니다.x 가 16 비 MPU 는비비비 。따라서 MPU는 8비트 메모리에 대한 단일 액세스 사이클만 수행합니다.x << 102년 전이 shift byte)보다,x << 10RAM에 할 때 을 탑재한 마이크로 됩니다.이것은, 고속 온보드 프로그램 ROM 를 탑재한 마이크로 컨트롤러로, 저속 외부 데이터 RAM 에 액세스 하고 있는 경우에 적용됩니다.

4. 3과 는 3의 유효 비트 수 .x << 10또한 16x16 곱셈을 16x8로 대체하는 등 더 작은 폭의 곱셈에 대한 추가 연산을 최적화합니다(낮은 바이트는 항상 0임).

전혀 명령어는 '시프트 왼쪽 명령어는 시프트 왼쪽 명령어는 '시프트 왼쪽 명령어'를 사용합니다.add x,x★★★★★★ 。

항상 그렇듯이 주변 코드 컨텍스트에 따라 달라집니다. 예를 들어,x<<1어레이 인덱스로요?아니면 다른 것에 추가하는 건가요?어느 경우든 시프트 카운트가 작을 경우(1 또는 2)는 컴파일러가 시프트만 하면 되는 경우보다 더 많은 시프트 카운트를 최적화할 수 있습니다.전체 throughput 대 지연 시간 대 프런트 엔드 병목 현상 간의 균형은 말할 것도 없습니다.작은 조각의 성능은 일차원적이지 않다.

만의 컴파일 .x<<1하지만 다른 답변은 대부분 그렇게 가정하고 있습니다.

---

x << 1 는 부호 없는 정수 및 2의 보완 부호 있는 정수와 정확히 동일합니다.컴파일러는 컴파일할 때 어떤 하드웨어를 대상으로 하는지 항상 알고 있기 때문에 이러한 기술을 활용할 수 있습니다.

인텔 Haswell에서는add throughput은인데, "4" 입니다.shl즉시 카운트를 지정하면 클럭당 throughput은 2개뿐입니다(순서 테이블 및 x86 태그 Wiki의 기타 링크에 대해서는http://http://agner.org/optimize/ 를 참조해 주세요).SIMD 벡터 시프트는 클럭당 1개(Skylake에서는 2개)이지만 SIMD 벡터 정수 추가는 클럭당 2개(Skylake에서는 3개)입니다.지연 시간은 동일하지만 1사이클입니다.

또한 특별한 시프트 바이 원 인코딩이 있습니다.shl여기서 카운트는 opcode에 암묵적으로 포함되어 있습니다.8086에는 즉시 카운트 시프트가 없으며, 1개씩, 2개 단위로만 변경 가능cl등록하세요.메모리 피연산자를 이동하지 않는 한 왼쪽 시프트에 추가할 수 있기 때문에 이것은 주로 오른쪽 시프트와 관련이 있습니다.그러나 나중에 값이 필요하면 먼저 레지스터에 로드하는 것이 좋습니다.근데 어쨌든shl eax,1또는add eax,eax보다 1바이트 짧다shl eax,10코드 사이즈는 퍼포먼스에 직접(디코딩/프런트 엔드 병목 현상) 또는 간접(L1I 코드 캐시 누락)으로 영향을 줄 수 있습니다.

보다 일반적으로 x86의 어드레싱 모드에서 작은 시프트 카운트를 스케일링된 인덱스로 최적화할 수 있습니다.오늘날 일반적으로 사용되는 다른 아키텍처는 대부분 RISC이며 스케일 인덱스 어드레싱 모드가 없습니다.그러나 x86은 언급할 가치가 있을 만큼 일반적인 아키텍처입니다.(예를 들어, 4바이트 요소의 배열을 인덱싱하는 경우 스케일 팩터를 1만큼 늘릴 수 있습니다.int arr[]; arr[x<<1]).

---

복사+시프트의 필요성은 원래 값이 다음과 같은 상황에서 흔히 볼 수 있습니다.x여전히 필요합니다.그러나 대부분의 x86 정수 명령어는 즉석에서 작동합니다.(수신처는 다음과 같은 명령의 소스 중 하나입니다.add또는shl) x86-64 System V 호출 규약은 레지스터의 arg를 전달하고 첫 번째 arg는edi값을 반환하다eax따라서 반환되는 함수는x<<10또한 컴파일러가 copy+shift 코드를 내보냅니다.

이 명령어를 사용하면 시프트 앤 추가를 할 수 있습니다(주소 지정 모드머신 인코딩을 사용하기 때문에 시프트 카운트는 0 ~3).그러면 결과가 별도의 레지스터에 저장됩니다.

gcc와 clang은 모두 Godbolt 컴파일러 탐색기에서 볼 수 있는 것과 같은 방식으로 이러한 기능을 최적화합니다.

int shl1(int x) { return x<<1; }
    lea     eax, [rdi+rdi]   # 1 cycle latency, 1 uop
    ret

int shl2(int x) { return x<<2; }
    lea     eax, [4*rdi]    # longer encoding: needs a disp32 of 0 because there's no base register, only scaled-index.
    ret

int times5(int x) { return x * 5; }
    lea     eax, [rdi + 4*rdi]
    ret

int shl10(int x) { return x<<10; }
    mov     eax, edi         # 1 uop, 0 or 1 cycle latency
    shl     eax, 10          # 1 uop, 1 cycle latency
    ret

2개의 컴포넌트로 구성된 LEA는 최신 인텔 및 AMD CPU에서 1사이클의 레이텐시와 2클럭당 스루풋을 실현합니다(Sandybridge 패밀리 및 불도저/Ryzen).인텔에서는 클럭당1개의 스루풋에 3c의 레이텐시가 있습니다.lea eax, [rdi + rsi + 123]. (관련:이 C++ 코드가 콜라츠 추측을 테스트하기 위해 손으로 쓴 어셈블리보다 빠른 이유는 무엇입니까?상세하게 설명합니다.)

어쨌든 copy+shift를 10으로 나누려면 별도의 작업이 필요합니다.mov설명.최근의 많은 CPU에서는 레이텐시가 제로일 수 있지만 프런트 엔드 대역폭과 코드 사이즈가 필요합니다.(x86의 MOV는 정말 '공짜'가 될 수 있을까요? 왜 전혀 재현할 수 없는 거죠?

관련 정보:x86에서 두 개의 연속된 명령어를 사용하여 레지스터에 37을 곱하는 방법은 무엇입니까?

---

컴파일러는 또한 주변 코드를 자유롭게 변환하여 실제 시프트가 없거나 다른 작업과 결합할 수 있습니다.

예를들면if(x<<1) { }필요한 것은and하이비트를 제외한 모든 비트를 체크합니다.x86 에서는,test예를 들어 명령어test eax, 0x7fffffff/jz .false대신shl eax,1 / jz이 최적화는 모든 시프트 카운트에 대응합니다.또한 대규모 시프트가 느린 머신(Pentium 4 등)이나 존재하지 않는 머신(일부 마이크로 컨트롤러)에서도 동작합니다.

많은 ISA는 단순히 시프트를 넘어 비트 조작 명령을 가지고 있습니다.예를 들어, 전원.PC에는 많은 비트 필드 추출/삽입 명령이 있습니다.또는 ARM에는 다른 명령의 일부로 소스 오퍼랜드의 이동이 있습니다.(따라서 시프트/회전 지시는 특별한 형태일 뿐입니다).move(시프트된 소스를 사용합니다).

C는 어셈블리 언어가 아닙니다.효율적인 컴파일을 위해 소스 코드를 조정할 때는 항상 최적화된 컴파일러 출력을 살펴보십시오.

8비트 프로세서에서는, 다음과 같이 생각할 수 있습니다.x<<1실제로는 보다 훨씬 느릴 수 있다x<<1016비트 값으로 설정합니다.

예를 들어, 의 적절한 번역은x<<1다음과 같은 경우가 있습니다.

byte1 = (byte1 << 1) | (byte2 >> 7)
byte2 = (byte2 << 1)

반면에.x<<10보다 심플합니다.

byte1 = (byte2 << 2)
byte2 = 0

주의:x<<1보다 더 자주, 그리고 심지어 더 멀리 이동x<<10더 나아가, 결과도x<<10byte1의 내용에 의존하지 않습니다.이것에 의해, 조작의 속도가 한층 더 빨라질 가능성이 있습니다.

이는 CPU와 컴파일러에 따라 달라집니다.기본 CPU가 배럴 시프터를 사용하여 임의의 비트 시프트를 수행하더라도 컴파일러가 해당 리소스를 활용할 경우에만 발생합니다.

데이터 비트의 폭 외 이동은 C 및 C++에서는 "정의되지 않은 동작"이라는 점에 유의하십시오.서명된 데이터의 오른쪽 이동도 "실장 정의"됩니다.속도에 대해 너무 많이 우려하기보다는 여러 구현에서 동일한 답변을 얻을 수 있다는 점에 유의하십시오.

ANSI C 섹션 3.3.7에서 인용:

3.3.7 비트 시프트 연산자

구문

      shift-expression:
              additive-expression
              shift-expression <<  additive-expression
              shift-expression >>  additive-expression

제약

각 피연산자는 일체형이어야 한다.

의미론

통합 프로모션은 각 오퍼랜드에 대해 수행됩니다.결과의 유형은 승격된 왼쪽 피연산자의 유형입니다.오른쪽 피연산자의 값이 음수이거나 승격된 왼쪽 피연산자의 비트 폭 이상일 경우 동작은 정의되지 않습니다.

E1 < E2의 결과는 E1의 좌측 시프트 E2 비트 위치입니다.빈 비트는 0으로 채워집니다.E1이 부호 없는 타입이면 결과값은 E1에 곱한 값, 2를 곱한 값, E1이 부호 없는 긴 타입이면 감소 모듈 ULONG_MAX+1이 된다.(상수 ULONG_MAX 및 UINT_MAX는 헤더에 정의되어 있습니다).

E1 > > E2의 결과는 E1의 오른쪽 시프트E2 비트 위치입니다E1에 부호 없는 타입이 있는 경우 또는 E1에 부호 없는 타입이 있고 음이 아닌 값이 있는 경우, 결과의 값은 E1의 몫의 정수 부분을 E2로 나눈 값이다. E1에 부호 있는 타입과 음의 값이 있는 경우, 결과 값은 구현 정의된다.

그래서:

x = y << z;

"<: y × 2^z(오버플로가 발생하는 경우 제외);

x = y >> z;

">": 서명된 구현 정의(대부분 산술 시프트의 결과: y / 2^z).

일부 세대의 인텔 CPU(P2 또는 P3)에서는?AMD는 아니지만, 제 기억으로는) 비트 시프트 조작이 터무니없이 느립니다.단, 1비트 단위의 비트 시프트는 덧셈만 사용할 수 있기 때문에 항상 빠릅니다.고려해야 할 또 하나의 문제는 일정한 비트 수에 의한 비트 이동이 가변 길이 시프트보다 빠른지 여부입니다.연산코드가 같은 속도라도 x86에서는 비트시프트의 불연속적인 righthand 피연산자가 CL 레지스터를 점유해야 합니다.이것에 의해 레지스터 할당에 추가의 제약이 부과되어 프로그램의 속도가 저하될 가능성이 있습니다.

ARM 에서는, 이것은 다른 명령의 부작용으로 실시할 수 있습니다.따라서 둘 다 대기 시간이 전혀 없을 수 있습니다.

여기 제가 가장 좋아하는 CPU가 있습니다.x<<2보다 두 배나 오래 걸린다x<<1:)

언급URL : https://stackoverflow.com/questions/4234120/which-is-faster-x1-or-x10