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



10 Answers

분기 예측.

정렬 된 배열을 사용하면 조건 data[c] >= 128 이 값 줄무늬에 대해 처음 false 가되고 이후의 모든 값에 대해 true 가됩니다. 그것은 예측하기 쉽습니다. 정렬되지 않은 배열을 사용하면 분기 비용을 지불하게됩니다.

java c++ performance optimization branch-prediction

매우 특이한 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);
    }
}

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

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

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



이 코드에서 더 많은 최적화를 할 수 있는지 궁금하신 분은 다음을 고려하십시오.

원래 루프로 시작 :

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 루프가 실행되는 동안 if 조건이 일정하다는 것을 알 수 있으므로 if 출력을 끌어 올 수 있습니다.

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        for (unsigned i = 0; i < 100000; ++i)
        {
            sum += data[j];
        }
    }
}

그런 다음 부동 소수점 모델에서 허용하는 것으로 가정하면 내부 루프를 단일 표현식으로 축소 할 수 있습니다 (예 : / fp : throw)

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        sum += data[j] * 100000;
    }
}

그 중 하나가 이전보다 100,000 배 빠릅니다.




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

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

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

  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();



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




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

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

모든 명령어는 일련의 단계로 분리되어 서로 다른 단계를 동시에 병렬로 실행할 수 있습니다. 이 기술은 명령 파이프 라인 (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 사이클이 필요합니다.




같은 줄에서 (나는 이것이 어떤 대답으로도 강조 표시되지 않았다고 생각한다) 때로는 (특히 리눅스 커널과 같은 성능 문제가있는 소프트웨어에서) 다음과 같은 if 문을 찾을 수 있다고 언급하는 것이 좋다 :

if (likely( everything_is_ok ))
{
    /* Do something */
}

또는 유사하게 :

if (unlikely(very_improbable_condition))
{
    /* Do something */    
}

모두 likely()와는 unlikely()GCC의의 같은 것을 사용하여 정의 된 사실 매크로에있는 __builtin_expect계정으로 사용자가 제공 한 정보를 복용 상태를 선호하는 컴파일러 삽입 예측 코드를 돕기 위해. GCC는 실행중인 프로그램의 동작을 변경하거나 캐시 지우기 등과 같은 저수준 명령을 내릴 수있는 다른 내장 명령을 지원합니다 . 사용 가능한 GCC 내장 명령을 참조하는 이 설명서 를 참조하십시오 .

일반적으로 이러한 종류의 최적화는 주로 하드 실시간 응용 프로그램이나 실행 시간이 중요한 임베디드 시스템에서 발생하며 중요합니다. 예를 들어 1/10000000 번만 발생하는 오류 조건을 검사하는 경우 컴파일러에 알리지 않는 이유는 무엇입니까? 이 방법은 기본적으로 분기 예측은 조건이 거짓이라고 가정합니다.




그건 확실합니다!...

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

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

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

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

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

1. 정적

2. 동적

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

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




분기 예측 이득!

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

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

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

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

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

심상:

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

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

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



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

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

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

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

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

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

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

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

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

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

참고 문헌 :




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

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

 // 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];               
 }





Related