__builtin_expect (likely, unlikey) 설명 / 성능 차이

GCC의 __builtin_expect keyword는 분기문이 어디로 탈지 컴파일러에게 hint를 줘서, 컴파일러가 분기문 최적화를 하도록 한다. __builtin_expect가 뭔지 알아보고 __builtin_expect가 분기문 최적화를 어떻게 하고 성능 차이는 어떻게 되는지 어셈블리 코드로 알아보자.

* 확인 방법 : C 코드를 컴파일하여 생성된 RISC-V 어셈블리(assembly) 코드로 확인

__builtin_expect 관련 사항

__builtin_expect

__builtin_expect는 GCC 내장함수이다.

prototype : long __builtin_expect (long exp, long c);

if (exp) foo; 로 변환되며, 컴파일러는 exp == 0 으로 예상해서(foo() 함수를 타지 않을 것이라 예상) 분기문 최적화를 한다.


likely, unlikely

linux kernel에서는 아래와 같이 define 하여 사용한다.

#define likely(x)       __builtin_expect(!!(x), 1)
#define unlikely(x)     __builtin_expect(!!(x), 0)

[[likely]], [[unlikely]]

C++20에서 likely, unlikely attributes가 추가되었으며, syntax는 [[likely]], [[unlikely]]이다. 사용법은 GCC _butin_expect와 조금 다르나 마찬가지로 분기문이 어디로 탈지 컴파일러에게 알려주어, 컴파일러가 분기문 최적화를 한다.


분기 예측

__builtin_expect를 사용하면 컴파일러는 CPU의 정적 분기 예측에 맞춰서 최적화를 한다. 따라서 분기 예측을 간단히 알아보자.

현대 CPU는 성능을 위해 대부분 파이프라인(pipeline)을 사용하며, 이로 인해 분기문에서 파이프라인에 stall이 걸려서 성능이 감소한다. 성능 감소를 줄이기 위해 분기 예측이 사용되며, 정적 분기 예측(static branch prediction)과 동적 분기 예측(dynamic branch prediction)이 있다. 

  • 동적 분기 예측
    분기문을 탈 때마다 history를 기록하고, 분기 history를 참고하여 분기 예측 한다.
  • 정적 분기 예측
    보통 역방향 분기(backward branch)는 분기하고 순반향 분기(forward branch)는 분기하지 않는 식으로 예측한다.. 정적 분기 예측만 사용하는 CPU가 있으며, 동적 분기 예측을 사용하는 CPU는 정적 분기 예측도 같이 사용하며, 분기 history가 생성되기 전에는 정적 분기 예측을 사용한다.
분기 예측의 자세한 설명은 아래 포스팅을 참고하자.

__builtin_expect 적용 코드 비교

<C 코드>

volatile int global_variable;

int get_value(int param)
{
    int return_value;

    if (param == 1) {
        return_value = 10;
    } else {
        return_value = 20;
    }

    global_variable = 1;
    global_variable = 1;
    global_variable = 1;
    
    return return_value;
}

"global_variable = 1" 3번 반복은 단순히 dummy 명령어를 추가하기 위해서 넣은 것이다. 보통 프로그램은 위의 dummy 명령어 부분에 아무 명령어도 수행하지 않기보다는 특정 명령어를 수행하는 경우가 더 많기 때문에 위와 같이 했다. 위와 같이 dummy 명령어를 넣음으로써 어셈블리 코드의 분기 관련 부분이 조금 변경된다.

global_variable 변수에 volatile을 적용했는데, volatile을 사용하면 컴파일러는 해당 변수가 언제든 변할 수 있다는 것을 알게 되어 최적화를 하지 않는다. 위에서는 컴파일러가 최적화 하면서 dummy 명령어가 없어지지 않도록 volatile을 사용했다.

volatile의 자세한 설명은 아래 포스팅을 참고하자.
포스팅 ▶ 어셈블리로 보는 C언어 volatile keyword


<어셈블리 코드>

00000000 <get_value>:
   0:	00100793          	li	a5,1 # a5=1
   4:	02f50063          	beq	a0,a5,24 <get_value+0x24> # if(param==1) 24번지로 jump
   8:	01400513          	li	a0,20 # return_value = 20
   c:	100007b7          	lui	a5,0x10000 # a5=0x10000000                    
  10:	00100713          	li	a4,1 #a4=1
  14:	00e7a023          	sw	a4,0(a5) # 10000000 <global_variable>
                                                 # global_variable = 1
  18:	00e7a023          	sw	a4,0(a5) # global_variable = 1
  1c:	00e7a023          	sw	a4,0(a5) # global_variable = 1
  20:	00008067          	ret # 함수종료
  24:	00a00513          	li	a0,10 # return_value = 10
  28:	fe5ff06f          	j	c <get_value+0xc> # c번지로 jump

위에서 정적 분기 예측은 역방향 분기는 분기하고 순반향 분기는 분기하지 않는 것으로 예측한다고 했다. 4번지의 beq는 분기 명령어인데 조건이 맞으면 4번지에서 24번지로 분기하므로 순반향 분기이다.

순반향 분기이므로 분기하지 않는 것으로 예측해서 파이프라인에 8번지, c번지, ... 을 차례대로 채우게 된다. 그러다 나중에 분기 예측 실패가 결정되면 지금까지 채운 파이프라인을 비우고 24번지 명령어부터 다시 파이프라인을 채운다.

