java - 장단점 - 정렬 알고리즘 자바



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

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

자, 코드를 보면

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의 네이티브 컴파일러를 사용할 수 없습니다. 예측할 수없는 분기 및 조건부 이동 간의 성능 차이를 알면 시나리오가 복잡 해져서 컴파일러가 자동으로 최적화 할 수 없을 때 더 나은 성능으로 코드를 작성할 수 있습니다.

https://src-bin.com

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

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

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

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

Answer #1

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

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

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

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

Answer #2

의심 할 여지없이 우리 중 일부는 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)
...

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


Answer #3

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

원래 루프로 시작 :

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 배 빠릅니다.


Answer #4

분기 예측 이득!

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

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

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

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

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

심상:

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

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

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

Answer #5

분기 예측.

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


Answer #6

공식적인 대답은

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

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

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

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

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

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


Answer #7

그건 확실합니다!...

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

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

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

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

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

1. 정적

2. 동적

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

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


Answer #8

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

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

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

Answer #9

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

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

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


Answer #10

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

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

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

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

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

정렬 된 배열 : 직선 도로

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

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

______   ________
|     |__|

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

___________________________________________ Straight road
 |_________________________________________|Longer road

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

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


Answer #11

ARM에는 모든 명령어가 0 비트 비용으로 테스트되는 4 비트 조건 필드를 갖고 있기 때문에 분기가 필요하지 않습니다. 이렇게하면 짧은 분기가 필요하지 않으므로 분기 예측 히트가 발생하지 않습니다. 따라서 정렬 된 추가 버전의 오버 헤드로 인해 정렬 된 버전이 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

Answer #12

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


Answer #13

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

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

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





branch-prediction