정렬된 어레이의 처리가 정렬되지 않은 어레이의 처리보다 빠른 이유는 무엇입니까?
다음은 매우 특이한 동작을 나타내는 C++ 코드입니다.어떤 이상한 이유로 데이터를 정렬하면(시간 지정 영역 전에) 기적적으로 루프가 거의 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는 다른/나중의 컴파일러 및 옵션에서도 같은 효과를 발휘합니다.
- 정렬되지 않은 어레이를 처리하는 속도가 최신 x86-64 Clang을 사용하여 정렬된 어레이를 처리하는 속도와 동일한 이유는 무엇입니까?
- gcc 최적화 플래그 -O3이 코드를 -O2보다 느리게 만듭니다.
지점 예측이란?
철도 교차로를 생각해 보십시오.
이미지: Mecanismo, Wikimedia Commons.CC-By-SA 3.0 라이선스로 사용됩니다.
논거를 위해, 이것이 장거리 통신이나 무선 통신 이전인 1800년대라고 가정해 봅시다.
당신은 분기점의 교환원으로서 기차가 오는 소리를 듣습니다.당신은 그것이 어느 방향으로 가야 하는지 전혀 모릅니다.당신은 기관사에게 어느 방향을 원하는지 묻기 위해 열차를 세운다.다음으로 스위치를 적절히 설정합니다.
전차는 무겁고 관성이 강하기 때문에 시동을 걸거나 속도를 늦추는 데 오랜 시간이 걸립니다.
더 좋은 방법이 있을까요?기차가 어느 방향으로 갈지 맞춰보세요!
- 당신이 맞혔다면, 그것은 계속됩니다.
- 만약 당신이 틀렸다면, 선장은 멈춰서서 뒤로 물러서서 당신에게 스위치를 바꾸라고 소리칠 것이다.그런 다음 다른 경로로 재시작할 수 있습니다.
매번 맞히면 기차는 멈추지 않아도 된다.
만약 당신이 너무 자주 틀리면, 기차는 멈추고, 백업하고, 다시 시작하는 데 많은 시간을 소비할 것입니다.
if 스테이트먼트를 검토합니다.프로세서 레벨에서는, 브랜치 명령입니다.
프로세서로 브랜치가 표시됩니다.당신은 그것이 어느 방향으로 갈지 모릅니다.무슨 일을 하세요?실행을 중지하고 이전 명령이 완료될 때까지 기다립니다.그런 다음 올바른 경로로 계속 진행합니다.
최신 프로세서는 복잡하고 파이프라인이 길다.이것은 그들이 "몸풀기"와 "속도 늦추기"에 오랜 시간이 걸린다는 것을 의미합니다.
더 좋은 방법이 있을까요?나뭇가지가 어느 방향으로 갈지 맞춰보세요!
- 추측이 맞으면 실행을 계속합니다.
- 추측이 틀리면 파이프라인을 플러시하고 브랜치로 롤백해야 합니다.그런 다음 다른 경로로 재시작할 수 있습니다.
매번 정확하게 맞히면 실행을 멈출 필요가 없습니다.
너무 자주 틀리면 시간 지연, 롤백 및 재시작에 많은 시간이 소요됩니다.
분기 예측입니다.기차가 깃발로 방향만 표시할 수 있기 때문에 최선의 유추는 아니라는 것을 인정한다.그러나 컴퓨터에서는 프로세서가 마지막 순간까지 브랜치가 어느 방향으로 갈지 알 수 없습니다.
어떻게 전략적으로 열차가 후진하여 다른 길로 가야 하는 횟수를 최소화할 수 있을까요?지난 역사를 보세요!열차가 99% 좌회전하면 좌회전인 것 같아요.번갈아가면, 당신은 추측을 번갈아 합니다.세 번마다 한 방향으로 가면 똑같은 거겠죠?
즉, 패턴을 파악하여 따라가려고 하는 것입니다.이것이 분기 예측 변수의 작동 방식입니다.
대부분의 응용 프로그램에는 올바르게 동작하는 분기가 있습니다.따라서 최신 지점 예측 변수는 일반적으로 90% 이상의 적중률을 달성합니다.그러나 인식할 수 있는 패턴이 없는 예측 불가능한 지점에 직면했을 때 지점 예측 변수는 사실상 무용지물입니다.
추가 읽기: Wikipedia의 "Branch predictor" 기사.
위에서 시사한 바와 같이 범인은 다음과 같은 if 스테이트먼트입니다.
if (data[c] >= 128)
sum += data[c];
데이터는 0과 255 사이에 균등하게 분포되어 있습니다.데이터가 정렬될 때 대략 전반의 반복은 if 스테이트먼트에 들어가지 않습니다.그런 다음 모두 if-statement를 입력합니다.
브런치가 같은 방향으로 여러 번 연속적으로 이동하기 때문에 브런치 프레딕터에 매우 적합합니다.단순한 포화 카운터라도 방향을 바꾼 후 몇 번의 반복을 제외하고 분기를 정확하게 예측합니다.
빠른 시각화:
T = branch taken
N = branch not taken
data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N N N N N ... N N T T T ... T T T ...
= 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 |
| 분기 없음 - 랜덤 데이터 | 2.564 |
| 분기 없음 - 정렬된 데이터 | 2.587 |
Java - NetBeans 7.1.1 JDK 7 - x 64
| 시나리오 | 시간(초) |
|---|---|
| 분기 - 랜덤 데이터 | 10.93293813 |
| 분기 - 정렬된 데이터 | 5.643797077 |
| 분기 없음 - 랜덤 데이터 | 3.113581453 |
| 분기 없음 - 정렬된 데이터 | 3.186068823 |
관찰:
- 브런치 포함:정렬된 데이터와 정렬되지 않은 데이터 사이에는 큰 차이가 있습니다.
- Hack의 경우:정렬된 데이터와 정렬되지 않은 데이터의 차이는 없습니다.
- C++의 경우 데이터를 정렬할 때 분기보다 해킹이 약간 느립니다.
일반적으로 중요한 루프(예: 이 예)에서 데이터에 의존하는 분기를 회피하는 것이 일반적입니다.
업데이트:
GCC 4.6.1과
-O3또는-ftree-vectorizex64의 경우 조건부 이동을 생성할 수 있으므로 정렬된 데이터와 정렬되지 않은 데이터 간에 차이가 없습니다. 둘 다 빠릅니다.(또는 다소 빠른 경우: 이미 정렬된 경우,
cmov특히 GCC가 단순히 중요한 경로에만 배치하는 것이 아니라add특히 Broadwell 이전 인텔에서는cmov2 사이클 레이텐시가 있습니다.gcc 최적화 플래그 -O3는 코드를 -O2보다 느리게 만듭니다.)VC++ 2010은 다음 조건에서도 이 브랜치에 대한 조건부 이동을 생성할 수 없습니다.
/Ox.인텔(R) C++ 컴파일러(ICC) 11은 놀라운 기능을 합니다.2개의 루프를 교환하여 예측할 수 없는 브런치를 외부 루프로 호이스트합니다.예측에 영향을 받지 않을 뿐만 아니라 VC++ 및 GCC가 생성할 수 있는 속도보다 2배 빠릅니다.다시 말해, ICC는 테스트 루프를 이용하여 벤치마크를 물리쳤습니다.
인텔 컴파일러에 브런치리스 코드를 지정하면 완전히 벡터화됩니다.(루프 교환을 사용하는 경우) 브런치와 같은 속도로 동작합니다.
이는 최신 컴파일러의 코드 최적화 능력에 있어서도 크게 다를 수 있음을 보여줍니다.
브런치 예측
정렬된 배열에서는data[c] >= 128첫 번째입니다false가치관의 연속에 대해서, 그리고 나서true모든 후속 값에 적용됩니다.그건 예측하기 쉬워요.정렬되지 않은 어레이의 경우 분기 비용을 지불해야 합니다.
데이터를 정렬하면 성능이 획기적으로 향상되는 이유는 미스티컬의 답변에서 아름답게 설명했듯이 분기 예측 패널티가 제거되기 때문이다.
자, 이제 코드를 보면
if (data[c] >= 128)
sum += data[c];
우리는 이 특별한 것의 의미가if... else...브랜치는 조건이 충족될 때 무언가를 추가하는 것입니다.이 브랜치 유형은 조건부 이동 명령으로 컴파일되는 조건부 이동 명령으로 쉽게 변환할 수 있습니다.cmovl, 의x86시스템.브랜치, 즉 잠재적인 브랜치 예측 패널티가 제거됩니다.
인C,따라서C++(최적화하지 않고) 직접 컴파일하여 의 조건부 이동명령어로 만듭니다.x86는 3진 연산자입니다.... ? ... : ...따라서 위의 문장은 동등한 문장으로 고쳐 씁니다.
sum += data[c] >=128 ? data[c] : 0;
가독성을 유지하면서 속도 향상 계수를 확인할 수 있습니다.
인텔 Core i7-2600K @ 3.4GHz 및 Visual Studio 2010 릴리즈 모드에서는 벤치마크는 다음과 같습니다.
x86
| 시나리오 | 시간(초) |
|---|---|
| 분기 - 랜덤 데이터 | 8.885 |
| 분기 - 정렬된 데이터 | 1.528 |
| 분기 없음 - 랜덤 데이터 | 3.716 |
| 분기 없음 - 정렬된 데이터 | 3.71 |
x64
| 시나리오 | 시간(초) |
|---|---|
| 분기 - 랜덤 데이터 | 11.302 |
| 분기 - 정렬된 데이터 | 1.830 |
| 분기 없음 - 랜덤 데이터 | 2.736 |
| 분기 없음 - 정렬된 데이터 | 2.737 |
결과는 여러 테스트에서 강력합니다.브랜치 결과를 예측할 수 없을 때는 속도가 크게 향상되지만, 예측할 수 있을 때는 다소 어려움을 겪습니다.실제로 조건부 이동을 사용할 경우 데이터 패턴에 관계없이 성능은 동일합니다.
이제 더 자세히 알아보겠습니다.x86조립을 합니다.심플화를 위해 두 가지 기능을 사용합니다.max1그리고.max2.
max1조건부 브랜치를 사용합니다.if... else ...:
int max1(int a, int b) {
정렬된 어레이의 처리가 정렬되지 않은 어레이의 처리보다 빠른 이유는 무엇입니까? if (a > b)
return a;
else
return b;
}
max23진 연산자를 사용합니다.... ? ... : ...:
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이전 명령의 결과에 의존하지 마십시오.후기 단계만 결과를 필요로 합니다.따라서 우리는 하나의 명령 실행 시간의 극히 일부만 기다립니다.따라서 예측이 쉬운 경우 조건부 이동 버전이 지점보다 느립니다.
컴퓨터 시스템: 프로그래머의 관점, 제2판은 이것을 자세히 설명합니다.섹션 3.6.6의 조건부 이동 지시, 제4장의 프로세서 아키텍처 전체, 섹션 5.11.2의 분기 예측 및 오심 패널티 특별처리를 확인할 수 있습니다.
경우에 따라서는 최신 컴파일러 중 일부는 어셈블리용으로 코드를 최적화할 수 있고, 일부 컴파일러는 그렇지 않습니다(문제의 코드는 Visual Studio의 네이티브 컴파일러를 사용하는 것입니다).브런치와 조건부 이동의 퍼포먼스 차이를 알면 컴파일러가 자동으로 최적화할 수 없을 정도로 복잡한 시나리오가 발생했을 때 보다 뛰어난 퍼포먼스로 코드를 작성할 수 있습니다.
이 코드에 대해 더 많은 최적화를 실시할 수 있는지 궁금할 경우 다음을 고려하십시오.
원래 루프부터 시작합니다.
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];
}
}
그러면 이제 아시겠죠?ifconditional은 실행 내내 일정합니다.i루프를 돌리면,if출력:
for (unsigned j = 0; j < arraySize; ++j)
{
if (data[j] >= 128)
{
for (unsigned i = 0; i < 100000; ++i)
{
sum += data[j];
}
}
}
그런 다음 부동소수점 모델에서 허용된다고 가정하면 내부 루프를 하나의 표현으로 축소할 수 있습니다( )./fp:fast예를 들어, 투척됩니다).
for (unsigned j = 0; j < arraySize; ++j)
{
if (data[j] >= 128)
{
sum += data[j] * 100000;
}
}
그것은 이전보다 10만 배 빨라졌다.
CPU의 분기 예측 변수에 문제가 있는 코드를 식별하는 방법에 관심이 있는 사람도 있을 것입니다.Valgrind 툴cachegrind에는 브런치 스위칭 시뮬레이터가 있으며 를 사용하여 유효하게 되어 있습니다.--branch-sim=yesflag. 외부 루프의 수를 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)line이 164,050,007의 예측에 어긋난 조건부 브랜치의 원인이 되고 있습니다(Bcm캐시그린드의 분기 분할 모델에서는)이 발생하지만 정렬된 버전에서는 10,006밖에 발생하지 않습니다.
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)
...
방금 이 질문과 답을 읽었는데 답이 빠진 것 같아요.
관리 대상 언어에서 특히 잘 작동하는 지점 예측을 제거하는 일반적인 방법은 지점을 사용하는 대신 테이블 검색을 사용하는 것입니다(이 경우 테스트하지 않았습니다).
이 접근방식은 일반적으로 다음과 같은 경우에 기능합니다.
- 작은 테이블로 프로세서에 캐시되어 있을 가능성이 있습니다.
- 매우 엄격한 루프 상태에서 작업을 수행하거나 프로세서가 데이터를 프리로드할 수 있습니다.
배경과 이유
프로세서의 관점에서 보면 메모리가 느립니다.속도의 차이를 보완하기 위해 프로세서(L1/L2 캐시)에 몇 개의 캐시가 내장되어 있습니다.그래서 당신이 좋은 계산을 하고 있다고 상상해보고 당신이 기억을 필요로 한다는 것을 알아보세요.프로세서는 「로드」연산을 실시해, 메모리의 일부를 캐시에 로드합니다.그 후, 캐시를 사용해 나머지 계산을 실시합니다.메모리는 비교적 느리기 때문에, 이 「로드」는 프로그램의 속도를 늦춥니다.
분기 예측과 마찬가지로 Pentium 프로세서에서 최적화되어 있습니다.프로세서는 데이터를 로드해야 한다고 예측하고 작업이 실제로 캐시에 도달하기 전에 데이터를 캐시에 로드하려고 합니다.이미 알고 있듯이 분기 예측이 잘못될 수 있습니다.최악의 경우 메모리 로드를 실제로 기다릴 필요가 있습니다(즉, 분기 예측 실패는 나쁘고 분기 예측 실패 후의 메모리 로드는 끔찍합니다).
다행히 메모리 액세스 패턴이 예측 가능한 경우 프로세서는 고속 캐시에 메모리를 로드하고 모든 것이 정상입니다.
가장 먼저 알아야 할 것은 무엇이 작은가?일반적으로 크기가 작을수록 좋지만, 경험의 법칙은 크기가 4096바이트 미만인 조회 테이블을 고수하는 것입니다.상한: 룩업 테이블이 64K보다 크다면 재고해 볼 가치가 있습니다.
테이블 구성
그래서 우리는 작은 테이블을 만들 수 있다는 것을 알아냈습니다.다음에 해야 할 일은 검색 기능을 설치하는 것입니다.룩업 함수는 보통 몇 가지 기본 정수 연산(또는 xor, shift, add, remove 및 multiply)을 사용하는 작은 함수입니다.검색 기능을 통해 입력 내용을 표 내의 '고유 키'로 변환하고 싶은 경우, 그러면 원하는 모든 작업에 대한 답을 얻을 수 있습니다.
이 경우 >= 128은 값을 유지할 수 있음을 의미하고 128 미만은 값을 삭제할 수 있음을 의미합니다.가장 쉬운 방법은 'AND'를 사용하는 것입니다.이것을 보관하고 있는 경우는 7FFFFFF로, 폐기하고 싶은 경우는 0으로 합니다.또한 128은 2의 거듭제곱입니다.그러면 32768/128 정수의 표를 만들고 1개의 0과 다수의 7FFFFFF로 채울 수 있습니다.
관리 대상 언어
관리 대상 언어에서 이 기능이 잘 작동하는 이유가 궁금할 수 있습니다.결국 관리 언어는 어레이의 경계를 브랜치로 체크하여 혼란을 일으키지 않도록 합니다.
뭐, 꼭 그런 건 아니지만... :-)
관리 대상 언어에서 이 분기를 제거하기 위한 작업이 상당히 많이 진행되었습니다.예를 들어 다음과 같습니다.
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();
배열 정렬 시 데이터는 0에서 255 사이로 분산되므로 전반의 반복은 다음 단계로 넘어가지 않습니다.if- 스테이트먼트(the statement)if스테이트먼트는 이하에 공유됩니다).
if (data[c] >= 128)
sum += data[c];
문제는 다음과 같습니다.정렬된 데이터의 경우처럼 특정 상황에서는 위의 문장이 실행되지 않는 이유는 무엇입니까?"지점 예측 변수"가 등장합니다.분기 프레딕터는 분기(예: 분기)의 어느 방향의 분기)를 추측하는 디지털 회로입니다.if-then-elsestructure)는, 이것이 확실히 알려지기 전에 행해집니다.분기 예측 변수의 목적은 명령 파이프라인의 흐름을 개선하는 것입니다.지점 예측 변수는 높은 성능을 달성하는 데 중요한 역할을 합니다.
좀 더 잘 이해할 수 있도록 벤치 마킹을 해 봅시다.
퍼포먼스if- 스테이트먼트는 그 상태가 예측 가능한 패턴을 가지고 있는지 여부에 따라 달라집니다.조건이 항상 true 또는 false일 경우 프로세서의 분기 예측 로직이 패턴을 선택합니다.한편 패턴이 예측할 수 없는 경우에는if- 스테이트먼트는 훨씬 더 비쌉니다.
이 루프의 퍼포먼스를 다른 조건으로 측정합니다.
for (int i = 0; i < max; i++)
if (condition)
sum++;
다른 true-false 패턴을 가진 루프의 타이밍을 다음에 나타냅니다.
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
'나쁜' true-false 패턴으로 인해if- "좋은" 패턴보다 최대 6배 느린 문장이 표시됩니다.물론 어떤 패턴이 좋고 어떤 패턴이 나쁜지는 컴파일러와 특정 프로세서에 의해 생성되는 정확한 명령에 따라 달라집니다.
따라서 분기 예측이 성능에 미치는 영향은 의심의 여지가 없습니다.
분기 예측 오류를 방지하는 한 가지 방법은 조회 테이블을 작성하고 데이터를 사용하여 인덱싱하는 것입니다.Stefan de Bruijn은 그의 대답에서 그것을 논의했다.
그러나 이 경우 값이 [0, 255] 범위에 있으며 >= 128의 값에만 관심이 있습니다.즉, 값을 원하는지 여부를 나타내는 단일 비트를 쉽게 추출할 수 있습니다. 즉, 데이터를 오른쪽 7비트로 이동하면 0비트가 남거나 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 스테이트먼트가 있는 버전보다 훨씬 빠릅니다.
그러나 테스트에서는 명시적 룩업테이블이 이것보다 약간 빨랐습니다.아마 룩업테이블로의 인덱스가 비트 이동보다 약간 빨랐기 때문일 겁니다.이것은 내 코드가 어떻게 설정되고 룩업 테이블을 사용하는지 보여줍니다(상상적으로 호출되지 않음).lut코드 내의 "LookUp Table"을 참조하십시오).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사용할 포인터를 결정하는 데 사용할 수 있습니다.나는 2개의 명명된 포인터를 갖는 대신 바이너리 트리를 구현하는 라이브러리를 보았다.pLeft그리고.pRightor other)는 길이 2의 포인터 배열을 가지고 있으며, 어떤 포인터를 따를지 결정하기 위해 "bit" 기술을 사용했습니다.예를 들어 다음과 같습니다.
if (x < node->value)
node = node->pLeft;
else
node = node->pRight;
이 라이브러리는 다음과 같은 작업을 수행합니다.
i = (x < node->value);
node = node->link[i];
다음은 이 코드에 대한 링크입니다.레드 블랙 트리, 영속적으로 혼란스러운
정렬된 경우 성공적인 분기 예측 또는 분기 없는 비교 트릭에 의존하는 것보다 분기를 완전히 제거할 수 있습니다.
실제로 어레이는 인접한 존으로 분할되어 있습니다.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개의 표본) :-)
위의 동작은 Branch 예측에 의해 발생합니다.
분기 예측을 이해하려면 먼저 명령 파이프라인을 이해해야 합니다.
모든 명령은 여러 단계를 동시에 실행할 수 있도록 일련의 단계로 분할됩니다.이 기술은 명령 파이프라인이라고 하며 최신 프로세서의 throughput을 높이기 위해 사용됩니다.이를 더 잘 이해하려면 위키피디아에서 이 예를 참조하십시오.
일반적으로 최신 프로세서는 파이프라인이 상당히 길지만 쉽게 하기 위해 다음 4단계만 살펴보겠습니다.
- IF - 메모리에서 명령을 가져옵니다.
- ID - 명령을 디코딩합니다.
- EX - 명령을 실행합니다.
- WB - CPU 레지스터에 다시 쓰기
일반적으로 4단계 파이프라인에는 2가지 지침이 있습니다. 
위의 질문으로 돌아가면 다음 절차에 대해 생각해 보겠습니다.
A) if (data[c] >= 128)
/\
/ \
/ \
true / \ false
/ \
/ \
/ \
/ \
B) sum += data[c]; C) for loop or print().
분기 예측이 없으면 다음과 같은 상황이 발생합니다.
명령 B 또는 명령 C를 실행하기 위해서는 명령 A가 파이프라인의 EX 스테이지에 도달할 때까지 프로세서가 기다려야 합니다.명령 B 또는 명령 C로 갈지는 명령 A의 결과에 따라 결정되기 때문입니다.파이프라인은 이렇게 됩니다.
조건이 true를 반환하는 경우: 
조건이 false를 반환하는 경우: 
명령 A의 결과를 기다린 결과, 위의 경우(분기 예측 없이 true와 false 모두)에 소비된 CPU 사이클의 합계는 7입니다.
그렇다면 지점 예측이란 무엇일까요?
분기 예측 변수는 분기(if-then-else 구조)가 어느 방향으로 갈지 예측하려고 시도합니다.명령 A가 파이프라인의 EX 단계에 도달할 때까지 기다리지 않고 결정을 추측하여 해당 명령으로 이동합니다(이 예에서는 B 또는 C).
추측이 정확할 경우 파이프라인은 다음과 같습니다. 
추정이 잘못된 것이 나중에 발견되면 부분적으로 실행된 명령이 폐기되고 파이프라인이 올바른 분기로 다시 시작되므로 지연이 발생합니다.브랜치가 잘못 판단된 경우 낭비되는 시간은 가져오기 단계부터 실행 단계까지의 파이프라인의 단계 수와 동일합니다.최신 마이크로프로세서는 파이프라인이 상당히 긴 경향이 있기 때문에 오배정 지연은 10~20클럭 사이클입니다.파이프라인이 길어질수록 좋은 분기 예측 변수의 필요성이 커집니다.
OP 코드에서는 조건부 예측 변수가 처음으로 예측을 기반으로 하는 정보가 없으므로 처음으로 다음 명령을 랜덤하게 선택합니다.for 루프의 후반부에서 이력에 근거해 예측을 실시할 수 있습니다.오름차순으로 정렬된 배열에는 다음 세 가지 가능성이 있습니다.
- 모든 요소가 128 미만입니다.
- 모든 요소가 128보다 큽니다.
- 일부 시작 새 요소는 128보다 작으며 나중에 128보다 커집니다.
예측 변수가 첫 번째 런에서 항상 실제 분기를 가정한다고 가정해 보겠습니다.
첫 번째 경우, 역사적으로 모든 예측이 맞기 때문에 항상 진정한 분기가 필요합니다.두 번째 경우 처음에는 잘못 예측하지만 몇 번 반복하면 올바르게 예측됩니다.세 번째 케이스에서는 요소가 128 미만일 때까지 처음에 올바르게 예측합니다.그 후 일정 시간 동안 실패하며 분기 예측 실패가 이력에서 확인되면 자체 수정이 이루어집니다.
이러한 경우 모두 실패 횟수가 너무 적기 때문에 부분적으로 실행된 명령을 폐기하고 올바른 분기로 다시 시작하면 CPU 사이클이 줄어듭니다.
그러나 랜덤으로 정렬되지 않은 어레이의 경우 예측에서는 부분적으로 실행된 명령을 폐기하고 대부분의 경우 올바른 분기로 다시 시작해야 하며 정렬된 어레이에 비해 CPU 사이클이 더 많이 발생합니다.
공식 답변은 다음과 같습니다.
- 인텔 - 브랜치 오인 비용 회피
- 인텔 - 브런치 및 루프의 재구성을 통한 예측 오류 방지
- 과학 논문 - 분기 예측 컴퓨터 아키텍처
- 책: J.L. 헤네시, D.A. 패터슨: 컴퓨터 아키텍처: 정량적 접근법
- 과학잡지에 실린 기사: T.Y.Y.Yeh, Y.N.Patt은 이런 것들을 나뭇가지 예측에서 많이 만들었습니다.
분기 예측 변수가 혼동되는 이유도 이 그림을 통해 알 수 있습니다.
원래 코드의 각 요소는 랜덤 값입니다.
data[c] = std::rand() % 256;
예측 변수가 변을 바꿀 수 있도록std::rand()불다.
한편, 일단 정렬되면 예측 변수는 먼저 강하게 측정되지 않은 상태로 이동하고 값이 높은 값으로 변경되면 세 번의 런에서 강하게 측정되지 않은 값에서 강하게 측정되지 않은 값으로 변경됩니다.
같은 줄에서 (특히 Linux 커널과 같이 성능이 중요한 소프트웨어에서) 다음과 같은 문장을 찾을 수 있습니다.
if (likely( everything_is_ok ))
{
/* Do something */
}
또는 이와 유사합니다.
if (unlikely(very_improbable_condition))
{
/* Do something */
}
둘다요.likely()그리고.unlikely()실제로 GCC와 같은 것을 사용하여 정의되는 매크로입니다.__builtin_expect컴파일러가 사용자가 제공한 정보를 고려하여 조건을 선호하는 예측 코드를 삽입할 수 있도록 지원합니다.GCC는 실행 중인 프로그램의 동작을 변경하거나 캐시 클리어 등의 낮은 수준의 명령을 내보낼 수 있는 기타 빌트인을 지원합니다.사용 가능한 GCC의 빌트인에 대해서는, 이 메뉴얼을 참조해 주세요.
일반적으로 이러한 최적화는 실행 시간이 중요하고 중요한 하드 실시간 애플리케이션이나 임베디드 시스템에서 주로 볼 수 있습니다.예를 들어, 1/10000,000 회 밖에 발생하지 않는 에러 상태를 체크하고 있는 경우는, 왜 컴파일러에 이 사실을 알리지 않는 것입니까.이렇게 하면 기본적으로 분기 예측은 조건이 false라고 가정합니다.
C++에서 자주 사용되는 부울 연산은 컴파일된 프로그램에서 많은 분기를 생성합니다.이러한 브런치가 루프 내부에 있어 예측이 어려운 경우 실행 속도가 크게 느려질 수 있습니다.부울 변수는 값을 사용하여 8비트 정수로 저장됩니다.0위해서false그리고.1위해서true.
부울 변수를 입력으로 갖는 모든 연산자가 입력에 다음 값이 있는지 검사한다는 점에서 부울 변수가 과도하게 결정되었습니다.0또는1단, Bohns를 출력으로 하는 연산자는 다음 값을 생성할 수 없습니다.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;
char대신 사용됩니다.bool비트 연산자를 사용할 수 있도록 하기 위해(&그리고.|Boolean 연산자 대신 )를 사용합니다.&&그리고.||). 비트 연산자는 1개의 클럭 사이클만 실행하는 단일 명령입니다.OR 연산자(|)는, 다음과 같은 경우에도 동작합니다.a그리고.b이외의 가치가 있다0또는1. AND 연산자(&및 EXCLUSIVE OR 연산자(^)는 오퍼랜드의 값이 다음 값일 경우 일치하지 않는 결과를 얻을 수 있습니다.0그리고.1.
~NOT에는 사용할 수 없습니다.대신, 다음과 같이 알려진 변수에 대해 부울 NOT를 만들 수 있습니다.0또는1XOR에 의해1:
bool a, b;
b = !a;
최적화 대상:
char a = 0, b;
b = a ^ 1;
a && b와는 바꿀 수 없다a & b한다면b이 경우 평가해서는 안 되는 표현입니다.a이false(&&평가하지 않음b,&will)도 마찬가지입니다.a || b와는 바꿀 수 없다a | b한다면b이 경우 평가해서는 안 되는 표현입니다.a이true.
피연산자가 비교 대상인 경우보다 피연산자가 변수인 경우 비트 연산자를 사용하는 것이 더 좋습니다.
bool a; double x, y, z;
a = x > y && z < 5.0;
대부분의 경우 최적입니다(예상하지 않는 한).&&표현식을 사용하여 많은 분기 오예측을 생성할 수 있습니다.
그건 틀림없어!
분기 예측은 코드에서 발생하는 전환 때문에 로직 실행 속도를 늦춥니다.직진 거리나 턴이 많은 거리를 가는 것 같으니까, 직진 거리가 더 빨리 완성되겠지!...
배열이 정렬된 경우 첫 번째 단계에서 조건이 false입니다.data[c] >= 128그러면 거리의 끝까지 가는 모든 길에 대한 진정한 값이 됩니다.그래야 논리의 끝에 더 빨리 도달할 수 있습니다.한편, 정렬되지 않은 어레이를 사용하면 많은 회전과 처리가 필요하기 때문에 코드 실행 속도가 느려집니다.
아래 이미지를 작성했습니다.어느 거리가 더 빨리 완공될까요?
따라서 프로그래밍적으로 분기 예측은 프로세스를 느리게 만듭니다.
마지막으로, 각각이 코드에 다른 영향을 미칠 것이라는 두 가지 종류의 분기 예측이 있다는 것을 알게 되면 좋습니다.
1. 정적
2. 다이내믹
마이크로프로세서에 의해 조건부 분기가 처음 마주쳤을 때 정적 분기 예측이 사용되며, 조건부 분기 코드의 후속 실행에 동적 분기 예측이 사용된다.
if-else 또는 switch 스테이트먼트를 작성할 때 이러한 규칙을 이용하기 위해 코드를 효율적으로 작성하려면 가장 일반적인 경우를 먼저 체크하고 가장 일반적인 경우까지 단계적으로 작업합니다.루프는 보통 루프 반복기의 조건만 사용되므로 정적 분기 예측을 위해 특별한 코드 순서가 필요하지 않습니다.
이 질문은 이미 여러 번 훌륭하게 답변되었다.그래도 나는 또 다른 흥미로운 분석에 대해 그룹의 관심을 끌고 싶다.
최근 이 예(매우 약간 수정)는 Windows에서 프로그램 내에서 코드를 프로파일링하는 방법을 보여주는 방법으로도 사용되었습니다.이 과정에서 저자는 분류된 케이스와 분류되지 않은 케이스 모두에서 코드가 어디에 대부분의 시간을 소비하고 있는지를 판별하기 위해 결과를 사용하는 방법도 보여줍니다.마지막으로 HAL(Hardware Abstraction Layer)의 거의 알려지지 않은 기능을 사용하여 정렬되지 않은 케이스에서 어느 정도의 브랜치 오심이 발생하고 있는지를 판단하는 방법도 설명합니다.
이미 언급한 바와 같이, 미스터리의 배후에 있는 것은 Branch Predictor입니다.
저는 무언가를 추가하려는 것이 아니라 다른 방식으로 개념을 설명하는 것입니다.Wiki에는 텍스트와 다이어그램이 포함된 간결한 소개가 있습니다.Branch Predictor를 직관적으로 설명하기 위해 다이어그램을 사용하는 다음 설명이 마음에 듭니다.
컴퓨터 아키텍처에서 분기 프레딕터는 분기(예를 들어 if-then-else 구조)가 확실하게 알려지기 전에 어느 방향으로 갈 것인지를 추측하는 디지털 회로입니다.분기 예측 변수의 목적은 명령 파이프라인의 흐름을 개선하는 것입니다.분기 예측 변수는 x86과 같은 많은 최신 파이프라인 마이크로프로세서 아키텍처에서 높은 성능을 달성하는 데 중요한 역할을 합니다.
쌍방향 분기는 보통 조건부 점프 명령과 함께 구현된다.조건부 점프는 "취득하지 않음"으로 간주되어 조건부 점프 직후에 이어지는 코드의 첫 번째 분기로 실행을 계속할 수도 있고, 또는 "취득"되어 코드의 두 번째 분기가 기억되는 프로그램 메모리 내의 다른 곳으로 점프할 수도 있다.조건이 계산되고 조건부 점프가 명령 파이프라인의 실행 단계를 통과할 때까지 조건부 점프가 수행될지 여부는 확실히 알려져 있지 않다(그림 1 참조).
전술한 시나리오에 근거해, 다양한 상황에서 파이프라인에서 명령이 어떻게 실행되는지를 나타내는 애니메이션 데모를 작성했습니다.
- Branch Predictor를 사용하지 않습니다.
분기 예측이 없으면 프로세서는 조건부 점프 명령이 실행 단계를 통과할 때까지 기다려야 다음 명령이 파이프라인의 가져오기 단계에 들어갈 수 있습니다.
이 예에는 세 가지 지침이 포함되어 있으며, 첫 번째 지침은 조건부 점프 명령입니다.후자의 두 명령은 조건부 점프 명령이 실행될 때까지 파이프라인에 들어갈 수 있습니다.
3개의 명령을 완료하는 데 9개의 클럭 사이클이 소요됩니다.
- 분기 예측 변수를 사용하고 조건부 점프를 수행하지 마십시오.예측이 조건부 점프를 취하는 것이 아니라고 가정해 봅시다.
3개의 명령을 완료하는 데 7개의 클럭 사이클이 소요됩니다.
- 분기 예측 변수를 사용하여 조건부 점프를 수행합니다.예측이 조건부 점프를 취하는 것이 아니라고 가정해 봅시다.
3개의 명령을 완료하는 데 9개의 클럭 사이클이 소요됩니다.
브랜치가 잘못 판단된 경우 낭비되는 시간은 가져오기 단계부터 실행 단계까지의 파이프라인의 단계 수와 동일합니다.최신 마이크로프로세서는 파이프라인이 상당히 긴 경향이 있기 때문에 오배정 지연은 10~20클럭 사이클입니다.따라서 파이프라인을 더 길게 만들면 고급 분기 예측 변수의 필요성이 증가합니다.
보시다시피 지점 예측 변수를 사용하지 않을 이유가 없는 것 같습니다.
이 데모에서는 Branch Predictor의 기본적인 부분을 명확하게 설명합니다.이러한 gif가 귀찮을 경우 답변에서 삭제해 주십시오.방문자는 BranchPredictorDemo에서 라이브 데모 소스 코드를 얻을 수도 있습니다.
분기 예측 이득!
브런치의 잘못 판단해도 프로그램이 느려지지 않는다는 것을 이해하는 것이 중요합니다.빗나간 예측의 비용은 마치 분기 예측이 존재하지 않고 식을 평가하여 실행할 코드를 결정하기를 기다리는 것과 같습니다(자세한 설명은 다음 단락에서 참조).
if (expression)
{
// Run 1
} else {
// Run 2
}
언제 어디서든if-else\switch스테이트먼트. 식을 평가하여 실행할 블록을 결정해야 합니다.컴파일러에 의해 생성된 어셈블리 코드에는 조건부 분기 명령이 삽입된다.
분기 명령은 컴퓨터가 다른 명령 시퀀스의 실행을 시작하도록 할 수 있으며, 따라서 명령을 순서대로 실행하는 기본 동작에서 벗어날 수 있습니다(즉, 표현식이 거짓일 경우 프로그램은 다음 명령의 코드를 건너뜁니다).ifblock)은 어떤 조건에 따라 달라지는데, 이것은 우리의 경우 표현 평가이다.
즉, 컴파일러는 실제로 평가되기 전에 결과를 예측하려고 합니다.명령어가 로부터 취득됩니다.if블록, 그리고 그 표현이 사실로 밝혀지면, 훌륭해!평가하는데 걸리는 시간을 단축하고 코드를 진행했습니다.잘못된 코드를 실행하고 있지 않으면 파이프라인이 플러시되고 올바른 블록이 실행됩니다.
시각화:
예를 들어 1번 또는 2번 도로를 선택해야 한다고 합시다.파트너가 지도를 체크하기를 기다리면 ##에서 멈추고 기다리거나 route1을 선택할 수 있습니다.또한 운이 좋으면(route1이 올바른 경로입니다), 파트너가 지도를 체크할 때까지 기다리지 않아도 됩니다(map을 체크하는 데 걸리는 시간을 절약할 수 있었습니다).그렇지 않으면 되돌립니다.
파이프라인 플러싱은 매우 빠르지만, 요즘은 이런 도박을 할 가치가 있다.정렬된 데이터 또는 느리게 변화하는 데이터를 예측하는 것이 빠른 변화를 예측하는 것보다 항상 쉽고 좋습니다.
O Route 1 /-------------------------------
/|\ /
| ---------##/
/ \ \
\
Route 2 \--------------------------------
ARM에서는 모든 명령에는 4비트 조건 필드가 있으며 프로세서 상태 레지스터에서 발생할 수 있는 16가지 다른 조건 중 하나를 테스트(비용 없이)하기 때문에 명령 조건이 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
하지만 이것은 사실 더 큰 그림의 일부입니다.
CMPopcodes는 프로세서 상태 레지스터(PSR)의 상태 비트를 항상 갱신합니다.이는 opcodes의 목적이기 때문입니다.다만, 그 외의 대부분의 명령에서는, 옵션의 추가가 없는 한 PSR에 액세스 할 수 없습니다.S명령어 접미사를 사용하여 명령어 결과에 따라 PSR을 업데이트해야 함을 지정합니다.4비트 조건 서픽스와 마찬가지로 PSR에 영향을 주지 않고 명령을 실행할 수 있는 것은 ARM 상의 브랜치의 필요성을 줄이는 메커니즘이며 하드웨어 레벨에서의 오순서 디스패치를 용이하게 합니다.상태 비트를 갱신하는 조작X 를 실행한 후에는 (또는 병렬로) 다수의 명령을 실행할 수 있기 때문입니다.상태 비트에 명시적으로 영향을 주지 않아야 하는(또는 영향을 받지 않아야 하는) 작업. 그러면 X에 의해 이전에 설정된 상태 비트 상태를 테스트할 수 있습니다.
조건 테스트 필드와 옵션인 "상태 비트 설정" 필드를 조합할 수 있습니다.다음은 예를 제시하겠습니다.
ADD R1, R2, R3실행하다R1 = R2 + R3상태 비트를 업데이트하지 않습니다.ADDGE R1, R2, R3는 상태 비트에 영향을 준 이전 명령에서 Greater than 또는 Equal 상태가 발생한 경우에만 동일한 동작을 수행합니다.ADDS R1, R2, R3추가 실행 후 업데이트 합니다.N,Z,C그리고.V결과가 Negative, Zero, Carried(부호가 없는 추가의 경우) 또는 oVerflowed(서명이 있는 추가의 경우) 중 어느 쪽인지에 따라 프로세서 상태 레지스터에 플래그가 표시됩니다.ADDSGE R1, R2, R3가 추가되는 것은, 다음의 경우뿐입니다.GEtest는 true이며 이후 추가 결과에 따라 상태 비트를 업데이트합니다.
대부분의 프로세서 아키텍처에는 특정 동작에 대해 상태 비트를 갱신할 필요가 있는지 여부를 지정하는 기능이 없습니다.이 기능은 상태 비트를 저장 및 복원하기 위해 추가 코드를 작성해야 하거나 추가 분기를 필요로 하거나 프로세서의 고장난 실행 효율을 제한할 수 있습니다.m의 부작용 중 하나입니다.ost CPU 명령 집합 아키텍처는 대부분의 명령 후에 강제로 상태 비트를 업데이트하기 때문에 어떤 명령을 서로 간섭하지 않고 병렬로 실행할 수 있는지 구분하기가 훨씬 어렵습니다.상태 비트를 업데이트하면 부작용이 발생하므로 코드에 선형화 효과가 있습니다.어떤 명령에서도 분기 없는 상태 테스트를 조합할 수 있는 ARM의 기능은 명령 후 상태 비트를 업데이트할지 여부에 관계없이 어셈블리 언어 프로그래머와 컴파일러 모두에 매우 강력하며 매우 효율적인 코드를 생성합니다.
분기할 필요가 없는 경우에는 짧은 분기에 대한 파이프라인 플러싱에 소요되는 시간 비용을 피할 수 있으며 여러 가지 형태의 투기적 평가의 설계 복잡성을 피할 수 있습니다.최근에 발견된 많은 프로세서의 취약성(Spectre 등)에 대한 완화 조치의 초기 순진한 구현이 성능에 미치는 영향을 보면 최신 프로세서의 성능이 복잡한 추측성 평가 논리에 얼마나 의존하는지 알 수 있습니다.파이프라인이 짧고 브런치의 필요성이 대폭 감소했기 때문에 ARM은 CISC 프로세서만큼 투기적 평가에 의존할 필요가 없습니다.(물론 하이엔드 ARM 구현에는 투기적 평가가 포함되지만 퍼포먼스 사례의 일부입니다.)
ARM이 왜 이렇게 경이적인 성공을 거두었는지 궁금하다면, 이 두 메커니즘의 뛰어난 효과와 상호 작용(산술 연산자의 두 가지 원칙 중 하나를 왼쪽 또는 오른쪽으로 "배럴 시프트"하거나 메모리 액세스 연산자를 추가 비용 없이 오프셋할 수 있는 다른 메커니즘과 결합)이 이 이야기의 큰 부분을 차지합니다.이는 ARM 아키텍처 효율성의 가장 큰 원천 중 하나이기 때문입니다.1983년 ARM ISA의 오리지널 디자이너인 스티브 퍼버와 로저(현 소피) 윌슨의 탁월함은 아무리 강조해도 지나치지 않습니다.
나뭇가지 예측에 관한 것입니다.그것은 무엇일까요?
분기 예측 변수는 현대 아키텍처에서 여전히 관련성을 찾는 고대 성능 개선 기술 중 하나입니다.단순한 예측 기술은 빠른 검색과 전력 효율을 제공하지만, 오보율이 높아 어려움을 겪고 있습니다.
한편, 복잡한 분기 예측(신경 기반 또는 2단계 분기 예측의 변형)은 더 나은 예측 정확도를 제공하지만, 더 많은 전력을 소비하고 복잡성은 기하급수적으로 증가합니다.
또, 복잡한 예측 기술에서는, 브랜치를 예측하는데 걸리는 시간 자체가, 실제 브랜치의 실행 시간에 버금가는, 2 사이클에서 5 사이클에 이르는 매우 긴 시간이 됩니다.
브랜치 예측은 본질적으로 최적화(최소화)의 문제로, 가능한 한 최저의 미스 레이트, 저소비 전력, 및 최소한의 자원으로의 저복잡도 달성에 중점을 두고 있습니다.
브런치에는 3가지 종류가 있습니다.
순방향 조건부 분기 - 런타임 조건에 따라 PC(프로그램 카운터)가 명령 스트림에서 순방향 주소를 가리키도록 변경됩니다.
역방향 조건부 분기 - PC가 명령 스트림에서 역방향으로 가리키도록 변경됩니다.분기는 루프의 끝에 있는 테스트에서 루프가 다시 실행되어야 한다고 명시되어 있는 경우 프로그램루프의 선두로 거꾸로 분기하는 등의 조건에 근거하고 있습니다.
Unconditional branchs - 점프, 프로시저 호출 및 특정 조건이 없는 반환이 포함됩니다.예를 들어, 무조건 점프 명령은 어셈블리 언어로 단순 "jmp"로 코딩될 수 있으며, 명령 스트림은 즉시 점프 명령에 의해 지적된 목표 위치로 향해야 하는 반면, "jmpne"로 코딩될 수 있는 조건부 점프는 명령 스트림을 재연결할 수 있습니다.앞의 "정확한" 명령의 두 값은 값이 같지 않음을 나타냅니다.(x86 아키텍처에서 사용되는 세그먼트 어드레싱 스킴은 점프가 "근접" (세그먼트 내) 또는 "멀리" (세그먼트 외) 중 하나이기 때문에 복잡성이 증가합니다.각 유형은 분기 예측 알고리즘에 다른 영향을 미칩니다.)
정적/동적 분기 예측:마이크로프로세서에 의해 조건부 분기가 처음 마주쳤을 때 정적 분기 예측이 사용되며, 조건부 분기 코드의 후속 실행에 동적 분기 예측이 사용된다.
참고 자료:
분기 예측(웨이백 머신 사용)
분기 예측이 느려질 수 있다는 사실 외에도 정렬된 배열에는 다음과 같은 또 다른 이점이 있습니다.
값을 확인하는 대신 정지 조건을 설정할 수 있습니다.이렇게 하면 관련 데이터만 루프하고 나머지는 무시합니다.
분기 예측이 한 번만 빗나갑니다.
// 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];
}
정렬된 배열은 분기 예측이라고 하는 현상으로 인해 정렬되지 않은 배열보다 빠르게 처리됩니다.
분기 프레딕터는 (컴퓨터 아키텍처에서) 분기가 어느 방향으로 갈지를 예측하여 명령 파이프라인의 흐름을 개선하려고 하는 디지털 회로입니다.회로/컴퓨터는 다음 단계를 예측하여 실행합니다.
예측을 잘못하면 이전 단계로 돌아가서 다른 예측을 실행하게 됩니다.예측이 맞다고 가정하면 코드는 다음 단계로 넘어갑니다.예측이 잘못되면 올바른 예측이 발생할 때까지 동일한 단계를 반복하게 됩니다.
당신의 질문에 대한 답은 매우 간단합니다.
정렬되지 않은 배열에서는 컴퓨터가 여러 번 예측하므로 오류가 발생할 가능성이 높아집니다.반면 정렬된 배열에서는 컴퓨터가 예측을 적게 하므로 오류 발생 가능성이 줄어듭니다.더 많은 예측을 하려면 더 많은 시간이 필요합니다.
정렬된 어레이: 스트레이트 로드
____________________________________________________________________________________
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
정렬되지 않은 어레이: 곡선 도로
______ ________
| |__|
분기 예측:어느 길이 직선인지 추측/예측하여 확인하지 않고 따라가는 것
___________________________________________ Straight road
|_________________________________________|Longer road
두 도로는 같은 목적지에 도착하지만 직선도로가 더 짧고 다른 도로는 더 깁니다.다른 쪽을 잘못 선택하면 되돌아갈 수 없기 때문에 더 긴 길을 선택하면 시간이 낭비됩니다.이것은 컴퓨터에서 일어나는 것과 비슷하며, 저는 이것이 여러분이 더 잘 이해하는데 도움이 되었기를 바랍니다.
또, 코멘트로부터 @Simon_Weaver를 인용하고 싶습니다.
예측 수를 줄이는 것이 아니라 잘못된 예측을 줄이는 것입니다.여전히 루프를 통해 각 시간을 예측해야 합니다...
MacBook Pro (Intel i7, 64비트, 2.4GHz)에서 MATLAB 2011b에서 다음 MATLAB 코드에 대해 동일한 코드를 사용해 보았습니다.
% 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배 느립니다.즉, (분기 예측의) 효과는 MATLAB 구현의 경우 1.46배, C 구현의 경우 2.7배입니다.
데이터를 정렬해야 한다는 다른 답변의 가정은 올바르지 않습니다.
다음 코드는 전체 어레이를 정렬하지 않고 200개의 요소 세그먼트만 정렬하므로 가장 빠르게 실행됩니다.
k-element 섹션만 정렬하면 선형 시간 내에 전처리가 완료됩니다.O(n)대신,O(n.log(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;
}
또, 정렬 순서등의 알고리즘의 문제와는 전혀 관계가 없는 것을 「증명」하고 있습니다.이것은 분기 예측입니다.
이 질문에 대한 Bjarne Stroustrup의 답변:
면접 질문 같네요.그게 사실인가요?네가 어떻게 알겠니?먼저 일부 측정을 수행하지 않고 효율에 대한 질문에 대답하는 것은 좋지 않으므로 측정하는 방법을 아는 것이 중요합니다.
100만 정수의 벡터로 시도해보니
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 ");
}
적어도 이 컴파일러, 표준 라이브러리 및 옵티마이저 설정에서는 이 현상은 현실적입니다.구현에 따라 답변이 다를 수 있습니다.실제로 누군가가 보다 체계적인 연구(빠른 웹 검색에서 찾을 수 있음)를 실시했고, 대부분의 구현에서 그 효과가 나타납니다.
1가지 이유는 분기 예측입니다.소트 알고리즘의 키 조작은 다음과 같습니다.“if(v[i] < pivot]) …”또는 이에 상당합니다.정렬된 시퀀스의 경우 검정이 항상 참인 반면 랜덤 시퀀스의 경우 선택한 분지가 랜덤하게 달라집니다.
또 다른 이유는 벡터가 이미 정렬되어 있으면 요소를 올바른 위치로 이동할 필요가 없기 때문입니다.이 작은 디테일의 효과는 우리가 본 대여섯 가지 요인이다.
QuickSort(및 일반적으로 정렬)는 컴퓨터 공학에서 가장 뛰어난 지성을 끌어모은 복잡한 연구입니다.양호한 정렬 함수는 적절한 알고리즘을 선택하고 구현 시 하드웨어 성능에 주의를 기울인 결과입니다.
효율적인 코드를 작성하려면 기계 아키텍처에 대해 조금 알아야 합니다.
이 질문은 CPU의 분기 예측 모델에 뿌리를 두고 있습니다.나는 이 신문을 읽는 것을 추천한다.
복수의 브랜치 예측과 브랜치주소 캐시를 통한 명령 페치 레이트 향상(그러나 오늘날 실제 CPU는 Haswell을 제외하고 클럭 사이클마다 여러 번 브랜치 예측을 실행하지 않고 나중에 루프 버퍼에서 작은 루프를 효과적으로 언롤링합니다).최신 CPU는 다수의 브런치를 예측하여 연속되는 대규모 블록에서 페치를 사용할 수 없습니다.)
요소를 정렬하면 분기 예측은 경계선을 제외하고 정확하게 예측하기 쉬우므로 명령이 CPU 파이프라인을 효율적으로 흐를 수 있으므로 잘못된 예측에 대해 올바른 경로를 되감거나 선택할 필요가 없습니다.
빠르고 간단한 이해를 위한 답변(자세한 내용은 다른 항목 참조)
이 개념을 분기 예측이라고 합니다.
분기 예측은 코드가 확실하게 알려지기 전에 취할 경로를 예측하는 최적화 기술입니다.코드 실행 중에 기계는 여러 개의 코드 문을 프리페치하여 파이프라인에 저장하기 때문에 이것은 중요합니다.
이 문제는 실행할 수 있는 경로 또는 코드의 일부가 2개 있는 조건부 분기에서 발생합니다.
예측이 들어맞았을 때 최적화 기법은 성공했습니다.
예측이 거짓일 경우 쉽게 설명하면 파이프라인에 저장된 코드문이 잘못되었음을 증명하고 실제 코드를 완전히 새로고침해야 하므로 많은 시간이 소요됩니다.
상식적으로 알 수 있듯이, 정렬된 것에 대한 예측은 정렬되지 않은 것에 대한 예측보다 훨씬 더 정확하다.
분기 예측 시각화:
정렬했다
정렬되어 있지 않다
정렬된 어레이의 처리가 정렬되지 않은 어레이의 처리보다 빠른 이유는 무엇입니까?
코드의 예:
// CPP program to demonstrate processing
// time of sorted and unsorted array
#include <iostream>
#include <algorithm>
#include <ctime>
using namespace std;
const int N = 100001;
int main()
{
int arr[N];
// Assign random values to array
for (int i=0; i<N; i++)
arr[i] = rand()%N;
// for loop for unsorted array
int count = 0;
double start = clock();
for (int i=0; i<N; i++)
if (arr[i] < N/2)
count++;
double end = clock();
cout << "Time for unsorted array :: "
<< ((end - start)/CLOCKS_PER_SEC)
<< endl;
sort(arr, arr+N);
// for loop for sorted array
count = 0;
start = clock();
for (int i=0; i<N; i++)
if (arr[i] < N/2)
count++;
end = clock();
cout << "Time for sorted array :: "
<< ((end - start)/CLOCKS_PER_SEC)
<< endl;
return 0;
}
실행 시기:
결론:
정렬된 어레이를 처리하는 데 걸리는 시간이 정렬되지 않은 어레이에 비해 적다는 점에 유의하십시오.정렬된 배열에 대해 이러한 최적화가 이루어지는 이유는 분기 예측입니다.
지점 예측이란 무엇입니까?
컴퓨터 아키텍처에서 분기 예측은 프로그램의 명령 파이프라인에 있는 조건부 분기(점프)가 실행될 가능성이 있는지 여부를 결정하는 데 초점을 맞춥니다.현재 명령이 실행되기 전에 가져올 주소 필드를 추측해야 하므로 모든 파이프라인 프로세서는 어떤 방식으로든 분기 예측을 수행합니다.
위의 경우 지점 예측이 어떻게 적용되지 않는가?
if 조건에서는 arr[i] < 5000 이 확인되지만 정렬된 배열의 경우 5000 을 넘으면 항상 false 상태가 되고 그 전에는 항상 true가 됩니다.CPU는 이 패턴을 인식하여 추측을 잘못하여 되감기를 할 필요가 없이 조건부 브랜치 다음에 실행할 명령을 올바르게 예측할 수 있습니다.
분기 예측 알고리즘 작업:
분기 예측은 알고리즘이 따르는 패턴 또는 기본적으로 이전 단계에서 실행된 이력에 대해 작동합니다.추측이 맞으면 CPU는 실행을 계속하고 오류가 발생하면 파이프라인을 플러시하여 브랜치로 롤백하고 처음부터 재시작해야 합니다.
언급URL : https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array
'programing' 카테고리의 다른 글
| adroid.content.res를 클릭합니다.Resources$NotFoundException:문자열 리소스 ID #0x0 (0) | 2022.07.14 |
|---|---|
| logger(log4j)에 대한 추가 프로그램을 찾을 수 없습니다. (0) | 2022.07.14 |
| Vue JS에서 열린 그래프 메타 태그가 이미지를 표시하지 않음 (0) | 2022.07.14 |
| Vuex - 바인딩 도우미의 동적 네임스페이스(mapState, ...) (0) | 2022.07.14 |
| Android의 MVC 패턴 (0) | 2022.07.06 |