질문자 :GManNickG
다음은 매우 독특한 동작을 보여주는 C++ 코드입니다. 이상한 이유로 데이터를 정렬하면( timed 영역 이전 ) 기적적으로 루프가 거의 6배 빨라집니다.
#include <algorithm> #include <ctime> #include <iostream> int main() { // Generate data const unsigned arraySize = 32768; int data[arraySize]; for (unsigned c = 0; c < arraySize; ++c) data[c] = std::rand() % 256; // !!! With this, the next loop runs faster. std::sort(data, data + arraySize); // Test clock_t start = clock(); long long sum = 0; for (unsigned i = 0; i < 100000; ++i) { for (unsigned c = 0; c < arraySize; ++c) { // Primary loop if (data[c] >= 128) sum += data[c]; } } double elapsedTime = static_cast<double>(clock()-start) / CLOCKS_PER_SEC; std::cout << elapsedTime << '\n'; std::cout << "sum = " << sum << '\n'; }
-
std::sort(data, data + arraySize); , 코드는 11.54초에 실행됩니다. - 정렬된 데이터로 코드는 1.93초 만에 실행됩니다.
(정렬 자체는 배열을 통과하는 것보다 더 많은 시간이 걸리므로 알 수 없는 배열에 대해 이것을 계산해야 하는 경우 실제로 수행할 가치가 없습니다.)
처음에는 이것이 단지 언어 또는 컴파일러 이상일 수 있다고 생각하여 Java를 시도했습니다.
import java.util.Arrays; import java.util.Random; public class Main { public static void main(String[] args) { // Generate data int arraySize = 32768; int data[] = new int[arraySize]; Random rnd = new Random(0); for (int c = 0; c < arraySize; ++c) data[c] = rnd.nextInt() % 256; // !!! With this, the next loop runs faster Arrays.sort(data); // Test long start = System.nanoTime(); long sum = 0; for (int i = 0; i < 100000; ++i) { for (int c = 0; c < arraySize; ++c) { // Primary loop if (data[c] >= 128) sum += data[c]; } } System.out.println((System.nanoTime() - start) / 1000000000.0); System.out.println("sum = " + sum); } }
비슷하지만 덜 극단적인 결과입니다.
내 첫 번째 생각은 정렬이 데이터를 캐시 로 가져오는 것이었지만 배열이 방금 생성되었기 때문에 그것이 얼마나 어리석은 것인지 생각했습니다.
- 무슨 일이야?
- 정렬된 배열을 처리하는 것이 정렬되지 않은 배열을 처리하는 것보다 빠른 이유는 무엇입니까?
코드는 몇 가지 독립적인 용어를 요약하므로 순서는 중요하지 않습니다.
다른 / 이후 컴파일러 및 옵션을 사용한 동일한 효과에 대한 관련 / 후속 Q&A:
답변자 : Mysticial
당신은 분기 예측 실패의 희생자입니다.
분기 예측이란 무엇입니까?
철도 교차로를 고려하십시오.
Wikimedia Commons를 통한 Mecanismo의 이미지. CC-By-SA 3.0 라이선스에 따라 사용됩니다.
이제 논쟁을 위해 이것이 장거리 또는 무선 통신 이전인 1800년대로 돌아간다고 가정합니다.
당신은 교차로의 운영자이고 기차가 오는 소리를 듣습니다. 당신은 그것이 어디로 가야하는지 전혀 모릅니다. 기차를 멈추고 운전사에게 원하는 방향을 묻습니다. 그런 다음 스위치를 적절하게 설정합니다.
기차는 무겁고 관성이 많기 때문에 출발하고 감속하는 데 시간이 오래 걸립니다.
더 좋은 방법이 있습니까? 기차가 어느 방향으로 갈지 맞춰보세요!
- 추측이 맞다면 계속 진행됩니다.
- 잘못 추측하면 선장이 멈추고 물러서고 소리를 지르며 스위치를 뒤집습니다. 그런 다음 다른 경로로 다시 시작할 수 있습니다.
매번 옳다고 생각 하면 기차가 멈출 필요가 없습니다.
너무 자주 틀리면 기차가 멈추고, 후진하고, 다시 시작하는 데 많은 시간을 소비합니다.
if 문을 고려하십시오 . 프로세서 수준에서 이는 분기 명령입니다.
당신은 프로세서이고 당신은 지점을 봅니다. 어떤 방향으로 흘러갈지 알 수 없습니다. 너 뭐하니? 실행을 중지하고 이전 지침이 완료될 때까지 기다립니다. 그런 다음 올바른 경로로 계속 진행합니다.
최신 프로세서는 복잡하고 긴 파이프라인을 가지고 있습니다. 이것은 그들이 "워밍업" 및 "슬로우다운"하는 데 영원히 걸린다는 것을 의미합니다.
더 좋은 방법이 있습니까? 당신은 지점이 갈 방향을 추측합니다!
- 추측이 맞다면 계속 실행합니다.
- 잘못 추측했다면 파이프라인을 플러시하고 분기로 롤백해야 합니다. 그런 다음 다른 경로로 다시 시작할 수 있습니다.
매번 옳게 추측 하면 실행을 중단할 필요가 없습니다.
너무 자주 잘못 추측 하면 지연, 롤백 및 다시 시작하는 데 많은 시간을 소비합니다.
이것은 분기 예측입니다. 나는 기차가 깃발로 방향을 알릴 수 있기 때문에 그것이 최선의 비유가 아니라는 것을 인정합니다. 그러나 컴퓨터에서 프로세서는 마지막 순간까지 분기가 어느 방향으로 갈지 모릅니다.
기차가 후진하고 다른 경로로 내려가야 하는 횟수를 최소화하기 위해 전략적으로 어떻게 추측하시겠습니까? 당신은 과거 역사를보고! 기차가 99% 왼쪽으로 간다면 당신은 왼쪽으로 추측합니다. 그것이 번갈아 나타나면 추측을 대체합니다. 3번 1번씩 가도 똑같을듯...
즉, 패턴을 식별하고 따르려고 합니다. 이것은 분기 예측자가 작동하는 방식입니다.
대부분의 응용 프로그램에는 잘 작동하는 분기가 있습니다. 따라서 최신 분기 예측기는 일반적으로 90% 이상의 적중률을 달성합니다. 그러나 인식할 수 있는 패턴이 없는 예측할 수 없는 분기에 직면했을 때 분기 예측자는 사실상 쓸모가 없습니다.
추가 읽기: Wikipedia의 "분기 예측자" 기사 .
위에서 암시했듯이 범인은 다음과 같은 if 문입니다.
if (data[c] >= 128) sum += data[c];
데이터가 0과 255 사이에 고르게 분포되어 있음을 주목하세요. 데이터가 정렬될 때 대략 반복의 전반부는 if 문에 들어가지 않을 것입니다. 그 후, 그들은 모두 if 문을 입력합니다.
이것은 분기가 연속적으로 같은 방향으로 여러 번 가기 때문에 분기 예측자에 매우 친숙합니다. 간단한 포화 카운터조차도 방향을 전환한 후 몇 번의 반복을 제외하고 분기를 올바르게 예측합니다.
빠른 시각화:
T = branch taken N = branch not taken data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ... branch = NNNNN ... NNTTT ... TTT ... = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT (easy to predict)
그러나 데이터가 완전히 무작위인 경우 분기 예측기는 무작위 데이터를 예측할 수 없기 때문에 쓸모가 없게 됩니다. 따라서 약 50%의 잘못된 예측이 있을 수 있습니다(무작위 추측보다 나을 수 없음).
data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, ... branch = T, T, N, T, T, T, T, N, T, N, N, T, T, T ... = TTNTTTTNTNNTTT ... (completely random - impossible to predict)
무엇을 할 수 있습니까?
컴파일러가 분기를 조건부 이동으로 최적화할 수 없는 경우 성능을 위해 가독성을 희생하려는 경우 몇 가지 해킹을 시도할 수 있습니다.
바꾸다:
if (data[c] >= 128) sum += data[c];
와 함께:
int t = (data[c] - 128) >> 31; sum += ~t & data[c];
이것은 분기를 제거하고 일부 비트 연산으로 대체합니다.
(이 해킹은 원래의 if-statement와 완전히 동일하지는 않습니다. 그러나 이 경우 data[] 의 모든 입력 값에 대해 유효합니다.)
벤치마크: Core i7 920 @ 3.5GHz
C++ - Visual Studio 2010 - x64 릴리스
| 대본 | 시간(초) |
|---|
| 분기 - 랜덤 데이터 | 11.777 |
| 분기 - 정렬된 데이터 | 2.352 |
| Branchless - 랜덤 데이터 | 2.564 |
| Branchless - 정렬된 데이터 | 2.587 |
자바 - NetBeans 7.1.1 JDK 7 - x64
| 대본 | 시간(초) |
|---|
| 분기 - 랜덤 데이터 | 10.93293813 |
| 분기 - 정렬된 데이터 | 5.643797077 |
| Branchless - 랜덤 데이터 | 3.113581453 |
| Branchless - 정렬된 데이터 | 3.186068823 |
관찰:
- 분기 사용: 정렬된 데이터와 정렬되지 않은 데이터 사이에는 큰 차이가 있습니다.
- With Hack: 정렬된 데이터와 정렬되지 않은 데이터 간에 차이가 없습니다.
- C++의 경우 해킹은 실제로 데이터가 정렬될 때 분기보다 약간 느립니다.
일반적인 경험 법칙은 중요한 루프(예: 이 예)에서 데이터 종속 분기를 피하는 것입니다.
업데이트:
-O3 또는 -ftree-vectorize 하는 GCC 4.6.1은 조건부 이동을 생성할 수 있으므로 정렬된 데이터와 정렬되지 않은 데이터 간에 차이가 없습니다. 둘 다 빠릅니다.
(또는 다소 빠름: 이미 정렬된 경우, cmov 가 2주기 대기 시간을 갖는 Broadwell 이전 Intel add 대신 중요한 경로에 놓는 경우 cmov 가 느려질 수 있습니다. gcc Optimization flag -O3는 코드를 느리게 만듭니다. -O2보다 )
/Ox 에서도 이 분기에 대한 조건부 이동을 생성할 수 없습니다.
인텔 C++ 컴파일러 (ICC) 11은 놀라운 일을 합니다. 두 루프를 교환하여 예측할 수 없는 분기를 외부 루프로 끌어 올립니다. 잘못된 예측에 대한 내성이 있을 뿐만 아니라 VC++ 및 GCC가 생성할 수 있는 것보다 두 배 빠릅니다! 즉, ICC는 테스트 루프를 이용하여 벤치마크를 패배시켰습니다...
인텔 컴파일러에 분기 없는 코드를 제공하면 완전히 벡터화하고... 분기만큼 빠릅니다(루프 교환 포함).
이것은 성숙한 최신 컴파일러조차도 코드를 최적화하는 능력이 크게 다를 수 있음을 보여줍니다...
답변자 : Daniel Fischer
분기 예측.
정렬된 배열을 사용하면 data[c] >= 128 조건이 처음에는 일련의 값에 대해 false 이고 이후의 모든 값에 대해서는 true 그것은 예측하기 쉽습니다. 정렬되지 않은 배열을 사용하면 분기 비용을 지불합니다.
답변자 : WiSaGaN
데이터를 정렬할 때 성능이 크게 향상되는 이유는 Mysticial의 답변에 아름답게 설명된 것처럼 분기 예측 패널티가 제거되었기 때문입니다.
이제 코드를 보면
if (data[c] >= 128) sum += data[c];
if... else... 분기의 의미는 조건이 충족될 때 무언가를 추가하는 것임을 알 수 있습니다. 이러한 유형의 분기는 x86 시스템에서 조건부 이동 명령인 cmovl 로 컴파일되는 조건부 이동 문으로 쉽게 변환될 수 있습니다. 분기 및 이에 따른 잠재적 분기 예측 패널티가 제거됩니다.
C 에서 따라서 C++ x86 의 조건부 이동 명령으로 직접(최적화 없이) 컴파일되는 명령문은 삼항 연산자 ... ? ... : ... . 그래서 우리는 위의 문장을 동등한 문장으로 다시 작성합니다:
sum += data[c] >=128 ? data[c] : 0;
가독성을 유지하면서 속도 향상 요인을 확인할 수 있습니다.
Intel Core i7 -2600K @ 3.4GHz 및 Visual Studio 2010 릴리스 모드에서 벤치마크는 다음과 같습니다.
x86
| 대본 | 시간(초) |
|---|
| 분기 - 랜덤 데이터 | 8.885 |
| 분기 - 정렬된 데이터 | 1.528 |
| Branchless - 랜덤 데이터 | 3.716 |
| Branchless - 정렬된 데이터 | 3.71 |
x64
| 대본 | 시간(초) |
|---|
| 분기 - 랜덤 데이터 | 11.302 |
| 분기 - 정렬된 데이터 | 1.830 |
| Branchless - 랜덤 데이터 | 2.736 |
| Branchless - 정렬된 데이터 | 2.737 |
결과는 여러 테스트에서 강력합니다. 분기 결과를 예측할 수 없는 경우 속도가 크게 향상되지만 예측 가능한 경우 약간의 어려움을 겪습니다. 실제로 조건부 이동을 사용하면 데이터 패턴에 관계없이 성능이 동일합니다.
이제 그들이 생성 x86 어셈블리를 조사하여 더 자세히 살펴보겠습니다. max1 및 max2 두 가지 함수를 사용합니다.
max1 은 조건부 분기를 사용합니다. if... else ... :
int max1(int a, int b) { if (a > b) return a; else return b; }
max2 는 삼항 연산자를 사용합니다 ... ? ... : ... :
int max2(int a, int b) { return a > b ? a : b; }
x86-64 시스템에서 GCC -S 는 아래 어셈블리를 생성합니다.
:max1 movl %edi, -4(%rbp) movl %esi, -8(%rbp) movl -4(%rbp), %eax cmpl -8(%rbp), %eax jle .L2 movl -4(%rbp), %eax movl %eax, -12(%rbp) jmp .L4 .L2: movl -8(%rbp), %eax movl %eax, -12(%rbp) .L4: movl -12(%rbp), %eax leave ret :max2 movl %edi, -4(%rbp) movl %esi, -8(%rbp) movl -4(%rbp), %eax cmpl %eax, -8(%rbp) cmovge -8(%rbp), %eax leave ret
max2 cmovge 사용으로 인해 훨씬 적은 코드를 사용합니다. 그러나 실제 이득은 max2 가 분기 점프( jmp )를 포함하지 않는다는 것입니다. 이는 예측된 결과가 옳지 않을 경우 상당한 성능 저하를 초래할 것입니다.
그렇다면 조건부 이동이 더 잘 수행되는 이유는 무엇입니까?
일반적인 x86 프로세서에서 명령어 실행은 여러 단계로 나뉩니다. 대략, 우리는 다른 단계를 처리하기 위해 다른 하드웨어를 가지고 있습니다. 따라서 새 명령을 시작하기 위해 하나의 명령이 완료될 때까지 기다릴 필요가 없습니다. 이것을 파이프라이닝 이라고 합니다.
분기의 경우 다음 명령은 이전 명령에 의해 결정되므로 파이프라이닝을 수행할 수 없습니다. 기다리거나 예측해야 합니다.
조건부 이동의 경우 실행 조건부 이동 명령은 여러 단계로 나뉘지만 Fetch 및 Decode 와 같은 이전 단계는 이전 명령의 결과에 의존하지 않습니다. 후기 단계에서만 결과가 필요합니다. 따라서 우리는 한 명령어의 실행 시간의 일부를 기다립니다. 예측이 쉬울 때 조건부 이동 버전이 분기보다 느린 이유입니다.
Computer Systems: A Programmer's Perspective, 2판에서는 이에 대해 자세히 설명합니다. 조건부 이동 명령에 대해서는 섹션 3.6.6 , 프로세서 아키텍처에 대한 전체 4장 , 분기 예측 및 오예측 페널티에 대한 특별 처리에 대해서는 섹션 5.11.2를 확인할 수 있습니다.
때때로 일부 최신 컴파일러는 더 나은 성능으로 어셈블리에 대한 코드를 최적화할 수 있지만 일부 컴파일러는 그렇지 않을 수 있습니다(문제의 코드는 Visual Studio의 기본 컴파일러를 사용함). 예측할 수 없을 때 분기와 조건부 이동 간의 성능 차이를 알면 시나리오가 너무 복잡해져서 컴파일러가 자동으로 최적화할 수 없을 때 더 나은 성능으로 코드를 작성하는 데 도움이 될 수 있습니다.
답변자 : vulcan raven
이 코드에 대해 수행할 수 있는 더 많은 최적화가 궁금하다면 다음을 고려하십시오.
원래 루프로 시작:
for (unsigned i = 0; i < 100000; ++i) { for (unsigned j = 0; j < arraySize; ++j) { if (data[j] >= 128) sum += data[j]; } }
루프 교환을 사용하면 이 루프를 다음과 같이 안전하게 변경할 수 있습니다.
for (unsigned j = 0; j < arraySize; ++j) { for (unsigned i = 0; i < 100000; ++i) { if (data[j] >= 128) sum += data[j]; } }
if i 루프를 실행하는 동안 일정하다는 것을 if out을 호이스트할 수 있습니다.
for (unsigned j = 0; j < arraySize; ++j) { if (data[j] >= 128) { for (unsigned i = 0; i < 100000; ++i) { sum += data[j]; } } }
그런 다음 부동 소수점 모델이 허용한다고 가정하면 내부 루프가 하나의 단일 표현식으로 축소될 수 있음을 알 수 있습니다( /fp:fast 가 throw됨).
for (unsigned j = 0; j < arraySize; ++j) { if (data[j] >= 128) { sum += data[j] * 100000; } }
이는 이전보다 100,000배 더 빠릅니다.
답변자 : caf
의심할 여지 없이 우리 중 일부는 CPU의 분기 예측기에 문제가 있는 코드를 식별하는 방법에 관심이 있을 것입니다. Valgrind 도구 cachegrind --branch-sim=yes 플래그를 사용하여 활성화된 분기 예측기 시뮬레이터가 있습니다. 외부 루프의 수를 10000으로 줄이고 g++ 컴파일하여 이 질문의 예제를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
정렬됨:
==32551== Branches: 656,645,130 ( 656,609,208 cond + 35,922 ind) ==32551== Mispredicts: 169,556 ( 169,095 cond + 461 ind) ==32551== Mispred rate: 0.0% ( 0.0% + 1.2% )
정렬되지 않음:
==32555== Branches: 655,996,082 ( 655,960,160 cond + 35,922 ind) ==32555== Mispredicts: 164,073,152 ( 164,072,692 cond + 460 ind) ==32555== Mispred rate: 25.0% ( 25.0% + 1.2% )
cg_annotate 의해 생성된 라인별 출력으로 드릴다운하면 문제의 루프에 대해 볼 수 있습니다.
정렬됨:
Bc Bcm Bi Bim 10,001 4 0 0 for (unsigned i = 0; i < 10000; ++i) . . . . { . . . . // primary loop 327,690,000 10,016 0 0 for (unsigned c = 0; c < arraySize; ++c) . . . . { 327,680,000 10,006 0 0 if (data[c] >= 128) 0 0 0 0 sum += data[c]; . . . . } . . . . }
정렬되지 않음:
Bc Bcm Bi Bim 10,001 4 0 0 for (unsigned i = 0; i < 10000; ++i) . . . . { . . . . // primary loop 327,690,000 10,038 0 0 for (unsigned c = 0; c < arraySize; ++c) . . . . { 327,680,000 164,050,007 0 0 if (data[c] >= 128) 0 0 0 0 sum += data[c]; . . . . } . . . . }
이것은 당신이 쉽게 문제가있는 라인을 식별 할 수 있습니다 - 정렬되지 않은 버전의 if (data[c] >= 128) 라인은 164,050,007 잘못 예측 조건 분기 (일으키는 Bcm 그것은 단지 정렬 된 버전에서 10,006을 일으키는 반면, cachegrind의 지사 예측 모델에서)를 .
또는 Linux에서 성능 카운터 하위 시스템을 사용하여 동일한 작업을 수행할 수 있지만 기본 성능은 CPU 카운터를 사용합니다.
perf stat ./sumtest_sorted
정렬됨:
Performance counter stats for './sumtest_sorted': 11808.095776 task-clock # 0.998 CPUs utilized 1,062 context-switches # 0.090 K/sec 14 CPU-migrations # 0.001 K/sec 337 page-faults # 0.029 K/sec 26,487,882,764 cycles # 2.243 GHz 41,025,654,322 instructions # 1.55 insns per cycle 6,558,871,379 branches # 555.455 M/sec 567,204 branch-misses # 0.01% of all branches 11.827228330 seconds time elapsed
정렬되지 않음:
Performance counter stats for './sumtest_unsorted': 28877.954344 task-clock # 0.998 CPUs utilized 2,584 context-switches # 0.089 K/sec 18 CPU-migrations # 0.001 K/sec 335 page-faults # 0.012 K/sec 65,076,127,595 cycles # 2.253 GHz 41,032,528,741 instructions # 0.63 insns per cycle 6,560,579,013 branches # 227.183 M/sec 1,646,394,749 branch-misses # 25.10% of all branches 28.935500947 seconds time elapsed
또한 디스어셈블리로 소스 코드 주석을 수행할 수도 있습니다.
perf record -e branch-misses ./sumtest_unsorted perf annotate -d sumtest_unsorted
Percent | Source code & Disassembly of sumtest_unsorted ------------------------------------------------ ... : sum += data[c]; 0.00 : 400a1a: mov -0x14(%rbp),%eax 39.97 : 400a1d: mov %eax,%eax 5.31 : 400a1f: mov -0x20040(%rbp,%rax,4),%eax 4.60 : 400a26: cltq 0.00 : 400a28: add %rax,-0x30(%rbp) ...
자세한 내용 은 성능 자습서 를 참조하세요.
답변자 : atlaste
방금 이 질문과 답변을 읽었으며 답변이 누락된 것 같습니다.
관리 언어에서 특히 잘 작동하는 것으로 확인된 분기 예측을 제거하는 일반적인 방법은 분기를 사용하는 대신 테이블 조회입니다(이 경우 테스트하지는 않았지만).
이 접근 방식은 일반적으로 다음과 같은 경우에 작동합니다.
- 작은 테이블이고 프로세서에 캐시될 가능성이 높으며
- 매우 빡빡한 루프에서 작업을 실행하고 있거나 프로세서가 데이터를 미리 로드할 수 있습니다.
배경과 이유
프로세서 관점에서 보면 메모리가 느립니다. 속도 차이를 보상하기 위해 몇 개의 캐시가 프로세서(L1/L2 캐시)에 내장되어 있습니다. 그래서 당신이 당신의 멋진 계산을 하고 있다고 상상하고 당신에게 메모리 조각이 필요하다는 것을 알아내십시오. 프로세서는 '로드' 작업을 수행하고 메모리 조각을 캐시에 로드한 다음 캐시를 사용하여 나머지 계산을 수행합니다. 메모리가 상대적으로 느리기 때문에 이 '로드'는 프로그램을 느리게 합니다.
분기 예측과 마찬가지로 이것은 Pentium 프로세서에서 최적화되었습니다. 프로세서는 데이터 조각을 로드해야 한다고 예측하고 작업이 실제로 캐시에 도달하기 전에 이를 캐시에 로드하려고 시도합니다. 우리가 이미 보았듯이 분기 예측은 때때로 끔찍하게 잘못됩니다. 최악의 시나리오에서는 돌아가서 실제로 메모리 로드를 기다려야 하며, 이는 영원히 걸릴 것입니다( 즉: 분기 예측 실패는 나쁘고, 분기 예측 실패 후 로드는 끔찍합니다! ).
다행스럽게도 메모리 액세스 패턴을 예측할 수 있는 경우 프로세서는 이를 빠른 캐시에 로드하고 모든 것이 정상입니다.
가장 먼저 알아야 할 것은 작은 것이 무엇입니까? 일반적으로 작을수록 좋지만 크기가 <= 4096바이트인 조회 테이블을 고수하는 것이 일반적입니다. 상한선: 조회 테이블이 64K보다 큰 경우 재고할 가치가 있습니다.
테이블 구성
그래서 우리는 작은 테이블을 만들 수 있다는 것을 알아냈습니다. 다음으로 할 일은 조회 기능을 제자리에 두는 것입니다. 조회 함수는 일반적으로 몇 가지 기본 정수 연산(및, 또는, xor, 시프트, 더하기, 제거 및 곱하기)을 사용하는 작은 함수입니다. 조회 기능에 의해 입력이 테이블의 일종의 '고유 키'로 변환되기를 원합니다. 그러면 원하는 모든 작업에 대한 답변이 제공됩니다.
이 경우 >= 128은 값을 유지할 수 있음을 의미하고 < 128은 값을 제거함을 의미합니다. 가장 쉬운 방법은 'AND'를 사용하는 것입니다. 유지하면 7FFFFFFF로 AND를 사용합니다. 그것을 없애고 싶다면 0과 AND를 사용합니다. 또한 128은 2의 거듭제곱이라는 점에 유의하세요. 따라서 32768/128 정수 테이블을 만들고 하나의 0과 많은 수로 채울 수 있습니다. 7FFFFFFFF.
관리 언어
이것이 관리 언어에서 잘 작동하는 이유가 궁금할 것입니다. 결국 관리 언어는 배열의 경계를 분기로 확인하여 엉망이 되지 않도록 합니다...
음, 정확히는... :-)
관리되는 언어에 대해 이 분기를 제거하는 작업이 꽤 있었습니다. 예를 들어:
for (int i = 0; i < array.Length; ++i) { // Use array[i] }
이 경우 컴파일러는 경계 조건이 결코 적중하지 않을 것이 분명합니다. 최소한 Microsoft JIT 컴파일러(Java가 유사한 작업을 수행할 것으로 예상함)가 이를 알아차리고 검사를 완전히 제거합니다. 와우, 그것은 지점이 없다는 것을 의미합니다. 마찬가지로, 다른 명백한 경우를 다룰 것입니다.
관리 언어로 조회하는 데 문제가 있는 경우 -- 핵심은 & 0x[something]FFF 를 추가하여 경계 검사를 예측 가능하게 만들고 더 빠르게 진행하는 것을 지켜보는 것입니다.
이 사건의 결과
// Generate data int arraySize = 32768; int[] data = new int[arraySize]; Random random = new Random(0); for (int c = 0; c < arraySize; ++c) { data[c] = random.Next(256); } /*To keep the spirit of the code intact, I'll make a separate lookup table (I assume we cannot modify 'data' or the number of loops)*/ int[] lookup = new int[256]; for (int c = 0; c < 256; ++c) { lookup[c] = (c >= 128) ? c : 0; } // Test DateTime startTime = System.DateTime.Now; long sum = 0; for (int i = 0; i < 100000; ++i) { // Primary loop for (int j = 0; j < arraySize; ++j) { /* Here you basically want to use simple operations - so no random branches, but things like &, |, *, -, +, etc. are fine. */ sum += lookup[data[j]]; } } DateTime endTime = System.DateTime.Now; Console.WriteLine(endTime - startTime); Console.WriteLine("sum = " + sum); Console.ReadLine();
답변자 : Saqlain
데이터가 0과 255 사이에 분산되기 때문에 어레이가 정렬되는 경우, 반복의 전반부가 입력되지 주위 if -statement을합니다 ( if 문 아래 공유된다).
if (data[c] >= 128) sum += data[c];
질문: 정렬된 데이터의 경우와 같이 특정 경우에 위의 명령문이 실행되지 않는 이유는 무엇입니까? 여기에 "분기 예측자"가 있습니다. 분기 예측기는 이것이 확실히 알려지기 전에 if-then-else 구조)가 어떤 방향으로 갈 것인지 추측하려고 시도하는 디지털 회로입니다. 분기 예측기의 목적은 명령 파이프라인의 흐름을 개선하는 것입니다. 분기 예측자는 높은 효과적인 성능을 달성하는 데 중요한 역할을 합니다!
더 잘 이해하기 위해 벤치마킹을 해보자
if 문의 성능은 해당 조건에 예측 가능한 패턴이 있는지 여부에 따라 다릅니다. 조건이 항상 참이거나 항상 거짓이면 프로세서의 분기 예측 논리가 패턴을 선택합니다. 반면에 패턴을 예측할 수 없는 if 문이 훨씬 더 비쌉니다.
다양한 조건으로 이 루프의 성능을 측정해 보겠습니다.
for (int i = 0; i < max; i++) if (condition) sum++;
다음은 참-거짓 패턴이 서로 다른 루프의 타이밍입니다.
Condition Pattern Time (ms) ------------------------------------------------------- (i & 0×80000000) == 0 T repeated 322 (i & 0xffffffff) == 0 F repeated 276 (i & 1) == 0 TF alternating 760 (i & 3) == 0 TFFFTFFF… 513 (i & 2) == 0 TTFFTTFF… 1675 (i & 4) == 0 TTTTFFFFTTTTFFFF… 1275 (i & 8) == 0 8T 8F 8T 8F … 752 (i & 16) == 0 16T 16F 16T 16F … 490
" 나쁜 " 참-거짓 패턴은 "좋은 " 패턴보다 최대 6배 느리게 if 물론 어떤 패턴이 좋고 어떤 것이 나쁜지는 컴파일러와 특정 프로세서에서 생성한 정확한 명령어에 따라 다릅니다.
따라서 분기 예측이 성능에 미치는 영향에 대해서는 의심의 여지가 없습니다!
답변자 : steveha
분기 예측 오류를 방지하는 한 가지 방법은 조회 테이블을 만들고 데이터를 사용하여 색인을 생성하는 것입니다. Stefan de Bruijn은 그의 답변에서 이에 대해 논의했습니다.
그러나 이 경우에 우리는 값이 [0, 255] 범위에 있다는 것을 알고 있으며 값 >= 128에만 관심이 있습니다. 즉, 값을 원하는지 여부를 알려주는 단일 비트를 쉽게 추출할 수 있습니다. 데이터를 오른쪽 7비트로 이동하면 0비트 또는 1비트가 남고 1비트가 있을 때만 값을 추가하려고 합니다. 이 비트를 "결정 비트"라고 합시다.
결정 비트의 0/1 값을 배열에 대한 인덱스로 사용하여 데이터가 정렬되었는지 여부에 관계없이 똑같이 빠른 코드를 만들 수 있습니다. 우리 코드는 항상 값을 추가하지만 결정 비트가 0이면 신경 쓰지 않는 곳에 값을 추가합니다. 코드는 다음과 같습니다.
// Test clock_t start = clock(); long long a[] = {0, 0}; long long sum; for (unsigned i = 0; i < 100000; ++i) { // Primary loop for (unsigned c = 0; c < arraySize; ++c) { int j = (data[c] >> 7); a[j] += data[c]; } } double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC; sum = a[1];
이 코드는 추가의 절반을 낭비하지만 분기 예측 실패는 없습니다. 실제 if 문이 있는 버전보다 무작위 데이터에서 엄청나게 빠릅니다.
그러나 내 테스트에서 명시적 룩업 테이블은 이것보다 약간 더 빨랐습니다. 아마도 룩업 테이블에 대한 인덱싱이 비트 시프팅보다 약간 더 빨랐기 때문일 것입니다. 이것은 내 코드가 조회 테이블을 설정하고 사용하는 방법을 보여줍니다(코드에서 "LookUp Table"에 대해 lut 다음은 C++ 코드입니다.
// Declare and then fill in the lookup table int lut[256]; for (unsigned c = 0; c < 256; ++c) lut[c] = (c >= 128) ? c : 0; // Use the lookup table after it is built for (unsigned i = 0; i < 100000; ++i) { // Primary loop for (unsigned c = 0; c < arraySize; ++c) { sum += lut[data[c]]; } }
이 경우 조회 테이블은 256바이트에 불과하므로 캐시에 잘 맞고 모두 빠릅니다. 이 기술은 데이터가 24비트 값이고 그 중 절반만 원하면 제대로 작동하지 않습니다. 조회 테이블은 너무 커서 실용적이지 않습니다. 반면에 위에 표시된 두 가지 기술을 결합할 수 있습니다. 먼저 비트를 위로 이동한 다음 조회 테이블을 인덱싱합니다. 상위 절반 값만 원하는 24비트 값의 경우 잠재적으로 데이터를 오른쪽으로 12비트 이동하고 테이블 인덱스에 대해 12비트 값을 남길 수 있습니다. 12비트 테이블 인덱스는 4096개의 값으로 구성된 테이블을 의미하므로 실용적일 수 있습니다.
if 문을 사용하는 대신 배열로 인덱싱하는 기술을 사용하여 사용할 포인터를 결정할 수 있습니다. 이진 트리를 구현한 라이브러리를 보았고 두 개의 명명된 포인터( pLeft 및 pRight )를 사용하는 대신 길이가 2인 포인터 배열을 갖고 "결정 비트" 기술을 사용하여 따를 것을 결정했습니다. 예를 들어 다음 대신:
if (x < node->value) node = node->pLeft; else node = node->pRight;
이 라이브러리는 다음과 같은 작업을 수행합니다.
i = (x < node->value); node = node->link[i];
이 코드에 대한 링크는 다음과 같습니다. Red Black Trees , Eternally Confuzzled
답변자 : Yves Daoust
정렬된 경우 성공적인 분기 예측이나 분기 없는 비교 트릭에 의존하는 것보다 더 잘할 수 있습니다. 분기를 완전히 제거하십시오.
data < 128 연속 영역과 data >= 128 연속 영역에서 분할됩니다. 따라서 이분법 검색 ( Lg(arraySize) = 15 비교 사용)으로 파티션 지점을 찾은 다음 해당 지점에서 직선 누적을 수행해야 합니다.
다음과 같은 것(선택하지 않음)
int i= 0, j, k= arraySize; while (i < k) { j= (i + k) >> 1; if (data[j] >= 128) k= j; else i= j; } sum= 0; for (; i < arraySize; i++) sum+= data[i];
또는, 약간 더 난독화
int i, k, j= (i + k) >> 1; for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j) j= (i + k) >> 1; for (sum= 0; i < arraySize; i++) sum+= data[i];
정렬되거나 정렬되지 않은 경우 모두에 대한 대략적인 솔루션을 제공하는 더 빠른 접근 방식 sum= 3137536; (진정으로 균일한 분포를 가정하면 예상 값이 191.5인 16384개의 샘플) :-)
답변자 : Harsh Sharma
위의 동작은 분기 예측으로 인해 발생합니다.
분기 예측을 이해하려면 먼저 명령 파이프라인을 이해해야 합니다.
모든 명령은 여러 단계를 동시에 병렬로 실행할 수 있도록 일련의 단계로 나뉩니다. 이 기술을 명령 파이프라인이라고 하며 최신 프로세서에서 처리량을 높이는 데 사용됩니다. 이것을 더 잘 이해하려면 Wikipedia에서 이 예를 참조하십시오.
일반적으로 최신 프로세서는 파이프라인이 상당히 길지만 편의를 위해 이 4단계만 고려하겠습니다.
- IF -- 메모리에서 명령어 가져오기
- ID -- 명령어 디코딩
- EX -- 명령어 실행
- WB -- CPU 레지스터에 다시 쓰기
일반적으로 2개의 명령어를 위한 4단계 파이프라인. 
위의 질문으로 돌아가서 다음 지침을 고려해 보겠습니다.
A) if (data[c] >= 128) /\ / \ / \ true / \ false / \ / \ / \ / \ B) sum += data[c]; C) for loop or print().
분기 예측이 없으면 다음이 발생합니다.
명령어 B 또는 명령어 C를 실행하기 위해 프로세서는 명령어 B 또는 명령어 C로의 결정이 명령어 A의 결과에 따라 달라지기 때문에 명령어 A가 파이프라인의 EX 단계까지 도달하지 않을 때까지 기다려야 합니다. 따라서 파이프라인 이렇게 보일 것입니다.
조건이 true를 반환할 때:
if 조건이 false를 반환하는 경우:
명령어 A의 결과를 기다린 결과, 위의 경우(분기 예측 없이, 참과 거짓 모두에 대해) 소비된 총 CPU 사이클은 7입니다.
그렇다면 분기 예측이란 무엇입니까?
분기 예측기는 이것이 확실히 알려지기 전에 분기(if-then-else 구조)가 어떤 방향으로 갈 것인지 추측하려고 시도합니다. 명령 A가 파이프라인의 EX 단계에 도달할 때까지 기다리지 않지만 결정을 추측하고 해당 명령(이 예의 경우 B 또는 C)으로 이동합니다.
정확한 추측의 경우 파이프라인은 다음과 같습니다.
나중에 추측이 잘못된 것으로 감지되면 부분적으로 실행된 명령이 삭제되고 파이프라인이 올바른 분기로 다시 시작되어 지연이 발생합니다. 분기 예측이 잘못된 경우 낭비되는 시간은 가져오기 단계에서 실행 단계까지 파이프라인의 단계 수와 같습니다. 최신 마이크로프로세서는 파이프라인이 상당히 긴 경향이 있어 오예측 지연이 10~20 클록 사이클 사이에 있습니다. 파이프라인이 길수록 좋은 분기 예측자가 필요합니다.
OP의 코드에서 처음 조건부 분기 예측자는 예측을 기반으로 하는 정보가 없으므로 처음에는 무작위로 다음 명령어를 선택합니다. 나중에 for 루프에서 히스토리를 기반으로 예측할 수 있습니다. 오름차순으로 정렬된 배열의 경우 세 가지 가능성이 있습니다.
- 모든 요소가 128보다 작습니다.
- 모든 요소가 128보다 큽니다.
- 일부 시작 새 요소는 128보다 작으며 나중에는 128보다 커집니다.
예측자가 항상 첫 번째 실행에서 실제 분기를 가정한다고 가정해 보겠습니다.
따라서 첫 번째 경우에는 역사적으로 모든 예측이 정확하기 때문에 항상 참 분기를 사용합니다. 두 번째 경우에는 처음에는 잘못 예측하지만 몇 번 반복하면 올바르게 예측합니다. 세 번째 경우에는 요소가 128보다 작을 때까지 처음에 올바르게 예측합니다. 그 후 한동안 실패하고 기록에서 분기 예측 실패를 볼 때 자체적으로 수정됩니다.
이 모든 경우에 실패 횟수가 너무 적어 결과적으로 부분적으로 실행된 명령을 버리고 올바른 분기로 다시 시작해야 하는 경우가 몇 번뿐이므로 CPU 주기가 줄어듭니다.
그러나 무작위 정렬되지 않은 배열의 경우 예측은 부분적으로 실행된 명령을 버리고 대부분의 시간에 올바른 분기로 다시 시작해야 하며 결과적으로 정렬된 배열에 비해 더 많은 CPU 주기가 발생합니다.
답변자 : Surt
공식 답변은
- 인텔 - 지점의 잘못된 예측으로 인한 비용 방지
- 인텔 - 잘못된 예측을 방지하기 위한 분기 및 루프 재구성
- 과학 논문 - 분기 예측 컴퓨터 아키텍처
- 저서: JL Hennessy, DA Patterson: 컴퓨터 아키텍처: 정량적 접근
- 과학 출판물에 있는 기사: TY Yeh, YN Patt는 분기 예측에 대해 많은 것을 했습니다.
또한 이 멋진 다이어그램 에서 분기 예측기가 혼동되는 이유를 알 수 있습니다.
원본 코드의 각 요소는 임의의 값입니다.
data[c] = std::rand() % 256;
따라서 예측자는 std::rand() 타격으로 측면을 변경합니다.
반면에, 일단 정렬되면 예측자는 먼저 강력하게 채택되지 않은 상태로 이동하고 값이 높은 값으로 변경되면 예측자는 강력하게 채택되지 않음에서 강력하게 채택됨으로 3회에 걸쳐 변경됩니다.
답변자 : rkachach
같은 줄에서(나는 이것이 어떤 대답으로도 강조되지 않았다고 생각한다) 때때로(특히 Linux 커널과 같이 성능이 중요한 소프트웨어에서) 다음과 같은 if 문을 찾을 수 있다는 점을 언급하는 것이 좋습니다.
if (likely( everything_is_ok )) { /* Do something */ }
또는 유사하게:
if (unlikely(very_improbable_condition)) { /* Do something */ }
likely() 및 unlikely() __builtin_expect 와 같은 것을 사용하여 정의된 매크로로, 컴파일러가 사용자가 제공한 정보를 고려하여 조건을 선호하도록 예측 코드를 삽입하는 데 도움이 됩니다. GCC는 실행 중인 프로그램의 동작을 변경하거나 캐시 지우기와 같은 저수준 명령을 내보낼 수 있는 다른 내장 기능을 지원합니다. 사용 가능한 GCC 내장 기능을 살펴보는 이 문서를 참조하십시오.
일반적으로 이러한 종류의 최적화는 실행 시간이 중요하고 중요한 실시간 응용 프로그램이나 임베디드 시스템에서 주로 볼 수 있습니다. 예를 들어, 1/10000000번만 발생하는 일부 오류 조건을 확인하는 경우 컴파일러에 이를 알리지 않겠습니까? 이렇게 하면 기본적으로 분기 예측에서 조건이 거짓이라고 가정합니다.
답변자 : Maciej
C++에서 자주 사용되는 부울 연산은 컴파일된 프로그램에서 많은 분기를 생성합니다. 이러한 분기가 루프 내부에 있고 예측하기 어려운 경우 실행 속도가 크게 느려질 수 있습니다. 부울 변수 값에 8 비트 정수로 저장되어 0 에 대한 false 및 1 에 대한 true .
부울 변수는 입력으로 부울 변수를 사용하는 모든 연산자가 입력에 0 또는 1 0 또는 1 이외의 다른 값을 생성할 수 없다는 점에서 과도하게 결정됩니다. 이로 인해 부울 변수를 입력으로 사용하는 작업이 필요한 것보다 덜 효율적입니다. 예를 들면 다음과 같습니다.
bool a, b, c, d; c = a && b; d = a || b;
이것은 일반적으로 다음과 같은 방식으로 컴파일러에 의해 구현됩니다.
bool a, b, c, d; if (a != 0) { if (b != 0) { c = 1; } else { goto CFALSE; } } else { CFALSE: c = 0; } if (a == 0) { if (b == 0) { d = 0; } else { goto DTRUE; } } else { DTRUE: d = 1; }
이 코드는 최적이 아닙니다. 잘못된 예측의 경우 분기에 시간이 오래 걸릴 수 있습니다. 0 및 1 이외의 다른 값을 갖지 않는다는 것을 확실히 알고 있으면 훨씬 더 효율적으로 만들 수 있습니다. 컴파일러가 이러한 가정을 하지 않는 이유는 변수가 초기화되지 않았거나 알 수 없는 소스에서 온 경우 다른 값을 가질 수 있기 때문입니다. 위의 코드를 최적화 할 수있는 경우 와 a b 유효한 값으로 초기화 된 또는 사업자로부터 온 경우 부울 출력을 생성하는 것이다. 최적화된 코드는 다음과 같습니다.
char a = 0, b = 1, c, d; c = a & b; d = a | b;
부울 연산자( && 및 || ) & 및 | )를 사용할 수 있도록 하기 위해 bool 대신 char 비트 연산자는 하나의 클럭 사이클만 사용하는 단일 명령어입니다. OR 연산자( | a 와 b 값이 0 또는 1 아닌 경우에도 작동합니다. AND 연산자( & )와 EXCLUSIVE OR 연산자( ^ 0 과 1 아닌 경우 일치하지 않는 결과를 제공할 수 있습니다.
~ 는 NOT에 사용할 수 없습니다. 대신 것으로 알려져 변수에 부울 NOT을 할 수 0 또는 1 함께 XOR'ing에 의해 1 :
bool a, b; b = !a;
다음과 같이 최적화할 수 있습니다.
char a = 0, b; b = a ^ 1;
a && b 로 대체 될 수 a & b 만약 b 있는 경우 평가되어서는 안된다 식이고 a 이고 false ( && 평가되지 b , & 것이다). 마찬가지로 a || b a | b 로 바꿀 수 없습니다. a | b if b a 가 true 평가되어서는 안 되는 표현식입니다.
피연산자가 비교인 경우보다 피연산자가 변수인 경우 비트 연산자를 사용하는 것이 더 유리합니다.
bool a; double x, y, z; a = x > y && z < 5.0;
대부분의 경우에 최적입니다( && 식이 많은 분기 오예측을 생성할 것으로 예상하지 않는 한).
답변자 : Alireza
그건 확실합니다!...
분기 예측 은 코드에서 발생하는 전환 때문에 논리 실행을 느리게 만듭니다! 직선거리나 회전이 많은 거리로 가는 것과 같습니다. 확실히 직선거리가 더 빨리 끝날 것입니다!...
배열이 정렬되면 첫 번째 단계에서 조건이 거짓( data[c] >= 128 )이 되고 거리 끝까지 가는 동안 참 값이 됩니다. 그래야 논리의 끝 부분에 더 빨리 도달할 수 있습니다. 반면에 정렬되지 않은 배열을 사용하면 코드를 느리게 실행하는 많은 회전과 처리가 필요합니다...
아래에서 내가 만든 이미지를 보십시오. 어느 거리가 더 빨리 완성될까요?
따라서 프로그래밍 방식으로 분기 예측으로 인해 프로세스가 느려집니다...
또한 마지막에는 코드에 서로 다른 영향을 미칠 두 가지 종류의 분기 예측이 있다는 것을 아는 것이 좋습니다.
1. 정적
2. 다이나믹
정적 분기 예측은 조건 분기가 처음 발생할 때 마이크로프로세서에서 사용되며 동적 분기 예측은 조건 분기 코드의 후속 실행에 사용됩니다.
이러한 규칙을 활용하는 코드를 효과적으로 작성 하려면 if-else 또는 switch 문을 작성할 때 가장 일반적인 경우를 먼저 확인하고 가장 일반적이지 않은 것까지 점진적으로 작업하십시오. 루프 반복기의 조건만 일반적으로 사용되기 때문에 루프는 정적 분기 예측을 위한 특별한 코드 순서를 필요로 하지 않습니다.
답변자 : ForeverLearning
이 질문은 이미 여러 번 훌륭하게 답변되었습니다. 그래도 나는 또 다른 흥미로운 분석에 대해 그룹의 관심을 끌고 싶습니다.
최근에 이 예제(매우 약간 수정됨)는 Windows에서 프로그램 자체 내에서 코드 조각을 프로파일링하는 방법을 보여주는 방법으로도 사용되었습니다. 그 과정에서 저자는 정렬된 경우와 정렬되지 않은 경우 모두에서 코드가 대부분의 시간을 소비하는 위치를 결정하기 위해 결과를 사용하는 방법도 보여줍니다. 마지막으로 이 조각은 HAL(Hardware Abstraction Layer)의 잘 알려지지 않은 기능을 사용하여 정렬되지 않은 경우에 분기 오류가 얼마나 많이 발생하는지 확인하는 방법도 보여줍니다.
링크는 다음과 같습니다. 자가 프로파일링 시연
답변자 : Eugene
다른 사람들이 이미 언급했듯이 신비 뒤에는 Branch Predictor가 있습니다.
나는 무언가를 추가하려고하는 것이 아니라 다른 방식으로 개념을 설명합니다. 위키에는 텍스트와 도표가 포함된 간략한 소개가 있습니다. 나는 직관적으로 Branch Predictor를 정교화하기 위해 다이어그램을 사용하는 아래의 설명을 좋아합니다.
컴퓨터 아키텍처에서 분기 예측기는 분기(예: if-then-else 구조)가 확실히 알려지기 전에 어떤 방향으로 갈 것인지 추측하려고 시도하는 디지털 회로입니다. 분기 예측기의 목적은 명령 파이프라인의 흐름을 개선하는 것입니다. 분기 예측기는 x86과 같은 많은 최신 파이프라인 마이크로프로세서 아키텍처에서 고효율 성능을 달성하는 데 중요한 역할을 합니다.
양방향 분기는 일반적으로 조건부 점프 명령으로 구현됩니다. 조건부 점프는 "취하지 않음"이고 조건부 점프 직후에 오는 코드의 첫 번째 분기로 계속 실행하거나 "가져가" 코드의 두 번째 분기가 있는 프로그램 메모리의 다른 위치로 점프할 수 있습니다. 저장. 조건이 계산되고 조건부 점프가 명령 파이프라인의 실행 단계를 통과할 때까지 조건부 점프가 수행되는지 여부는 확실하지 않습니다(그림 1 참조).
설명된 시나리오를 기반으로 다양한 상황에서 파이프라인에서 명령이 실행되는 방식을 보여주는 애니메이션 데모를 작성했습니다.
- 분기 예측기 없이.
분기 예측이 없으면 프로세서는 조건부 점프 명령이 실행 단계를 통과할 때까지 기다려야 다음 명령이 파이프라인의 페치 단계에 들어갈 수 있습니다.
예제에는 세 개의 명령어가 포함되어 있으며 첫 번째는 조건부 점프 명령어입니다. 후자의 두 명령어는 조건부 점프 명령어가 실행될 때까지 파이프라인으로 들어갈 수 있습니다.
3개의 명령어가 완료되려면 9개의 클럭 사이클이 필요합니다.
- 분기 예측기를 사용하고 조건부 점프를 사용하지 마십시오. 예측이 조건부 점프를 하지 않는다고 가정해 봅시다.
3개의 명령어가 완료되려면 7개의 클럭 사이클이 필요합니다.
- 분기 예측기를 사용하고 조건부 점프를 합니다. 예측이 조건부 점프를 하지 않는다고 가정해 봅시다.
3개의 명령어가 완료되려면 9개의 클럭 사이클이 필요합니다.
분기 예측이 잘못된 경우 낭비되는 시간은 가져오기 단계에서 실행 단계까지 파이프라인의 단계 수와 같습니다. 최신 마이크로프로세서는 파이프라인이 상당히 긴 경향이 있어 오예측 지연이 10~20 클록 사이클 사이에 있습니다. 결과적으로 파이프라인을 더 길게 만들면 고급 분기 예측기가 필요하게 됩니다.
보시다시피 Branch Predictor를 사용하지 않을 이유가 없습니다.
Branch Predictor의 가장 기본적인 부분을 명확히 하는 아주 간단한 데모입니다. 이러한 gif가 귀찮다면 답변에서 자유롭게 제거하십시오. 방문자는 BranchPredictorDemo에서 라이브 데모 소스 코드를 얻을 수도 있습니다.
답변자 : Tony Tannous
분기 예측 이득!
분기 예측이 프로그램 속도를 늦추지 않는다는 점을 이해하는 것이 중요합니다. 누락된 예측의 비용은 분기 예측이 존재하지 않고 실행할 코드를 결정하기 위해 표현식의 평가를 기다렸던 것과 같습니다(다음 단락에서 추가 설명).
if (expression) { // Run 1 } else { // Run 2 }
if-else \ switch 문이 있을 때마다 표현식을 평가하여 실행해야 하는 블록을 결정해야 합니다. 컴파일러에서 생성된 어셈블리 코드에는 조건 분기 명령이 삽입됩니다.
분기 명령은 컴퓨터가 다른 명령 시퀀스를 실행하기 시작하도록 하여 어떤 조건에 따라 명령을 순서대로 실행하는 기본 동작에서 벗어날 수 있습니다(즉, 표현식이 거짓이면 프로그램은 if 블록의 코드를 건너뜁니다). 우리의 경우 표현 평가입니다.
즉, 컴파일러는 실제로 평가되기 전에 결과를 예측하려고 합니다. if 블록에서 명령을 가져오고 표현식이 사실로 판명되면 훌륭합니다! 우리는 그것을 평가하는 데 걸리는 시간을 얻었고 코드에서 진전을 이루었습니다. 그렇지 않은 경우 잘못된 코드를 실행하고 파이프라인이 플러시되고 올바른 블록이 실행됩니다.
심상:
경로 1 또는 경로 2를 선택해야 한다고 가정해 보겠습니다. 파트너가 지도를 확인하기를 기다리거나 ##에서 멈춰서 기다리거나 경로 1을 선택하고 운이 좋으면(경로 1이 올바른 경로임), 그러면 파트너가 지도를 확인할 때까지 기다릴 필요가 없었습니다(지도를 확인하는 데 걸리는 시간을 절약했습니다). 그렇지 않으면 그냥 돌아서게 될 것입니다.
파이프라인을 플러싱하는 것은 매우 빠르지만 요즘에는 이 도박을 할 가치가 있습니다. 정렬된 데이터나 느리게 변경되는 데이터를 예측하는 것은 빠른 변화를 예측하는 것보다 항상 쉽고 더 좋습니다.
O Route 1 /------------------------------- /|\ / | ---------##/ / \ \ \ Route 2 \--------------------------------
답변자 : Luke Hutchison
ARM에서는 분기가 필요하지 않습니다. 모든 명령어에는 프로세서 상태 레지스터에서 발생할 수 있는 16가지 다른 조건 중 하나를 테스트하는 4비트 조건 필드가 있고 명령어의 조건이 다음과 같은 경우 false이면 명령을 건너뜁니다. 이렇게 하면 짧은 분기가 필요하지 않으며 이 알고리즘에 대한 분기 예측 적중이 없습니다. 따라서 이 알고리즘의 정렬된 버전은 정렬의 추가 오버헤드로 인해 ARM에서 정렬되지 않은 버전보다 느리게 실행됩니다.
이 알고리즘의 내부 루프는 ARM 어셈블리 언어에서 다음과 같습니다.
MOV R0, #0 // R0 = sum = 0 MOV R1, #0 // R1 = c = 0 ADR R2, data // R2 = addr of data array (put this instruction outside outer loop) .inner_loop // Inner loop branch label LDRB R3, [R2, R1] // R3 = data[c] CMP R3, #128 // compare R3 to 128 ADDGE R0, R0, R3 // if R3 >= 128, then sum += data[c] -- no branch needed! ADD R1, R1, #1 // c++ CMP R1, #arraySize // compare c to arraySize BLT inner_loop // Branch to inner_loop if c < arraySize
그러나 이것은 실제로 더 큰 그림의 일부입니다.
CMP opcode는 PSR(Processor Status Register)의 상태 비트를 항상 업데이트합니다. 그 이유는 이것이 목적이기 때문입니다. 그러나 명령어에 선택적 S 접미사를 추가하여 PSR을 업데이트해야 한다고 지정하지 않는 한 대부분의 다른 명령어는 PSR을 건드리지 않습니다. 지시의 결과에. 4비트 조건 접미사와 마찬가지로 PSR에 영향을 주지 않고 명령을 실행할 수 있다는 것은 ARM에서 분기의 필요성을 줄이고 하드웨어 수준에서 비순차적 디스패치를 용이하게 하는 메커니즘입니다. 상태 비트에 이어서(또는 병렬로) 명시적으로 상태 비트에 영향을 미치지 않아야 하는(또는 영향을 받지 않아야 하는) 다른 많은 작업을 수행할 수 있습니다. 그러면 이전에 X가 설정한 상태 비트의 상태를 테스트할 수 있습니다.
조건 테스트 필드와 선택적 "상태 비트 설정" 필드를 결합할 수 있습니다. 예를 들면 다음과 같습니다.
-
ADD R1, R2, R3 은 상태 비트를 업데이트하지 않고 R1 = R2 + R3 을 수행합니다. -
ADDGE R1, R2, R3 은 상태 비트에 영향을 미친 이전 명령어가 보다 크거나 같음 조건을 초래한 경우에만 동일한 작업을 수행합니다. -
ADDS R1, R2, R3 은 덧셈을 수행한 다음 결과가 음수, 0, Carried(부호 없는 덧셈의 경우) 또는 oVerflowed(부호 있는 덧셈의 경우)인지 여부에 따라 프로세서 상태 레지스터 N , Z , C 및 V . -
ADDSGE R1, R2, R3 GE 테스트가 참인 경우에만 추가를 수행한 다음 추가 결과에 따라 상태 비트를 업데이트합니다.
대부분의 프로세서 아키텍처에는 주어진 작업에 대해 상태 비트를 업데이트해야 하는지 여부를 지정할 수 있는 기능이 없으므로 상태 비트를 저장하고 나중에 복원하기 위해 추가 코드를 작성해야 하거나 추가 분기가 필요할 수 있습니다. 순서 실행 효율성: 대부분의 명령 이후에 강제로 상태 비트를 업데이트하는 대부분의 CPU 명령 세트 아키텍처의 부작용 중 하나는 서로 간섭하지 않고 병렬로 실행할 수 있는 명령을 구별하는 것이 훨씬 더 어렵다는 것입니다. 상태 비트를 업데이트하면 부작용이 있으므로 코드에 선형화 효과가 있습니다. 명령 후 상태 비트를 업데이트하거나 업데이트하지 않는 옵션과 함께 모든 명령에서 분기 없는 조건 테스트를 혼합 및 일치시키는 ARM의 기능은 어셈블리 언어 프로그래머와 컴파일러 모두에게 매우 강력하며 매우 효율적인 코드를 생성합니다.
분기할 필요가 없으면 짧은 분기가 될 파이프라인을 플러시하는 시간 비용을 피할 수 있고 다양한 형태의 추측 평가의 설계 복잡성을 피할 수 있습니다. 최근에 발견된 많은 프로세서 취약점(Spectre 등)에 대한 완화의 초기 순진한 구현의 성능 영향은 최신 프로세서의 성능이 복잡한 추측 평가 논리에 얼마나 의존하는지 보여줍니다. 파이프라인이 짧고 분기 필요성이 크게 감소했기 때문에 ARM은 CISC 프로세서만큼 투기적 평가에 의존할 필요가 없습니다. (물론 고급 ARM 구현에는 추측 평가가 포함되지만 성능 이야기의 작은 부분입니다.)
ARM이 놀라운 성공을 거둔 이유가 무엇인지 궁금하다면 이 두 메커니즘의 뛰어난 효과와 상호 작용(산술 연산자의 두 인수 중 하나를 왼쪽 또는 오른쪽으로 "배럴 시프트"할 수 있는 다른 메커니즘과 결합하거나 메모리 액세스를 오프셋할 수 있습니다.) 추가 비용이 없는 연산자)는 ARM 아키텍처 효율성의 가장 큰 소스 중 일부이기 때문에 이야기의 큰 부분입니다. 1983년 ARM ISA의 원래 디자이너인 Steve Furber와 Roger(현재 Sophie) Wilson의 탁월함은 아무리 강조해도 지나치지 않습니다.
답변자 : Farhad
분기 예측에 관한 것입니다. 그것은 무엇입니까?
분기 예측기는 현대 아키텍처에서 여전히 관련성을 찾는 고대의 성능 향상 기술 중 하나입니다. 간단한 예측 기술은 빠른 조회와 전력 효율성을 제공하지만 높은 오예측률로 어려움을 겪습니다.
반면에 복잡한 분기 예측(신경 기반 또는 2단계 분기 예측의 변형)은 더 나은 예측 정확도를 제공하지만 더 많은 전력을 소비하고 복잡성이 기하급수적으로 증가합니다.
이 외에도 복잡한 예측 기술에서 분기를 예측하는 데 걸리는 시간 자체가 2~5주기로 매우 높아 실제 분기의 실행 시간과 비슷합니다.
분기 예측은 기본적으로 최소의 리소스로 가능한 가장 낮은 실패율, 낮은 전력 소비 및 낮은 복잡성을 달성하는 데 중점을 둔 최적화(최소화) 문제입니다.
분기에는 실제로 세 가지 종류가 있습니다.
순방향 조건 분기 - 런타임 조건에 따라 PC(프로그램 카운터)가 명령 스트림의 순방향 주소를 가리키도록 변경됩니다.
역방향 조건 분기 - PC는 명령 스트림에서 역방향을 가리키도록 변경됩니다. 분기는 루프 끝의 테스트에 루프가 다시 실행되어야 한다고 명시될 때 프로그램 루프의 시작 부분으로 뒤로 분기하는 것과 같은 일부 조건을 기반으로 합니다.
무조건 분기 - 여기에는 특정 조건이 없는 점프, 프로시저 호출 및 반환이 포함됩니다. 예를 들어, 무조건 점프 명령어는 어셈블리 언어에서 단순히 "jmp"로 코딩될 수 있으며 명령어 스트림은 점프 명령어가 가리키는 대상 위치로 즉시 보내져야 하는 반면, 조건부 점프는 "jmpne"로 코딩될 수 있습니다. 이전 "비교" 명령어에서 두 값을 비교한 결과 값이 같지 않은 것으로 표시되는 경우에만 명령어 스트림을 리디렉션합니다. (x86 아키텍처에서 사용하는 분할된 주소 지정 체계는 점프가 "가까운"(세그먼트 내) 또는 "원거리"(세그먼트 외부)일 수 있기 때문에 추가 복잡성을 추가합니다. 각 유형은 분기 예측 알고리즘에 서로 다른 영향을 미칩니다.
정적/동적 분기 예측 : 정적 분기 예측은 조건 분기가 처음 발생할 때 마이크로프로세서에서 사용되며 동적 분기 예측은 조건 분기 코드의 후속 실행에 사용됩니다.
참조:
답변자 : Yochai Timmer
분기 예측이 속도를 늦출 수 있다는 사실 외에도 정렬된 배열에는 또 다른 이점이 있습니다.
값을 확인하는 대신 중지 조건을 가질 수 있습니다. 이렇게 하면 관련 데이터만 반복하고 나머지는 무시합니다.
분기 예측은 한 번만 누락됩니다.
// sort backwards (higher values first), may be in some other part of the code std::sort(data, data + arraySize, std::greater<int>()); for (unsigned c = 0; c < arraySize; ++c) { if (data[c] < 128) { break; } sum += data[c]; }
답변자 : omkaartg
정렬된 배열은 분기 예측이라는 현상으로 인해 정렬되지 않은 배열보다 빠르게 처리됩니다.
분기 예측기는 분기 방향을 예측하여 명령 파이프라인의 흐름을 개선하는 디지털 회로(컴퓨터 아키텍처)입니다. 회로/컴퓨터는 다음 단계를 예측하고 실행합니다.
잘못된 예측을 하면 이전 단계로 돌아가서 다른 예측으로 실행하게 됩니다. 예측이 정확하다고 가정하면 코드는 다음 단계로 계속됩니다. 잘못된 예측은 올바른 예측이 발생할 때까지 동일한 단계를 반복하는 결과를 낳습니다.
귀하의 질문에 대한 답변은 매우 간단합니다.
정렬되지 않은 배열에서 컴퓨터는 여러 예측을 수행하므로 오류 가능성이 높아집니다. 반면 정렬된 배열에서는 컴퓨터가 예측을 더 적게 수행하므로 오류 가능성이 줄어듭니다. 더 많은 예측을 하려면 더 많은 시간이 필요합니다.
정렬된 배열: 직선 도로
____________________________________________________________________________________ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
정렬되지 않은 배열: 곡선 도로
______ ________ | |__|
분기 예측: 어느 도로가 직선인지 확인/확인 없이 따라가는 추측/예측
___________________________________________ Straight road |_________________________________________|Longer road
두 도로가 같은 목적지에 도달하지만 직선 도로는 더 짧고 다른 하나는 더 깁니다. 그러다 실수로 다른 길을 선택하면 후퇴가 없기 때문에 더 긴 길을 선택하면 시간을 더 낭비하게 된다. 이것은 컴퓨터에서 일어나는 일과 유사하며, 이것이 더 나은 이해에 도움이 되었기를 바랍니다.
또한 의견에서 @Simon_Weaver 를 인용하고 싶습니다.
더 적은 수의 예측을 하는 것이 아니라 더 적은 수의 잘못된 예측을 합니다. 루프를 통해 매번 예측해야 합니다...
답변자 : Shan
다음 MATLAB 코드에 대해 MacBook Pro(Intel i7, 64비트, 2.4GHz)와 함께 MATLAB 2011b에서 동일한 코드를 시도했습니다.
% Processing time with Sorted data vs unsorted data %========================================================================== % Generate data arraySize = 32768 sum = 0; % Generate random integer data from range 0 to 255 data = randi(256, arraySize, 1); %Sort the data data1= sort(data); % data1= data when no sorting done %Start a stopwatch timer to measure the execution time tic; for i=1:100000 for j=1:arraySize if data1(j)>=128 sum=sum + data1(j); end end end toc; ExeTimeWithSorting = toc - tic;
위의 MATLAB 코드에 대한 결과는 다음과 같습니다.
a: Elapsed time (without sorting) = 3479.880861 seconds. b: Elapsed time (with sorting ) = 2377.873098 seconds.
@GManNickG에서와 같은 C 코드의 결과는 다음과 같습니다.
a: Elapsed time (without sorting) = 19.8761 sec. b: Elapsed time (with sorting ) = 7.37778 sec.
이를 기반으로 MATLAB은 정렬이 없는 C 구현보다 거의 175배 , 정렬이 있는 경우 350배 느린 것으로 보입니다. 즉, (브랜치 예측) 효과는 C 구현을위한 구현 및 MATLAB 2.7 대 1.46x이다.
답변자 : user2297550
데이터를 정렬해야 한다는 다른 답변의 가정은 옳지 않습니다.
다음 코드는 전체 배열을 정렬하지 않고 200개 요소로 구성된 세그먼트만 정렬하므로 가장 빠르게 실행됩니다.
k 요소 섹션만 정렬하면 전체 배열을 정렬하는 데 필요한 O(n.log(n)) 시간이 아닌 O(n)
#include <algorithm> #include <ctime> #include <iostream> int main() { int data[32768]; const int l = sizeof data / sizeof data[0]; for (unsigned c = 0; c < l; ++c) data[c] = std::rand() % 256; // sort 200-element segments, not the whole array for (unsigned c = 0; c + 200 <= l; c += 200) std::sort(&data[c], &data[c + 200]); clock_t start = clock(); long long sum = 0; for (unsigned i = 0; i < 100000; ++i) { for (unsigned c = 0; c < sizeof data / sizeof(int); ++c) { if (data[c] >= 128) sum += data[c]; } } std::cout << static_cast<double>(clock() - start) / CLOCKS_PER_SEC << std::endl; std::cout << "sum = " << sum << std::endl; }
이것은 또한 정렬 순서와 같은 알고리즘 문제와 아무 관련이 없으며 실제로 분기 예측이라는 것을 "증명"합니다.
답변자 : Community Wiki
이 질문에 대한 Bjarne Stroustrup의 답변:
면접 질문 같네요. 사실이야? 당신은 어떻게 알겠습니까? 먼저 몇 가지 측정을 하지 않고 효율성에 대한 질문에 답하는 것은 좋지 않으므로 측정 방법을 아는 것이 중요합니다.
그래서 백만 정수의 벡터로 시도하고 다음을 얻었습니다.
Already sorted 32995 milliseconds Shuffled 125944 milliseconds Already sorted 18610 milliseconds Shuffled 133304 milliseconds Already sorted 17942 milliseconds Shuffled 107858 milliseconds
확인하기 위해 몇 번 실행했습니다. 예, 현상은 실제입니다. 내 키 코드는 다음과 같습니다.
void run(vector<int>& v, const string& label) { auto t0 = system_clock::now(); sort(v.begin(), v.end()); auto t1 = system_clock::now(); cout << label << duration_cast<microseconds>(t1 — t0).count() << " milliseconds\n"; } void tst() { vector<int> v(1'000'000); iota(v.begin(), v.end(), 0); run(v, "already sorted "); std::shuffle(v.begin(), v.end(), std::mt19937{ std::random_device{}() }); run(v, "shuffled "); }
이 컴파일러, 표준 라이브러리 및 최적화 프로그램 설정에서는 적어도 현상이 현실입니다. 다른 구현은 다른 답변을 제공할 수 있고 제공합니다. 사실, 누군가가 더 체계적인 연구를 수행했으며(빠른 웹 검색으로 찾을 수 있음) 대부분의 구현에서 그 효과가 나타납니다.
한 가지 이유는 분기 예측입니다. 정렬 알고리즘의 핵심 연산은 “if(v[i] < pivot]) …” 또는 이와 동등한 것입니다. 테스트가 항상 참인 정렬된 시퀀스의 경우 무작위 시퀀스의 경우 선택된 분기가 무작위로 변경됩니다.
또 다른 이유는 벡터가 이미 정렬되어 있으면 요소를 올바른 위치로 이동할 필요가 없기 때문입니다. 이러한 작은 세부 사항의 효과는 우리가 본 5~6개의 요소입니다.
퀵정렬(일반적인 정렬)은 컴퓨터 과학의 위대한 지성인을 끌어들인 복잡한 연구입니다. 좋은 정렬 기능은 좋은 알고리즘을 선택하고 구현 시 하드웨어 성능에 주의를 기울인 결과입니다.
효율적인 코드를 작성하려면 기계 아키텍처에 대해 약간 알아야 합니다.
답변자 : hatirlatici
이 질문은 CPU의 분기 예측 모델에 뿌리를 두고 있습니다. 이 문서를 읽는 것이 좋습니다.
다중 분기 예측 및 분기 주소 캐시를 통해 명령 가져오기 속도 증가
요소를 정렬하면 IR 이 모든 CPU 명령어를 계속해서 가져오는 데 신경을 쓸 수 없습니다. 캐시에서 가져옵니다.
답변자 : Numan Gillani
분기 예측
이것을 분기 예측 이라고 합니다. 분기 예측이 없으면 프로세서는 조건부 점프 명령이 실행 단계를 통과할 때까지 기다려야 다음 명령이 파이프라인의 페치 단계에 들어갈 수 있습니다. 분기 예측기는 조건부 점프가 수행될 가능성이 가장 높은지 여부를 추측하여 이러한 시간 낭비를 방지하려고 시도합니다. 그런 다음 가장 가능성이 높은 것으로 추측되는 분기를 가져와서 추측에 따라 실행합니다. 나중에 추측이 잘못된 것으로 감지되면 추측에 따라 실행되어 지연이 발생합니다.
data[c] >= 128
이 링크에서 더 많은 도움 받기: 광역 문제 슈퍼스칼라에 대한 다중 분기 예측
답변자 : Bart Mensfort
출력 값 범위가 제한되어 있으므로 데이터를 정렬하면 안 됩니다. 각 값이 발생하는 횟수를 계산하는 것이 훨씬 빠릅니다.
예를 들어 0..3 사이에 20개의 데이터가 있는 경우 3개의 카운터를 예약할 수 있습니다. 결국 당신은 가질 수 있습니다 : { 0: 10x , 1: 8x, 2: 2x }
이 배열을 선형 배열로 다시 변환하는 것은 쉽습니다. 10x 0, 8x 1, 2x 2를 인쇄하면 됩니다.
값이 0..2가 아니지만 여전히 제한적일 때 이 방법을 고려할 수 있습니다. 정렬은 항상 느립니다! 다른 장점: 이것은 코드가 적고 읽기 쉽고 테스트하기 쉽고 버그가 적습니다.
출처 : Here
출처 : http:www.stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array">
