x << 1 또는 x << 10 중 어느 것이 더 빠릅니까?

x << 1 또는 x << 10 중 어느 것이 더 빠릅니까?

---

나는 아무것도 최적화하고 싶지 않습니다. 맹세합니다. 호기심에서이 질문을하고 싶습니다. 나는 대부분의 하드웨어에서 비트 변화 (예를 들면의 어셈블리 명령어가 있다는 것을 알고 shl, shr하나의 명령이다). 그러나 얼마나 많은 비트를 이동하는지가 중요합니까 (나노초 단위 또는 CPU 전술 단위). 즉, 다음 중 하나가 CPU에서 더 빠릅니까?

x << 1;

과

x << 10;

그리고이 질문에 대해 나를 미워하지 마십시오. :)

---

잠재적으로 CPU에 따라 다릅니다.

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

그래서 결론은 ... 아뇨. 차이 없음.

---

일부 임베디드 프로세서에는 "하나씩 이동"명령 만 있습니다. 같은 프로세서에서 컴파일러는 바꿀 것 x << 3으로 ((x << 1) << 1) << 1.

모토로라 MC68HCxx는 이러한 한계가있는 가장 인기있는 제품군 중 하나라고 생각합니다. 다행히도 이러한 아키텍처는 현재 매우 드물며 대부분은 가변 시프트 크기의 배럴 시프터를 포함합니다.

최신 파생 제품이 많은 Intel 8051은 임의의 비트 수를 이동할 수 없습니다.

---

이것에 대한 많은 경우가 있습니다.

1. 많은 고속 MPU에는 배럴 시프터, 멀티플렉서와 ​​같은 전자 회로가있어 일정한 시간에 모든 시프트를 수행합니다.

2. MPU에 1 비트 시프트 만있는 경우 x << 10일반적으로 10 시프트 또는 2 시프트로 바이트 복사로 수행되므로 일반적으로 더 느립니다.

3. 그러나 일반적인 경우가 알려져 x << 10도 될 것 빠른 이상을 x << 1. x가 16 비트 인 경우 하위 6 비트 만주의해야합니다 (다른 모든 비트는 시프트 됨). 따라서 MPU는 하위 바이트 만로드하면되므로 8 비트 메모리에 대한 단일 액세스 주기만 만들고 x << 102 개의 액세스주기가 필요합니다. 액세스주기가 시프트보다 느리면 (하위 바이트 지우기) x << 10더 빠릅니다. 이것은 느린 외부 데이터 RAM에 액세스하는 동안 빠른 온보드 프로그램 ROM이있는 마이크로 컨트롤러에 적용될 수 있습니다.

4. 경우 3 외에도 컴파일러는 x << 1016x16 곱셈을 16x8 1로 바꾸는 것과 같이 (하위 바이트는 항상 0이므로) 더 낮은 너비의 비트로 추가 작업을 최적화 할 수 있습니다.

일부 마이크로 컨트롤러에는 왼쪽 시프트 명령이 전혀 없으며 add x,x대신 사용 합니다.

---

ARM에서는 다른 명령어의 부작용으로이 작업을 수행 할 수 있습니다. 따라서 잠재적으로 둘 중 하나에 대해 대기 시간이 전혀 없습니다.

---

여기 내가 좋아하는 CPU 하는, x<<2만큼 배 걸립니다 x<<1:)

---

이는 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를 E2 거듭 제곱하고 E1에 부호없는 long 유형이 있으면 모듈로 ULONG_MAX + 1이 감소하고 그렇지 않으면 UINT_MAX + 1이됩니다. (상수 ULONG_MAX 및 UINT_MAX는 헤더에 정의되어 있습니다.)

E1 >> E2의 결과는 E1 오른쪽으로 이동 한 E2 비트 위치입니다. E1에 부호없는 유형이 있거나 E1에 부호있는 유형과 음이 아닌 값이있는 경우 결과 값은 E1 몫의 정수 부분을 수량으로 나눈 값 2를 E2 제곱합니다. E1에 부호있는 유형과 음수 값이있는 경우 결과 값은 구현에서 정의됩니다.

그래서:

x = y << z;

"<<": y × 2 ^z ( 오버플로가 발생하면 정의되지 않음 );

x = y >> z;

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

---

8 비트 프로세서에서는 x<<1실제로 16 비트 값 보다 훨씬 느릴 수 있습니다 x<<10.

For example a reasonable translation of x<<1 may be:

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

whereas x<<10 would be more simple:

byte1 = (byte2 << 2)
byte2 = 0

