[C++] Branchless 가 얼마나 잘 작동할까?

개요

원래는 큰 생각 없었던 부분인데 유튜브 알고리즘 덕분에 생각해 볼 자료를 가지게 되었습니다.

 

 

이곳에서 Branchless에 대한 이야기를 하고 있었습니다. 저 같은 경우 학교 컴시구에서 if 구문이 명령어로 변경되었을 시 true, false 중 한곳을 맞다고 생각하고 가정한 뒤 계산을 하다가 그 가정이 틀리게 되면 이전 계산을 중지한 뒤 새 계산을 한다는 이론을 알고 있었습니다. 그래서 if문이 없으면 더 빠르지 않을까? 하고 막연하게만 생각해 왔습니다.

 

이번 영상을 보면서 제 생각이 마냥 옳다는 게 아니라는 걸 알아내서 이번 기회에 이에 대해 한번 적어보려고 합니다. 간단한 메모용으로요.

 

 

단순 수 비교에 있어서는 Branchless 보다 컴파일러가 더 믿을만하다

영상 초입에서 나오는 문제사항으로 두 개의 int 수를 두고 이중 더 작은 수를 반환하는 작업을 하는 것입니다. 이곳에 있어서 if 문을 통한 비교 후 반환을 하는가 아니면 if 없이 반환을 하는가에 대한 검증이 있었습니다.

 

// if문을 사용한, 일반적으로 생각되는 코드
int Min_Int1(int a, int b)
{
    if(a < b)
        return a;
    else
        return b;
}

 

// if문의 사용 없이, true, false를 활용한 연산
int Min_Int3(int a, int b)
{
    return a * (a < b) + b * (b <= a);
}

 

추가적으로 영상에서는 없는 삼항 연산자를 통한 함수를 추가해 테스트를 해 봤습니다.

 

int Min_Int2(int a, int b)
{
    return (a < b) ? a :  b;
}

 

전체 코드

 

#include <iostream>
#include <chrono>
using namespace std;

int Min_Int1(int a, int b)
{
    if(a < b)
        return a;
    else
        return b;
}

int Min_Int2(int a, int b)
{
    return (a < b) ? a :  b;
}

int Min_Int3(int a, int b)
{
    return a * (a < b) + b * (b <= a);
}

constexpr int COUNT = INT32_MAX - 1;

int main()
{
    int a = 7; 
    int b = 6;

    {
        cout << "1. Use if statement\n";
        auto start = chrono::system_clock::now();

        for(int i = 0; i < COUNT; i++)
        {
            Min_Int1(a, b);
        }

        auto end = chrono::system_clock::now();
        auto duration = chrono::duration_cast<chrono::microseconds>(end - start);
        cout << duration.count() << "\n ============================\n";
    }

    {
        cout << "2. Use ternary operator\n";
        auto start = chrono::system_clock::now();

        for(int i = 0; i < COUNT; i++)
        {
            Min_Int2(a, b);
        }

        auto end = chrono::system_clock::now();
        auto duration = chrono::duration_cast<chrono::microseconds>(end - start);
        cout << duration.count() << "\n ============================\n";
    }

    {
        cout << "3. Use branchless calculation\n";
        auto start = chrono::system_clock::now();

        for(int i = 0; i < COUNT; i++)
        {
            Min_Int3(a, b);
        }

        auto end = chrono::system_clock::now();
        auto duration = chrono::duration_cast<chrono::microseconds>(end - start);
        cout << duration.count() << "\n ============================\n";
    }
}

 

결과는 if문의 승리, 컴파일러의 최적화를 기대할 수 있다!

그냥 cpu 이론을 간단하게 알고 있는 상태에서는 if문의 사용이 더 오래 걸릴 것으로 봤으나 제 환경에서는 if문이 더 빠르게 나올 수 있었습니다. 약 21억 번의 int 수 비교를 했을 때 branchless가 50% 더 느린 것을 확인할 수 있었습니다.

 

- 시간은 μs단위

	a = 5, b = 6	a = 6, b = 6	a = 7, b = 6
if	2032362	2156047	2166109
ternary operation	2452248	2236292	2237679
branchless	3166223	3113922	3113913

 

