About_builtin_exptect
Table of Contents
Background⌗
컴퓨터 구조를 배우면서, MIPS 아키텍쳐에 대해 공부하고 있다. MIPS의 경우, pipeline을 도입하고 branch prediction을 위해 여러 방법을 사용한다고 한다. 그 방법 중 static prediction의 방법으로 해당 branch가 거짓일 경우(즉, jump를 수행하지 않는 분기)로 예상하는 방법이 존재한다고 한다.
이 방법을 보고나서 gcc의 __builtin_expect나 C++20의 likely 및 unlikely attribute가 이러한 분기 예측을 기반으로 구성되어 있는 것이 아닌가하는 생각이 들었다. 따라서 이를 간단하게 분석해보고자 하였다.
__builtin_expect⌗
GCC에서는 컴파일러에게 도움을 줄 수 있는 여러 builtin macro를 제공한다.
앞서 언급했듯, 그 중에는 __builtin_expect와 __builtin_expect_with_probability가 존재한다.
Example code & Opcodes⌗
간단한 테스트를 위해 다음과 같은 코드를 -O3 옵션으로 컴파일했다.
#include <stdio.h>
int main() {
int c;
scanf("%d", &c);
if(__builtin_expect(c != 0, 1)) {
puts("c != 0");
} else {
puts("c == 0");
}
return 0;
}
컴파일했을 때의 결과는 다음과 같다.
.text:00000000000010A0 ; int __fastcall main(int argc, const char **argv, const char **envp)
.text:00000000000010A0 public main
.text:00000000000010A0 main proc near ; DATA XREF: _start+18↓o
.text:00000000000010A0
.text:00000000000010A0 var_14 = dword ptr -14h
.text:00000000000010A0 var_10 = qword ptr -10h
.text:00000000000010A0
.text:00000000000010A0 ; __unwind {
.text:00000000000010A0 endbr64
.text:00000000000010A4 sub rsp, 18h
.text:00000000000010A8 lea rdi, unk_2004
.text:00000000000010AF mov rax, fs:28h
.text:00000000000010B8 mov [rsp+18h+var_10], rax
.text:00000000000010BD xor eax, eax
.text:00000000000010BF lea rsi, [rsp+18h+var_14]
.text:00000000000010C4 call ___isoc99_scanf
.text:00000000000010C9 mov eax, [rsp+18h+var_14]
.text:00000000000010CD test eax, eax
.text:00000000000010CF jz short loc_10F4
.text:00000000000010D1 lea rdi, s ; "c != 0"
.text:00000000000010D8 call _puts
.text:00000000000010DD
.text:00000000000010DD loc_10DD: ; CODE XREF: main+60↓j
.text:00000000000010DD mov rax, [rsp+18h+var_10]
.text:00000000000010E2 sub rax, fs:28h
.text:00000000000010EB jnz short loc_1102
.text:00000000000010ED xor eax, eax
.text:00000000000010EF add rsp, 18h
.text:00000000000010F3 retn
.text:00000000000010F4 ; ---------------------------------------------------------------------------
.text:00000000000010F4
.text:00000000000010F4 loc_10F4: ; CODE XREF: main+2F↑j
.text:00000000000010F4 lea rdi, aC0_0 ; "c == 0"
.text:00000000000010FB call _puts
.text:0000000000001100 jmp short loc_10DD
.text:0000000000001102 ; ---------------------------------------------------------------------------
.text:0000000000001102
.text:0000000000001102 loc_1102: ; CODE XREF: main+4B↑j
.text:0000000000001102 call ___stack_chk_fail
.text:0000000000001102 ; } // starts at 10A0
.text:0000000000001102 main endp
그러면 다음 코드를 컴파일하면 어떻게 될까?
#include <stdio.h>
int main() {
int c;
scanf("%d", &c);
if(__builtin_expect(c != 0, 0)) {
puts("c != 0");
} else {
puts("c == 0");
}
return 0;
}
다음과 같은 결과가 나온다.
.text:00000000000010A0 ; int __fastcall main(int argc, const char **argv, const char **envp)
.text:00000000000010A0 public main
.text:00000000000010A0 main proc near ; DATA XREF: _start+18↓o
.text:00000000000010A0
.text:00000000000010A0 var_14 = dword ptr -14h
.text:00000000000010A0 var_10 = qword ptr -10h
.text:00000000000010A0
.text:00000000000010A0 ; __unwind {
.text:00000000000010A0 endbr64
.text:00000000000010A4 sub rsp, 18h
.text:00000000000010A8 lea rdi, unk_2004
.text:00000000000010AF mov rax, fs:28h
.text:00000000000010B8 mov [rsp+18h+var_10], rax
.text:00000000000010BD xor eax, eax
.text:00000000000010BF lea rsi, [rsp+18h+var_14]
.text:00000000000010C4 call ___isoc99_scanf
.text:00000000000010C9 mov eax, [rsp+18h+var_14]
.text:00000000000010CD test eax, eax
.text:00000000000010CF jnz short loc_10F4
.text:00000000000010D1 lea rdi, s ; "c == 0"
.text:00000000000010D8 call _puts
.text:00000000000010DD
.text:00000000000010DD loc_10DD: ; CODE XREF: main+60↓j
.text:00000000000010DD mov rax, [rsp+18h+var_10]
.text:00000000000010E2 sub rax, fs:28h
.text:00000000000010EB jnz short loc_1102
.text:00000000000010ED xor eax, eax
.text:00000000000010EF add rsp, 18h
.text:00000000000010F3 retn
.text:00000000000010F4 ; ---------------------------------------------------------------------------
.text:00000000000010F4
.text:00000000000010F4 loc_10F4: ; CODE XREF: main+2F↑j
.text:00000000000010F4 lea rdi, aC0_0 ; "c != 0"
.text:00000000000010FB call _puts
.text:0000000000001100 jmp short loc_10DD
.text:0000000000001102 ; ---------------------------------------------------------------------------
.text:0000000000001102
.text:0000000000001102 loc_1102: ; CODE XREF: main+4B↑j
.text:0000000000001102 call ___stack_chk_fail
.text:0000000000001102 ; } // starts at 10A0
.text:0000000000001102 main endp
Analysis the result⌗
결과를 보면, __builtin_expect(c != 0, 1)를 사용했을 때는 jz로 분기를 하지 않으면 c != 0을 출력한다.
반면에 __builtin_expect(c != 0, 0)를 사용했을 때는 jz로 분기하지 않으면 c == 0이 출력된다.
즉, __builtin_expect를 통해 컴파일러에게 분기에 대한 예측을 제공하면 내가 예상한 대로 static branch prediction을 고려해서 실행될 것으로 예측될 블록은 점프를 하지 않고 실행할 수 있게 만든다.
Conclusion⌗
예측이 옳았다. __builtin_expect는 Static Branch Prediction을 고려해서, 예상되는 분기의 코드를 실행하기 위해 필요한 branch를 없앤다.
또한 글을 보면, 비단 static prediction에서뿐만 아니라 dynamic prediction(Branch Target Buffer를 사용한다든가 하는 방법)에서도 성능 향상을 이룰 수 있다고 한다[1].