java 퀵정렬 왜 분류되지 않은 배열보다 정렬 된 배열을 처리하는 것이 더 빠릅니까?




정렬 영어 (17)

매우 특이한 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)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}
  • std::sort(data, data + arraySize); 없이 std::sort(data, data + arraySize); 코드는 11.54 초 만에 실행됩니다.
  • 정렬 된 데이터로 코드는 1.93 초 만에 실행됩니다.

처음에는 이것이 언어 또는 컴파일러 예외 일 수 있다고 생각했습니다. 그래서 나는 자바로 시도했다.

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)
        {
            // Primary loop
            for (int c = 0; c < arraySize; ++c)
            {
                if (data[c] >= 128)
                    sum += data[c];
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

다소 유사하지만 덜 극단적 인 결과.

나의 첫 번째 생각은 정렬이 캐시에 데이터를 가져 왔지만 어레이가 방금 생성 되었기 때문에 이것이 얼마나 어리석은 것인지 생각했습니다.

  • 무슨 일 이니?
  • 왜 분류되지 않은 배열보다 정렬 된 배열을 처리하는 것이 더 빠릅니까?
  • 이 코드는 몇 가지 독립적 인 용어를 요약 한 것이며 순서는 중요하지 않습니다.

분기 예측 이득!

분기 예측이 프로그램을 느리게하지 않는다는 것을 이해하는 것이 중요합니다. 누락 된 예측의 비용은 분기 예측이 존재하지 않는 것과 마찬가지로 표현식의 평가가 실행될 코드를 결정하기를 기다렸던 것과 같습니다 (다음 단락에서 추가 설명).

if (expression)
{
    // Run 1
} else {
    // Run 2
}

if-else\ switch문 이있을 때마다 표현식을 평가하여 어떤 블록을 실행해야하는지 결정해야합니다. 컴파일러에 의해 생성 된 어셈블리 코드에는 조건부 branch 명령어가 삽입됩니다.

브랜치 명령은 컴퓨터가 다른 명령 시퀀스를 실행하기 시작하게하여 명령을 실행하는 기본 동작 (즉, 표현식이 거짓이면 프로그램이 if블록 의 코드를 건너 뜁니다)에서 벗어나는 경우가 발생할 수 있습니다. 우리의 경우 표현식 평가.

즉, 컴파일러는 실제로 평가되기 전에 결과를 예측하려고합니다. if블록 에서 지시를 가져오고 , 표현이 사실이라면, 훌륭합니다! 우리는 코드를 평가하는 데 걸린 시간을 얻었으며 코드에서 진전을 이루었습니다. 그렇지 않은 경우 잘못된 코드가 실행되고 파이프 라인이 플러시되고 올바른 블록이 실행됩니다.

심상:

경로 1 또는 경로 2를 선택해야한다고 가정 해 봅시다. 파트너가지도를 확인하기를 기다렸다가 ##에서 멈추고 기다렸거나 route1을 선택하고 운이 좋다면 (경로 1이 올바른 경로 임) 그때 당신은 파트너가지도를 확인하기를 기다릴 필요가 없었습니다 (지도를 확인하기 위해 데려 간 시간을 절약했습니다). 그렇지 않으면 되돌릴 수 있습니다.

파이프 라인을 플러시하는 것이 매우 빠르지 만, 요즘이 도박을하는 것은 가치가 있습니다. 정렬 된 데이터 또는 천천히 변화하는 데이터를 예측하는 것은 빠른 변경을 예측하는 것보다 항상 쉽고 빠릅니다.

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------

분기 예측 오류를 방지하는 한 가지 방법은 조회 테이블을 작성하고 데이터를 사용하여 색인을 생성하는 것입니다. 스테판 드 브루 인 (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 문을 사용하는 버전보다 무작위 데이터가 훨씬 빠릅니다.

그러나 내 테스트에서 명시 적 조회 테이블은 약간 더 빨랐습니다. 아마도 조회 테이블에 대한 인덱싱이 비트 이동보다 약간 빠르기 때문일 수 있습니다. 이 코드는 내 코드가 설정되고 조회 테이블을 사용하는 방법을 보여줍니다 (코드 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문 을 사용하는 대신 배열로 인덱싱하는 기술 을 사용하여 사용할 포인터를 결정할 수 있습니다. 두 라이브러리를 구현 한 라이브러리를 보았습니다. 대신 두 개의 명명 된 포인터 ( pLeftpRight기타)가 포인터의 길이 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


분기 예측으로 인해 속도가 느려지는 것 외에도 정렬 된 배열은 또 다른 장점이 있습니다.

값을 확인하는 대신 중지 조건을 설정하여 관련 데이터를 반복 만하고 나머지는 무시할 수 있습니다.
분기 예측은 한 번만 누락됩니다.

 // sort backwards (higher values first)
 std::sort(data, data + arraySize, std::greater<int>());

 for (unsigned c = 0; c < arraySize; ++c) {
       if (data[c] < 128) {
              break;
       }
       sum += data[c];               
 }

데이터가 정렬 될 때 성능이 크게 향상되는 이유는 의 대답에서 아름답게 설명 된 것처럼 분기 예측 패널티가 제거된다는 것입니다.

자, 코드를 보면

if (data[c] >= 128)
    sum += data[c];

이 특별한 if... else... branch의 의미는 조건이 만족 될 때 뭔가를 추가하는 것입니다. 이러한 유형의 분기는 조건부 이동 명령문으로 쉽게 변환 할 수 있습니다.이 명령문은 x86 시스템에서 조건부 이동 명령 인 cmovl 로 컴파일됩니다. 브랜치와 따라서 잠재적 브랜치 예측 패널티가 제거됩니다.

C 에서 C++ 과 같이, (최적화없이) x86 의 조건부 이동 명령어로 직접 컴파일하는 명령문은 삼항 연산자입니다 ... ? ... : ... ... ? ... : ... 그래서 우리는 위의 문장을 동일한 문장으로 다시 작성합니다 :

sum += data[c] >=128 ? data[c] : 0;

가독성을 유지하면서 속도 향상 요소를 확인할 수 있습니다.

Intel Core i7 -2600K @ 3.4GHz 및 Visual Studio 2010 릴리스 모드에서 벤치 마크는 다음과 같습니다 (형식이 Mysticial에서 복사 됨).

x86

//  Branch - Random
seconds = 8.885

//  Branch - Sorted
seconds = 1.528

//  Branchless - Random
seconds = 3.716

//  Branchless - Sorted
seconds = 3.71

x64

//  Branch - Random
seconds = 11.302

//  Branch - Sorted
 seconds = 1.830

//  Branchless - Random
seconds = 2.736

//  Branchless - Sorted
seconds = 2.737

결과는 여러 테스트에서 강력합니다. 분기 결과가 예측할 수 없을 때 큰 속도 향상을 얻을 수 있지만 예측할 수있을 때 약간의 어려움이 있습니다. 사실, 조건부 이동을 사용할 때 성능은 데이터 패턴에 관계없이 동일합니다.

이제 그들이 생성하는 x86 어셈블리를 조사해 보겠습니다. 간단히하기 위해 max1max2 두 함수를 사용합니다.

max1if... 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 포함하지 않는다는 것입니다. jmp 는 예측 된 결과가 옳지 않을 경우 상당한 성능 저하를 초래합니다.

조건부 이동이 더 좋은 이유는 무엇입니까?

일반적인 x86 프로세서에서 명령어 실행은 여러 단계로 나뉩니다. 대략적으로, 우리는 다른 단계를 다룰 다양한 하드웨어를 가지고 있습니다. 따라서 우리는 새로운 명령을 시작하기 위해 하나의 명령이 끝날 때까지 기다릴 필요가 없습니다. 이를 pipelining 이라고합니다.

분기의 경우 다음 명령은 앞의 명령에 의해 결정되므로 파이프 라인을 수행 할 수 없습니다. 우리는 기다리거나 예측해야합니다.

조건부 이동의 경우 실행 조건부 이동 명령은 여러 단계로 나뉘지만 FetchDecode 와 같은 초기 단계는 이전 명령의 결과에 종속되지 않습니다. 후반 단계에서만 결과가 필요합니다. 따라서 우리는 하나의 명령어 실행 시간의 일부만 기다립니다. 이것은 조건부 이동 버전이 예측이 쉬운 분기보다 느린 이유입니다.

Computer Systems : A Programmer 's Perspective, 2 판 에서 자세히 설명합니다. 조건부 이동 명령어에 대해서는 3.6.6 절을, 프로세서 아키텍처에 대해서는 4 장 전체, 분기 예측 및 예측 불이행에 대해서는 특별한 처리를 위해 섹션 5.11.2를 확인할 수 있습니다.

경우에 따라 일부 현대 컴파일러는 더 나은 성능으로 어셈블리에 코드를 최적화 할 수 있지만 경우에 따라 일부 컴파일러는 Visual Studio의 네이티브 컴파일러를 사용할 수 없습니다. 예측할 수없는 분기 및 조건부 이동 간의 성능 차이를 알면 시나리오가 복잡 해져서 컴파일러가 자동으로 최적화 할 수 없을 때 더 나은 성능으로 코드를 작성할 수 있습니다.


의심 할 여지없이 우리 중 일부는 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) 행은 cachegrind의 분기 예측 모델 아래에서 예측 오류 분기점 (Bcm)을 164,050,007 발생시키는 반면, 정렬 된 버전에서는 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)
...

자세한 내용 은 성능 자습서 를 참조하십시오.


그건 확실합니다!...

분기 예측 은 코드에서 발생하는 전환으로 인해 로직이 느리게 실행되도록합니다! 마치 곧바로 길을가는 길과 많은 길목이있는 길을가는 것과 같습니다.

배열이 정렬 된 경우 첫 번째 단계에서 조건은 false data[c] >= 128가되고 거리의 끝까지가는 전체 값이됩니다. 이것이 논리의 끝까지 빠르게 도달하는 방법입니다. 반면 정렬되지 않은 배열을 사용하면 코드를 더 느리게 실행할 수 있도록 터닝 및 처리가 많이 필요합니다.

아래에서 내가 당신을 위해 만든 이미지를보십시오. 어느 거리가 더 빨리 끝날 것입니까?

그래서 프로그래밍 방식으로, 분기 예측 은 프로세스가 느려지 게 만듭니다 ...

또한 결국에는 각기 다른 방식으로 코드에 영향을 미칠 두 종류의 분기 예측이 있음을 알면 좋습니다.

1. 정적

2. 동적

정적 분기 예측은 조건부 분기가 처음 발견 될 때 마이크로 프로세서에 의해 사용되며 동적 분기 예측은 조건 분기 코드의 후속 실행에 사용됩니다.

이러한 규칙을 효과적으로 활용하도록 코드를 작성 하려면 if-else 또는 switch 문을 작성할 때 가장 일반적인 경우를 먼저 확인하고 점차적으로 가장 일반적인 것으로 확인하십시오. 루프 반복자의 조건 만 정상적으로 사용되기 때문에 루프는 정적 분기 예측을 위해 특수한 코드 순서를 반드시 요구하지는 않습니다.


정렬 된 배열은 분기 예측이라고하는 현상으로 인해 정렬되지 않은 배열보다 빠르게 처리됩니다.

분기 예측기는 분기가 어느 방향으로 갈 것인지 예측하려고하는 디지털 회로 (컴퓨터 아키텍처)로, 명령 파이프 라인의 흐름을 개선합니다. 회로 / 컴퓨터는 다음 단계를 예측하고 실행합니다.

잘못된 예측을하면 이전 단계로 돌아가고 다른 예측으로 실행됩니다. 예측이 정확하다고 가정하면 코드는 다음 단계로 계속 진행됩니다. 잘못된 예측은 올바른 예측이 발생할 때까지 동일한 단계를 반복합니다.

귀하의 질문에 대한 답변은 매우 간단합니다.

정렬되지 않은 배열에서 컴퓨터는 여러 예측을 수행하여 오류 가능성을 높입니다. 반면 정렬 된 컴퓨터는 오류 확률을 줄이는 예측을 적게 만듭니다. 더 많은 예측을하려면 더 많은 시간이 필요합니다.

정렬 된 배열 : 직선 도로

____________________________________________________________________________________
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

정렬되지 않은 배열 : 곡선 도로

______   ________
|     |__|

분기 예측 : 어떤 도로가 직선인지 추측 / 예측하고 확인없이 추적

___________________________________________ Straight road
 |_________________________________________|Longer road

두 도로가 같은 목적지에 도착하더라도 직선 도로가 짧아지고 다른 도로가 길어집니다. 실수로 다른 하나를 선택하면 되돌릴 수 없으므로 긴 도로를 선택하면 시간이 더 많이 걸립니다. 이것은 컴퓨터에서 일어나는 것과 유사하며, 이것이 당신이 더 잘 이해하는 데 도움이되기를 바랍니다.

업데이트 : @Simon_Weaver가 말한 바에 따르면, 나는 또 다른 사실을 추가하고 싶다. "예측이 적지 않아 부정확 한 예측이 줄어들고 루프를 통해 매번 예측해야한다."


C ++에서 자주 사용되는 부울 연산은 컴파일 된 프로그램에서 많은 분기를 생성합니다. 이러한 분기가 루프 내부에 있고 예측하기가 어렵다면 실행이 크게 느려질 수 있습니다. 부울 변수는 및 for 값 0을 갖는 8 비트 정수로 저장됩니다 .false1true

부울 변수는 입력으로 부울 변수가있는 모든 연산자가 입력이 다른 값을 가지면 확인합니다. 01, 부울을 출력으로 갖는 연산자는 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. 컴파일러가 이러한 가정을하지 않는 이유는 변수가 초기화되지 않았거나 알 수없는 출처에서 나온 경우 변수가 다른 값을 가질 수 있기 때문입니다. 위의 코드는 유효한 값으로 초기화 된 경우 ab부울 출력을 생성하는 연산자에서 나온 경우 최적화 될 수 있습니다 . 최적화 된 코드는 다음과 같습니다.

char a = 0, b = 1, c, d;
c = a & b;
d = a | b;

char대신 부울 연산자 ( 및 ) 대신 bool비트 연산자 ( &|) 를 사용할 수 있도록하기 위해 대신 사용됩니다 . 비트 연산자는 단 하나의 클록 사이클을 취하는 단일 명령어입니다. 는 OR 연산자 ( ) 경우에도 작동 및 이외의 값을 가지고 나 . AND 연산자 ( )와 EXCLUSIVE OR 연산자 ( 피연산자가 아닌 다른 값을 가질 경우) 일치 결과를 얻을 수있다 와 .&&|||ab01&^01

~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, &것입니다). 마찬가지로 a || b대체 될 수없는 a | b경우 b경우 평가 안되는 표현 a이다 true.

비트 연산자를 사용하는 것이 피연산자가 변수 인 경우 피연산자가 비교 인 경우보다 유리합니다.

bool a; double x, y, z;
a = x > y && z < 5.0;

대부분의 경우에 최적입니다 ( &&표현식에서 많은 분기 오보를 생성 하지 않는다면 ).


당신은 지점 예측 의 희생자입니다.

지점 예측이란 무엇입니까?

철도 교차점을 고려하십시오.

Mecanismo의 , 위키 미디어 커먼즈를 통해. CC-BY-SA 3.0 라이센스 하에서 사용됩니다.

논쟁을 위해서, 이것이 장거리 또는 무선 통신을하기 전인 1800 년대로 돌아 간다고 가정 해보십시오.

당신은 교차점의 운영자이고 기차가 오는 것을 듣습니다. 어떤 방향으로 가야할지 모르실 겁니다. 당신은 운전자에게 그들이 원하는 방향을 묻기 위해 열차를 멈춘다. 그런 다음 스위치를 적절하게 설정합니다.

기차는 무겁고 많은 관성이 있습니다. 그래서 그들은 시작하고 천천히 걸릴 영원히 가져 가라.

더 좋은 방법이 있습니까? 기차가 어느 방향으로 가는지 알 것입니다!

  • 당신이 옳은 것을 짐작하면 계속됩니다.
  • 잘못 추측 한 경우, 선장은 멈추고 백업하고 스위치를 뒤집을 것입니다. 그런 다음 다른 경로를 다시 시작할 수 있습니다.

매번 바르게 추측 하면 열차가 멈추지 않아도됩니다.
너무 자주 잘못 생각 하면 열차가 멈추고, 백업하고, 재시작하는 데 많은 시간을 할애 할 것입니다.

if 문을 고려하십시오 . 프로세서 수준에서 분기 명령입니다.

당신은 프로세서이고 지점을 볼 수 있습니다. 어떤 방향으로 나아갈 지 전혀 모릅니다. 너 뭐하니? 실행을 중단하고 이전 지시가 완료 될 때까지 대기합니다. 그런 다음 올바른 경로를 계속 진행합니다.

최신 프로세서는 복잡하고 긴 파이프 라인을 가지고 있습니다. 그래서 그들은 영원히 "워밍업"과 "천천히"걸립니다.

더 좋은 방법이 있습니까? 어떤 방향으로가는 지 짐작할 수 있습니다!

  • 당신이 옳은 것을 짐작하면, 당신은 계속해서 실행합니다.
  • 잘못 추측 한 경우 파이프 라인을 비우고 지점으로 롤백해야합니다. 그런 다음 다른 경로를 다시 시작할 수 있습니다.

매번 바르게 추측 하면 실행을 멈출 필요가 없습니다.
너무 자주 잘못 생각한 경우 많은 시간을 연기하고, 롤백하고 다시 시작하는 데 소비합니다.

이는 분기 예측입니다. 기차가 깃발을 들고 방향을 알려줄 수 있기 때문에 가장 유추하지는 않습니다. 그러나 컴퓨터에서 프로세서는 지점이 마지막 순간까지 어느 방향으로 갈지 알지 못합니다.

그렇다면 열차가 다른 길을 되돌아 가야하는 횟수를 최소화하기 위해 전략적으로 어떻게 생각하십니까? 당신은 과거사를 봐요! 열차가 시간의 99 %를 남겨두면 왼쪽으로 추측합니다. 대체하는 경우 추측을 번갈아 수행합니다. 그것이 3 번에 한 번가는다면, 당신은 같은 것을 추측합니다 ...

즉, 패턴을 식별하고이를 따르려고합니다. 이것은 분기 예측 자의 작동 방식을 어느 정도 나타냅니다.

대부분의 응용 프로그램은 잘 작동하는 분기를가집니다. 따라서 현대 분기 예측자는 일반적으로 90 %를 초과하는 적중률을 달성합니다. 그러나 예측할 수없는 패턴이없는 예측할 수없는 분기점에 직면 할 때 분기 예측기는 사실상 쓸모가 없습니다.

더 읽을 거리 : Wikipedia의 "Branch predictor"기사 .

위에서 암시 된 것처럼 범인은 if-statement입니다.

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, 133, ...
branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T,   N  ...

       = TTNTTTTNTNNTTTN ...   (completely random - hard to predict)

그래서 무엇을 할 수 있습니까?

컴파일러가 분기를 조건부 이동으로 최적화 할 수없는 경우 성능을 위해 가독성을 희생하려는 경우 해킹을 시도 할 수 있습니다.

바꾸다:

if (data[c] >= 128)
    sum += data[c];

와:

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

이렇게하면 분기가 제거되고 일부 분기 연산으로 바뀝니다.

(이 해킹은 원래 if 문과 엄격하게 동일하지는 않지만이 경우 data[] 의 모든 입력 값에 유효합니다.)

벤치 마크 : Core i7 920 @ 3.5 GHz

Visual Studio 2010 - x64 출시

//  Branch - Random
seconds = 11.777

//  Branch - Sorted
seconds = 2.352

//  Branchless - Random
seconds = 2.564

//  Branchless - Sorted
seconds = 2.587

Java - Netbeans 7.1.1 JDK 7 - x64

//  Branch - Random
seconds = 10.93293813

//  Branch - Sorted
seconds = 5.643797077

//  Branchless - Random
seconds = 3.113581453

//  Branchless - Sorted
seconds = 3.186068823

관찰 :

  • 지점으로 : 정렬 된 데이터와 정렬되지 않은 데이터간에 큰 차이가 있습니다.
  • 해킹 : 정렬 된 데이터와 정렬되지 않은 데이터에는 차이가 없습니다.
  • C ++의 경우 해킹은 실제로 데이터가 정렬 될 때 분기보다 느립니다.

일반적인 경험적 규칙은 중요한 루프에서 데이터 종속 분기를 피하는 것입니다. (이 예와 같이)

최신 정보:

  • x64에서 -O3 또는 -ftree-vectorize 하는 GCC 4.6.1은 조건부 이동을 생성 할 수 있습니다. 따라서 정렬 된 데이터와 정렬되지 않은 데이터간에 차이는 없습니다. 둘 다 빠릅니다.

  • VC ++ 2010에서는 /Ox 아래 /Ox 분기에 대한 조건부 이동을 생성 할 수 없습니다.

  • 인텔 컴파일러 11은 기적적인 일을합니다. 두 개의 루프를 상호 교환 함으로써 예측할 수없는 분기를 외부 루프로 끌어 올립니다. VC ++와 GCC가 생성 할 수있는 것보다 2 배 빠릅니다! 즉, ICC는 벤치 마크를 이기기 위해 테스트 루프를 활용했습니다 ...

  • 인텔 컴파일러에 브랜치리스 코드를 주면 바로 오른쪽 벡터 라이 제이션을 수행하고 브랜치 (루프 교환 포함)만큼 빠릅니다.

이것은 성숙한 현대 컴파일러조차도 코드 최적화 능력이 크게 달라질 수 있다는 것을 보여줍니다 ...


이미 다른 사람들이 언급 한 바와 같이, 신비의 배후에는 지점 예측 자 (Branch Predictor)가 있습니다.

나는 뭔가를 추가하려하지 않고 개념을 다른 방식으로 설명하려고합니다. wiki에는 텍스트와 다이어그램이 포함 된 간결한 소개가 있습니다. 직감적으로 Branch Predictor를 정교화하기 위해 다이어그램을 사용하는 아래의 설명이 마음에 든다.

컴퓨터 아키텍처에서 브랜치 예측자는 브랜치 (예 : if-then-else 구조)가 확실하게 알려지기 전에 어떤 방향으로 갈 것인지를 추측하는 디지털 회로입니다. 분기 예측기의 목적은 명령 파이프 라인의 흐름을 개선하는 것입니다. 분기 예측기는 x86과 같은 많은 최신 파이프 라인 형 마이크로 프로세서 아키텍처에서 높은 성능을 달성하는 데 중요한 역할을합니다.

양방향 분기는 대개 조건부 점프 명령으로 구현됩니다. 조건부 점프는 조건부 점프 직후에 첫 번째 코드 분기로 실행되지 않거나 "take"될 수 있고 코드의 두 번째 분기가있는 프로그램 메모리의 다른 위치로 점프 할 수 있습니다 저장된. 조건이 계산되고 조건 점프가 명령 파이프 라인의 실행 단계를 통과 할 때까지 조건 점프가 수행되는지 여부는 확실하지 않습니다 (그림 1 참조).

설명 된 시나리오에 기반하여 필자는 다양한 상황에서 파이프 라인에서 명령이 어떻게 실행되는지 보여주기 위해 애니메이션 데모를 작성했습니다.

  1. 지점 예측 자없이.

분기 예측이 없으면 프로세서는 조건부 점프 명령이 실행 단계를 통과 할 때까지 대기해야만 다음 명령이 파이프 라인의 페치 단계에 들어갈 수 있습니다.

이 예제에는 세 가지 명령어가 포함되어 있으며 첫 번째 명령어는 조건부 점프 명령어입니다. 후자의 두 명령은 조건부 점프 명령이 실행될 때까지 파이프 라인으로 들어갈 수 있습니다.

3 개의 명령이 완료되기까지 9 클럭 사이클이 소요됩니다.

  1. Branch Predictor를 사용하고 조건부 점프를하지 마십시오. 예측이 조건부 점프를 취하지 않는다고 가정 해 봅시다 .

3 개의 명령이 완료 될 때까지 7 클럭 사이클이 소요됩니다.

  1. Branch Predictor를 사용하고 조건부 점프를하십시오. 예측이 조건부 점프를 취하지 않는다고 가정 해 봅시다 .

3 개의 명령이 완료되기까지 9 클럭 사이클이 소요됩니다.

분기 오보의 경우 낭비되는 시간은 가져 오기 단계에서 실행 단계까지 파이프 라인의 단계 수와 같습니다. 최신 마이크로 프로세서는 파이프 라인이 상당히 길어서 예측 오류 지연이 10 ~ 20 클럭주기가되는 경향이 있습니다. 결과적으로, 파이프 라인을 길게 만드는 것은보다 진보 된 분기 예측 자에 대한 요구를 증가시킵니다.

보시다시피 Branch Predictor를 사용하지 않는 이유가없는 것으로 보입니다.

Branch Predictor의 가장 기본적인 부분을 명확하게 보여주는 데모입니다. 이러한 gif가 성가신 경우 답장에서 자유롭게 삭제하십시오. 방문객은 git 에서 데모를 얻을 수도 있습니다.git


방금이 질문과 답변을 읽었으며 대답이 누락되었다고 생각합니다.

관리되는 언어에서 특히 잘 작동하는 것으로 발견 된 분기 예측을 제거하는 일반적인 방법은 분기를 사용하는 대신 테이블 조회입니다 (이 경우 테스트하지는 않았지만).

이 방법은 일반적으로 다음과 같은 경우에 사용할 수 있습니다.

  1. 작은 테이블이며 프로세서에 캐시 될 가능성이 큽니다.
  2. 매우 빡빡한 루프에서 일을하고 있거나 프로세서가 데이터를 미리로드 할 수 있습니다.

배경 및 이유

파 퓨. 도대체 도대체 무슨 소리 야?

프로세서 관점에서 볼 때 메모리가 느립니다. 속도의 차이를 보완하기 위해 프로세서 (L1 / L2 캐시)에있는 두 개의 캐시에서이를 보완합니다. 그래서 당신이 당신의 좋은 계산을하고 있고 당신이 기억의 조각을 필요로한다는 것을 이해한다고 상상해보십시오. 프로세서는 '로드'연산을 수행하고 캐시에 메모리 조각을로드 한 다음 캐시를 사용하여 나머지 계산을 수행합니다. 메모리가 비교적 느리기 때문에이 '로드'는 프로그램 속도를 저하시킵니다.

분기 예측과 마찬가지로, 이것은 펜티엄 프로세서에서 최적화되었습니다. 프로세서는 데이터 조각을로드해야하며 캐시에 실제로로드되기 전에 캐시에로드하려고 시도합니다. 이미 살펴본 바와 같이, 분기 예측은 때로는 끔찍하게 잘못됩니다. 최악의 시나리오에서는 돌아가서 실제로 메모리로드가 필요할 때까지 기다려야합니다. 즉, 영원히 걸릴 것입니다 ( 즉, 분기 예측 실패, 메모리 부족 분기 예측이 실패한 후 부하가 끔찍합니다! ).

다행스럽게도 우리에게 메모리 액세스 패턴이 예측 가능한 경우 프로세서는 빠른 캐시에로드하므로 모두 정상입니다.

가장 먼저 알아야 할 것은 작은 것 입니까? 일반적으로 크기가 더 작은 것이 좋지만 일반적으로 크기가 4096 바이트 미만인 조회 테이블을 사용하는 것이 좋습니다. 상한으로 : 조회 테이블이 64K보다 큰 경우 재검토 가치가 있습니다.

테이블 만들기

그래서 우리는 작은 테이블을 만들 수 있다는 것을 알아 냈습니다. 다음으로 할 일은 조회 기능을 제자리에 놓는 것입니다. 조회 함수는 일반적으로 몇 가지 기본 정수 연산 (및 또는, xor, shift, add, remove 및 아마도 곱하기)을 사용하는 작은 함수입니다. 조회 기능을 통해 테이블의 '고유 키'에 대한 귀하의 의견을 번역하고 싶다면 원하는 모든 작업에 대한 답변을 제공하면됩니다.

이 경우 :> = 128은 값을 유지할 수 있음을 의미하고 <128은 제거한다는 의미입니다. 가장 쉬운 방법은 'AND'를 사용하는 것입니다 : 우리가 그것을 지키면 7FFFFFFF와 AND합니다. 우리가 그것을 제거하고 싶다면 0과 함께합니다. 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 rnd = new Random(0);
for (int c = 0; c < arraySize; ++c)
    data[c] = rnd.Next(256);

//To keep the spirit of the code in-tact 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();

이 질문은 여러 번 이미 훌륭하게 답변되었습니다. 여전히 흥미로운 또 다른 분석에 그룹의 관심을 끌고 싶습니다.

최근에이 예제 (약간 수정)는 Windows에서 프로그램 자체 내에서 코드 조각을 프로파일 링하는 방법을 보여주기위한 방법으로도 사용되었습니다. 그 과정에서 저자는 정렬 된 & 정렬되지 않은 경우에서 코드가 대부분의 시간을 보내는 곳을 결정하기 위해 결과를 사용하는 방법을 보여줍니다. 마지막으로 HAL (Hardware Abstraction Layer)의 약간 알려진 기능을 사용하여 정렬되지 않은 경우에 얼마나 많은 분기 예측 오류가 발생 하는지를 확인하는 방법을 보여줍니다.

링크는 http://www.geoffchappell.com/studies/windows/km/ntoskrnl/api/ex/profile/demo.htm


위의 동작은 분기 예측 때문에 발생합니다.

분기 예측을 이해하려면 먼저 명령어 파이프 라인을 이해해야합니다 .

모든 명령어는 일련의 단계로 분리되어 서로 다른 단계를 동시에 병렬로 실행할 수 있습니다. 이 기술은 명령 파이프 라인 (command pipeline)으로 알려져 있으며, 이는 최신 프로세서의 처리량을 높이는 데 사용됩니다. 더 잘 이해하려면 Wikipedia의 예제 를 참조하십시오 .

일반적으로 최신 프로세서는 상당히 긴 파이프 라인을 가지고 있지만, 쉽게이 4 단계만을 고려해 보겠습니다.

  1. IF - 메모리에서 명령 가져 오기
  2. ID - 명령 디코드
  3. EX - 명령 실행
  4. 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의 결과에 의존하기 때문에 프로세서는 파이프 라인에서 EX 단계까지 명령 A가 도달하지 않을 때까지 기다려야합니다. 따라서 파이프 라인 이렇게 보일거야.

조건이 true를 반환하는 경우 :

조건이 거짓을 반환하는 경우 :

명령 A의 결과를 기다린 결과 위의 경우 (분기 예측없이 true 또는 false 모두에 대해 사용 된) 총 CPU 사이클은 7입니다.

분기 예측이란 무엇입니까?

분기 예측자는 분기 (if-then-else 구조)가 확실하게 알려지기 전에 어떤 방식으로 진행되는지 추측하려고합니다. 명령 A가 파이프 라인의 EX 단계에 도달 할 때까지 기다리지 않고 결정을 추측하여 해당 명령으로 이동합니다 (예에서는 B 또는 C).

정확한 추측의 경우 파이프 라인은 다음과 같이 보입니다.

나중에 추측이 잘못되었다고 판단되면 부분적으로 실행 된 명령어는 폐기되고 파이프 라인은 올바른 분기로 시작되어 지연이 발생합니다. 분기 오보의 경우 낭비되는 시간은 가져 오기 단계에서 실행 단계까지 파이프 라인의 단계 수와 같습니다. 최신 마이크로 프로세서는 파이프 라인이 상당히 길어서 예측 오류 지연이 10 ~ 20 클럭주기가되는 경향이 있습니다. 파이프 라인이 길수록 양호한 분기 예측 자의 필요성이 커 집니다.

OP의 코드에서 처음으로 조건부 분기 예측자는 예측을 기반으로하는 정보가 없으므로 처음으로 임의로 다음 명령어를 선택합니다. 나중에 for 회 돌이에서, 그것은 역사에 대한 예측을 기반으로 할 수있다. 오름차순으로 정렬 된 배열의 경우 세 가지 가능성이 있습니다.

  1. 모든 요소가 128보다 작습니다.
  2. 모든 요소가 128보다 큽니다.
  3. 일부 새로운 시작 요소는 128보다 작 으면 나중에 128보다 커집니다.

먼저 예측자가 항상 첫 번째 실행에서 실제 분기를 가정한다고 가정 해 보겠습니다.

그래서 첫 번째 경우에는 역사적으로 모든 예측이 정확하기 때문에 언제나 진정한 가지를 취할 것입니다. 두 번째 경우에는 처음에는 잘못 예측되지만 몇 번 반복하면 올바르게 예측됩니다. 세 번째 경우에는 요소가 128보다 작아 질 때까지 처음에 올바르게 예측됩니다. 이후에는 분기 예측 오류가 발생하면 시간이 지나면 오류가 발생합니다.

이 모든 경우에 오류가 너무 적어서 결과적으로 몇 번만 실행하면 부분적으로 실행되는 명령을 무시하고 올바른 분기로 다시 시작해야하므로 CPU주기가 줄어 듭니다.

그러나 무작위로 정렬되지 않은 배열의 경우, 부분적으로 실행 된 명령어를 버리고 예측 된 분기로 대부분 다시 시작해야하며 정렬 된 배열과 비교하여 더 많은 CPU 사이클이 필요합니다.


공식적인 대답은

  1. 인텔 - 지점 미스 비용 피하기
  2. 인텔 - 예측 불허를 방지하기위한 지점 및 루프 재구성
  3. 과학 논문 - 분기 예측 컴퓨터 아키텍처
  4. 책 : JL Hennessy, DA Patterson : 컴퓨터 아키텍처 : 정량적 접근
  5. 과학 출판물의 기사 : TYYeh, YN Patt은 분기 예측에 대해 많은 것을 만들었습니다.

이 아름다운 diagram 에서 분기 예측자가 혼란스러워하는 이유를 알 수 있습니다 .

원래 코드의 각 요소는 임의의 값입니다.

data[c] = std::rand() % 256;

따라서 예측자는 측면을 std::rand()타격 으로 바꿀 것 입니다.

반면에 일단 정렬되면 예측자는 먼저 강하게 취해지지 않은 상태로 이동하고 값이 높은 값으로 변경되면 예측자가 3 단계로 진행하여 강하게 잡히지 않은 상태에서 강하게 수행 된 상태로 변경됩니다.


그것은 분기 예측에 관한 것입니다. 이게 뭐야?

  • 분기 예측기는 현대 아키텍처와 관련성이 높은 고대 성능 향상 기술 중 하나입니다. 간단한 예측 기술은 빠른 검색 및 전력 효율성을 제공하지만 높은 예측 오류율로 인해 어려움을 겪습니다.

  • 반면, 복잡한 분기 예측 - 신경 기반 또는 2 수준 분기 예측의 변형 -은 더 나은 예측 정확도를 제공하지만 더 많은 전력과 복잡성을 기하 급수적으로 증가시킵니다.

  • 이 외에도 복잡한 예측 기술에서 분기를 예측하는 데 걸리는 시간 자체가 2 ~ 5 사이클로 매우 높습니다. 이는 실제 분기의 실행 시간과 비슷합니다.

  • 분기 예측은 본질적으로 최소 가능한 누락 률, 낮은 전력 소비 및 최소의 자원으로 낮은 복잡성을 달성하는 데 중점을두고있는 최적화 (최소화) 문제입니다.

실제로 가지의 3 개의 다른 종류가있다 :

조건부 분기 전 방향 - 런타임 조건에 따라 PC (프로그램 카운터)가 변경되어 명령 스트림의 전방 주소를 가리 킵니다.

하위 조건부 분기 - PC가 명령 스트림에서 역방향을 가리 키도록 변경됩니다. 브랜치는 루프의 끝에서 테스트를 수행하면 루프를 다시 실행해야한다고 프로그램 루프의 시작 부분으로 뒤로 분기하는 것과 같은 일부 조건을 기반으로합니다.

무조건 분기 - 여기에는 특정 조건이없는 점프, 프로 시저 호출 및 반환이 포함됩니다. 예를 들어, 무조건 점프 명령은 단순히 어셈블리 언어로 "jmp"로 코딩 될 수 있으며, 명령 스트림은 점프 명령이 가리키는 대상 위치로 즉시 지정되어야하며 반면에 "jmpne" 이전의 "비교"명령에서 두 값을 비교 한 결과 값이 같지 않음을 나타내는 경우에만 명령 스트림을 리디렉션합니다. (x86 아키텍처에서 사용하는 세그먼트 화 된 주소 지정 체계는 점프가 세그먼트 내에서 "가까운"또는 "멀리"(세그먼트 외부) 일 수 있기 때문에 복잡성을 추가합니다. 각 유형은 분기 예측 알고리즘에 다른 영향을줍니다.

정적 / 동적 분기 예측 : 정적 분기 예측은 조건부 분기가 처음 발견 될 때 마이크로 프로세서에 의해 사용되고 동적 분기 예측은 조건 분기 코드의 후속 실행에 사용됩니다.

참고 문헌 :


정렬 된 경우 성공적으로 분기 예측이나 분기없는 비교 기법을 사용하는 것보다 더 효율적으로 수행 할 수 있습니다. 분기를 완전히 제거합니다.

실제로 배열은 인접한 영역 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;(a 진정으로 균일 한 분포, 기대치 191.5 16,384 샘플을 가정) :-)


배열이 정렬 될 때 데이터가 0에서 255 사이로 분산되기 때문에 반복의 처음 절반은 if 구문을 입력하지 않습니다 ( if 문은 아래에서 공유 됨).

if (data[c] >= 128)
    sum += data[c];

질문 : 정렬 된 데이터의 경우처럼 위의 명령문이 특정 경우 실행되지 않는 이유는 무엇입니까? 여기에 "분기 예측 자"가옵니다. 브랜치 예측자는 브랜치 (예 : if-then-else 구조)가 확실하게 알려지기 전에 어떤 방향으로 갈 것인지 추측하려고 시도하는 디지털 회로입니다. 분기 예측기의 목적은 명령 파이프 라인의 흐름을 개선하는 것입니다. 지점 예측자는 높은 효율을 달성하는 데 중요한 역할을합니다!

더 나은 이해를 위해 벤치 마킹을 해보 죠.

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

" 잘못된 "진실한 거짓 패턴은 if" 좋은 "패턴 보다 6 배나 더 느린 구문을 만들 수 있습니다 ! 물론 어떤 패턴이 좋고 어떤 패턴이 나쁜지는 컴파일러와 특정 프로세서에서 생성 된 정확한 명령어에 달려 있습니다.

따라서 분기 예측이 성능에 미치는 영향에 대해서는 의심의 여지가 없습니다!





branch-prediction