위 경우들을 시행했을 때 전부 if문이 빠르게 나옴을 알 수 있었습니다. 3항 연산자의 경우 branchless보다는 빠르게 나오지만 if문의 시간을 단 한 번도 앞지르지 못했습니다.

 

이는 영상에서도 알 수 있듯 컴파일러가 좋은 어셈블리어를 매칭해 줘서 그런 것이고 branchless의 경우 그 혜택을 받지 못한 채 더 많은 어셈블리어를 만들어 내기 때문입니다.

 

 

 

영상에서  나온 다른 Branchless는 어떨까?

근데 이건 또 아닙니다. Branchless 가 쓸모 있다는 부분을 영상에서 소개를 해 줬는데요. 그 주제는 "문자열에서 알파벳을 전부 대문자로 변경하기"였습니다. 일단 영상에서는 Branchless로 개발한 곳이 더 나은 성능을 보여준다고 합니다. 최대 7~8배 정도 빠른 속도가 나온다고 하는데요.

 

저 같은 경우 GCC 환경에서 실행했을 때 1,000,000,000자리의 string을 Branch로 변경하는 게 더 빠르게 계산되었습니다. 영상과는 확실히 다른 이야기가 되네요.

 

#include <iostream>
#include <chrono>
#include <string>
using namespace std;

string GenerateRandomString() {
    static const char alphabet[] =
        "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
        "abcdefghijklmnopqrstuvwxyz";

    string resultString;
    resultString.reserve(1000000000);

    for (int i = 0; i < 1000000000; ++i) {
        resultString += alphabet[rand() % (sizeof(alphabet) - 1)];
    }
    
    return resultString;
}

void BranchConverter(string& s)
{
    for(int i = 0; i < s.size(); i++)
    {
        if(s[i] >= 'a' && s[i] <= 'z')
        {
            s[i] -= 32;
        }
    }
}

void BranchlessConverter(string& s)
{
    for(int i = 0; i < s.size(); i++)
    {
        s[i] -= 32 * (s[i] >= 'a' && s[i] <= 'z');
    }
}

int main()
{
    {
        cout << "1. Convert with Branch\n";
        string testString = GenerateRandomString();
        auto start = chrono::system_clock::now();

        BranchConverter(testString);

        auto end = chrono::system_clock::now();
        auto duration = chrono::duration_cast<chrono::microseconds>(end - start);
        cout << duration.count() << "\n ============================\n";
    }

    {
        cout << "2. Convert with Branchless\n";
        string testString = GenerateRandomString();
        auto start = chrono::system_clock::now();

        BranchlessConverter(testString);

        auto end = chrono::system_clock::now();
        auto duration = chrono::duration_cast<chrono::microseconds>(end - start);
        cout << duration.count() << "\n ============================\n";
    }
}

 

컴파일러마다 차이가 있을까 해서 봤을 때 VS에서 실행에도 역시 Branchless가 더 늦은 속도를 보였습니다.

 

	VS Code (with GCC)	VS (C++14)	VS (C++17)
if	8038199	24729922	25337510
Branchless	8768503	29587214	29824873

 

일단 모든 경우에서 if문을 사용하는 게 더 빠르게 나오는 걸 볼 수 있었습니다. 아무래도 환경의 차이인지 영상과는 다른 결과가 나와서 당황스럽네요.

 

 

나만의 결론

일단 위 2가지 경우에서 컴파일러의 최적화에 기대는 게 더 좋은 결과를 가져온다는 걸 확인할 수 있었습니다. 또한 각 환경마다 속도가 달라질 수 있다는 걸 알게 되었으니 이를 잘 기억할 필요가 있겠습니다.

 

무조건적인 이론 숭배보다는 실제 나의 개발 환경에서 속도를 측정해 보고 사용해 보자는 생각이 더 강해지네요. 또 branchless 구문들의 경우 한 번에 보고 확 이해되지는 않고 이 수식을 이해할 필요가 있어 유지보수에 마냥 좋은 코드는 아닐 거란 생각이 듭니다.

 

마지막으로 위 영상에서 댓글을 보아하니 GPU 코드를 작성하는 데는 이런 Branchless 구문들을 많이 보게 된다는데 혹시나 이쪽 환경으로 넘어가게 된다면 잘 기억해 보도록 하겠습니다.