예컨대, SiFive E31 CPU는 5단계 파이프라인 CPU인데 분기 예측 실패시에 3 cycle penalty가 있다. 파이프라인 단계가 더 많은 CPU라면 일반적으로 penalty cycle은 더 커질 것이다.

따라서 위의 어셈블리 코드는 정적 분기 예측에 따라 분기하지 않는 것으로 예측하고 8번지(return_value = 20), c번지, ... 을 파이프라인에 넣기 때문에 "return_value = 20"을 타는 경우에 분기 예측이 성공하고 penalty cycle이 없다. 반대로 "return_value = 10"을 탄다면 이미 채운 파이프라인을 비우고 다시 명령어를 채워야 하므로 penalty cycle이 발생한다.


<C 코드>

if (param == 1) { --> if ( __builtin_expect(param == 1, 0)) { 로 수정

"param == 1"이 0이길 기대하고("return value = 20"을 타길 기대) 컴파일러가 최적화한다.

어셈블리 코드는 위와 동일하며, __builtin_expect로 의도한대로 컴파일러가 분기문 최적화를 했다.


<C 코드>

if (param == 1) { --> if ( __builtin_expect(param == 1, 1)) { 로 수정

"param == 1"이 1이길 기대하고("return value = 10"을 타길 기대) 컴파일러가 최적화한다.


<어셈블리 코드>

00000000 <get_value>:
   0:	00100793          	li	a5,1
   4:	02f51063          	bne	a0,a5,24 <get_value+0x24> # if(param!=1) 24번지로 jump
   8:	00a00513          	li	a0,10 #
   c:	100007b7          	lui	a5,0x10000
  10:	00100713          	li	a4,1
  14:	00e7a023          	sw	a4,0(a5) # 10000000 <global_variable>
  18:	00e7a023          	sw	a4,0(a5)
  1c:	00e7a023          	sw	a4,0(a5)
  20:	00008067          	ret
  24:	01400513          	li	a0,20 #
  28:	fe5ff06f          	j	c <get_value+0xc>

이전 어셈블리 코드 대비, 4번지 명령어가 변경됐고, 8번지와 24번지의 명령어가 서로 바뀌었다.

4번지의 beq는 분기 명령어인데 조건이 맞으면 4번지에서 24번지로 분기하므로 순반향 분기이다.

순반향 분기이므로 정적 분기 예측에 따라 분기하지 않는 것으로 예측하고 8번지(return_value = 10), c번지, ... 을 파이프라인에 넣기 때문에 "return_value = 10"을 타는 경우에 분기 예측이 성공하고 penalty cycle이 없다. __builtin_expect로 의도한대로 컴파일러가 분기문 최적화를 했다.


실제 적용 사례

실제로 필자가 다니는 회사에서 embedded device를 개발하는데, 개발자는 성능 path에서 분기문이 높은 확률로 어디로 탈지 알고 있기 때문에 해당 부분에 __builtin_expect를 사용해서 성능 튜닝을 한다. 회사에서 사용하는 CPU중에 하나는 동적 분기 예측은 없고 정적 분기 예측만 하는 CPU인데, __builtin_expect 사용 유무에 따라 성능 차이가 많이 난다.

그렇다면 동적 분기 예측을 하는 CPU는 __builtin_expect 사용 유무에 따라 속도 차이가 날까? 분기 history가 생성되기 전에는 정적 분기 예측을 하므로 마찬가지로 속도 차이가 있다. 그러나 분기 history가 생성되면 정적 분기 예측을 하지 않고 분기 history를 참고해서 분기 예측을 하기 때문에 정적 분기 예측에 맞춰서 분기문 최적화한 부분은 성능 차이를 만들지 않는다.

그런데 회사에서 사용하는 CPU중에 하나는 동적 분기 예측 사용을 사용하는데, __builtin_expect를 사용하면 위에서 말한 동적 분기 예측을 사용하지 않는 CPU만큼은 아니지만 성능 향상이 있다. 분기 history가 생성되기 전에는 정적 분기 예측을 하기 때문에 그럴 거라고 추측했었는데, 어셈블리 코드를 보면서 다른 부분도 있다는 것을 알게 됐다. 위의 어셈블리 코드를 보면 __builtin_expect 로 기대한 대로 타지 않으면 28번지의 j 명령어(무조건 분기)를 추가로 수행하기 때문에 더 느려진다. 즉, __builtin_expect로 분기문이 높은 확률로 어디로 탈지 컴파일러에게 알려줘서, 컴파일러는 분기할 확률이 높은 path에서 28번지의 j 명령어를 추가로 수행하지 않도록 컴파일한다.


정리

분기문이 높은 확률로 어디로 탈지 안다면, __builtin_expect를 사용해서 컴파일러에게 어디로 탈지 알려주면 컴파일러는 정적 분기 예측에 맞춰 분기문 최적화를 한다. 따라서 정적 분기 예측이 사용 될 때 성능의 이득이 있다. 동적 분기 예측을 사용하는 CPU라도 분기 history가 생성되기 전에는 정적 분기 예측이 사용되므로, 정적 분기 예측이 사용되는 경우에는 마찬가지로 성능 이득이 있고, 동적 분기 예측이 사용되는 경우라도 높은 확률로 분기하는 path에서 명령어 1개 정도가 덜 사용되어 성능에 이득이 되는 경우가 있다.

* Feedback은 언제나 환영합니다.

Comments

Post a Comment