Notice how x<<1 shifts more often and even farther than x<<10. Furthermore the result of x<<10 doesn't depend on the content of byte1. This could speed up the operation additionally.

---

On some generations of Intel CPUs (P2 or P3? Not AMD though, if I remember right), the bitshift operations are ridiculously slow. Bitshift by 1 bit should always be fast though since it can just use addition. Another question to consider is whether bitshifts by a constant number of bits are faster than variable-length shifts. Even if the opcodes are the same speed, on x86 the nonconstant righthand operand of a bitshift must occupy the CL register, which imposes additional constrains on register allocation and may slow the program down that way too.

---

As always, it depends on the surrounding code context: e.g. are you using x<<1 as an array index? Or adding it to something else? In either case, small shift counts (1 or 2) can often optimize even more than if the compiler ends up having to just shift. Not to mention the whole throughput vs. latency vs. front-end bottlenecks tradeoff. Performance of a tiny fragment is not one-dimensional.

A hardware shift instructions is not a compiler's only option for compiling x<<1, but the other answers are mostly assuming that.

---

x << 1 is exactly equivalent to x+x for unsigned, and for 2's complement signed integers. Compilers always know what hardware they're targeting while they're compiling, so they can take advantage of tricks like this.

On Intel Haswell, add has 4 per clock throughput, but shl with an immediate count has only 2 per clock throughput. (See http://agner.org/optimize/ for instruction tables, and other links in the x86 tag wiki). SIMD vector shifts are 1 per clock (2 in Skylake), but SIMD vector integer adds are 2 per clock (3 in Skylake). Latency is the same, though: 1 cycle.

There's also a special shift-by-one encoding of shl where the count is implicit in the opcode. 8086 didn't have immediate-count shifts, only by-one and by cl register. This is mostly relevant for right-shifts, because you can just add for left shifts unless you're shifting a memory operand. But if the value is needed later, it's better to load into a register first. But anyway, shl eax,1 or add eax,eax is one byte shorter than shl eax,10, and code-size can directly (decode / front-end bottlenecks) or indirectly (L1I code cache misses) affect performance.

More generally, small shift counts can sometimes be optimized into a scaled index in an addressing mode on x86. Most other architectures in common use these days are RISC, and don't have scaled-index addressing modes, but x86 is a common enough architecture for this to be worth mentioning. (e.g.g if you're indexing an array of 4-byte elements, there's room to increase the scale factor by 1 for int arr[]; arr[x<<1]).

---

Needing to copy+shift is common in situations where the original value of x is still needed. But most x86 integer instructions operate in-place. (The destination is one of the sources for instructions like add or shl.) The x86-64 System V calling convention passes args in registers, with the first arg in edi and return value in eax, so a function that returns x<<10 also makes the compiler emit copy+shift code.

The LEA instruction lets you shift-and-add (with a shift count of 0 to 3, because it uses addressing-mode machine-encoding). It puts the result in a separate register.

gcc and clang both optimize these functions the same way, as you can see on the Godbolt compiler explorer:

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

LEA with 2 components has 1 cycle latency and 2-per-clock throughput on recent Intel and AMD CPUs. (Sandybridge-family and Bulldozer/Ryzen). On Intel, it's only 1 per clock throughput with 3c latency for lea eax, [rdi + rsi + 123]. (Related: Why is this C++ code faster than my hand-written assembly for testing the Collatz conjecture? goes into this in detail.)

Anyway, copy+shift by 10 needs a separate mov instruction. It might be zero latency on many recent CPUs, but it still takes front-end bandwidth and code size. (Can x86's MOV really be "free"? Why can't I reproduce this at all?)

Also related: How to multiply a register by 37 using only 2 consecutive leal instructions in x86?.

---

The compiler is also free to transform the surrounding code so there isn't an actual shift, or it's combined with other operations.

For example if(x<<1) { } could use an and to check all bits except the high bit. On x86, you'd use a test instruction, like test eax, 0x7fffffff / jz .false instead of shl eax,1 / jz. This optimization works for any shift count, and it also works on machines where large-count shifts are slow (like Pentium 4), or non-existent (some micro-controllers).

Many ISAs have bit-manipulation instructions beyond just shifting. e.g. PowerPC has a lot of bit-field extract / insert instructions. Or ARM has shifts of source operands as part of any other instruction. (So shift/rotate instructions are just a special form of move, using a shifted source.)

Remember, C is not assembly language. Always look at optimized compiler output when you're tuning your source code to compile efficiently.

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