Branch prediction(분기 예측)

개요

스택 오버 플로우를 보던 중 재밌는 글을 찾았다. 링크

Why is processing a sorted array faster than processing an unsorted array?

질문의 요지는

#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;
}

위의 코드에서 일반적인 생각으로는 

당연히 정렬을 하지 않은게 더 빠르다고 생각하기 마련인데 

테스트를 해봤는데 정렬 한게 더 빠르다고 한다.

 

나도 테스트를 해봤는데 sort를 한게 더 빨랐다.

 

실험 결과

스택오버플로우의 답변을 쭈욱 읽어보니 결론은 cpu의 branch prediction 때문이다.

 

Branch prediction

위키피디아에 따르면

분기 예측(영어: branch prediction)은 다음 실행될 조건문이 어떤 곳으로 분기할 것인지를 확실히 알게 되기 전에 
미리 추측하는 CPU 기술이다. (출저 위키피디아)

내 기억을 더듬어 보자면 컴퓨터 구조 수업때 교수님이 컴퓨터는 미래를 예측해서 분기된곳의 코드를 미리 수행해놓고 기다린다고 하셨다. 맞을 확률이 절반이나 된다고 맞으면 빠르게 수행가능하다고.

당시에는 저게 뭔소리인가 싶었는데 이제서야 이해가 간다.

 

정확히 말하면 CPU가 연산을 수행하면서 분기를 만나게 된다면 조건 값의 계산이 끝날때 까지 기다려야 한다. 그만큼의 지연이 발생한다.

그렇기때문에 CPU는 미리 조건의 값을 추론하여 미리 명령을 실행시켜놓고 기다린다.

만약 분기 예측이 맞으면 지연없이 바로 수행이 가능하고 분기 예측이 틀린 경우 다시 올바른 명령이 수행된다.

 

결론

위의 예제를 보면

 

정렬된 경우

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)

정렬되지 않은 경우

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)

 

정렬된 경우 분기 예측이 계속 적중하여 지연이 없이 수행된거고

정렬되지 않을 경우에는 분기 예측이 틀려 다시 처음부터 연산이 수행되어 시간이 지연된것이다.

 

확장

그렇다면 정렬되지 않은 데이터를 사용하면서 속도를 좀 더 빠르게 할 수 없을까?

방법은 분기(branch)되지 않게 하면 된다.

스택오버플로우의 답변을 가져오면

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

위의 코드를

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

아래 코드로 변경 할 수 있다.

이럴 경우 분기를 사용하지 않는데

위의 코드로 실행한 결과

위 : 정렬 X              아래 : 정렬 O

이러면 정렬하지 않은 경우가 빠르다.

//  Branch - Random
seconds = 11.777

//  Branch - Sorted
seconds = 2.352

//  Branchless - Random
seconds = 2.564

//  Branchless - Sorted
seconds = 2.587

출처 : stackoverflow

위의 시간들은 분기의 유무, 정렬의 유무 별로 실험한 결과이다.

 

분기를 사용하지 않는 경우가 어떠한 상황에서도 빠르게 동작하지만

 

코드 가독성을 생각하면 별로 좋은 방법 같지 않은거 같다.