분기 없는 코드 에서

분기 없는 코드 소개

조건문 개념에서는 조건에 따라 분기하는 명령어 계열인 jcc를 소개해요. jcc는 조건이 충족될 때만 실행 흐름을 프로그램의 다른 지점으로 옮겨요.

그런데 최신 CPU는 빠르고, 여러 명령어를 병렬로 실행할 수 있어요. CPU가 조건을 런타임에 검사하느라 기다리는 동안 모든 작업을 멈춰 세우는 것은 비용이 너무 많이 들어요.

그래서 CPU는 내부적으로 기다리지 않아요. 대신 분기 예측기를 사용해 조건의 결과를 추측하고, 예측한 경로를 _추측 실행_하기 시작해요.

예측이 맞으면 분기가 없었던 것처럼 실행이 이어져요. 반대로 예측이 틀리면 CPU는 예측한 경로에서 했던 작업을 버리고 올바른 경로에서 다시 시작해야 해요.

이것을 분기 예측 실패라고 하며, 지연을 일으키기 때문에 비용이 커요.

분기를 예측하기 어려우면 이런 예측 실패가 쌓여요. 그런 경우에는 분기를 아예 피해서 조건과 상관없이 같은 명령어가 실행되도록 하는 편이 더 나을 때가 있어요. jcc 없이 값들 중에서 선택하는 코드를 분기 없는 코드라고 해요.

코드를 구성해서 분기가 덜 일어나게 하거나, 분기가 일어나더라도 더 예측하기 쉽게 만드는 방법은 여러 가지가 있어요. 특히 x86-64는 분기 없는 코드를 작성할 때 흔히 쓰이는 두 가지 명령어 계열을 제공해요.

조건부 이동

cmovcc 명령어 계열은 특정 조건이 충족될 때만 소스 피연산자를 대상 피연산자로 복사해요. 그렇지 않으면 대상은 그대로 유지돼요.

cc 접미사는 jcc와 같은 이름 규칙을 따르고, 의미도 같아요:

규칙은 jcc와 비슷해요:

1. l과 g는 부호 있는 비교에, b와 a는 부호 없는 비교에 사용해요.
2. 접미사에 e를 더하면 같음을 포함해요.
3. 접미사에 n을 더하면 조건을 부정해요.
4. 플래그가 설정된 상태를 가리키는 변형도 있어요. 예를 들어 cmovz와 cmovc가 있어요.

rdi에 있는 부호 있는 정수의 절댓값을 rax에 반환하는 경우를 생각해 봐요. jcc로 작성하면 함수는 두 경로 중 하나를 선택해요:

abs_branch:
    mov rax, rdi
    cmp rax, 0
    jge .done
    neg rax
.done:
    ret

cmovcc로 작성하면 두 후보 값을 조건 없이 모두 계산하고, 조건부 이동이 그중 하나를 골라요:

abs_branchless:
    mov rax, rdi
    neg rax            ; rax = -rdi
    cmp rdi, 0
    cmovge rax, rdi    ; if rdi >= 0, rax = rdi
                       ; otherwise rax stays = -rdi
    ; now rax = abs(rdi)
    ret

분기 없는 버전은 항상 같은 명령어를 실행해요. 예측기가 추측할 jcc가 없어요.

cmovcc의 대상은 레지스터여야 해요. 소스는 레지스터나 메모리 위치일 수 있지만, 즉시값은 될 수 없어요.

abs_branchless:
    mov rax, rdi
    neg rax            ; rax = -rdi. `neg` sets SF = 1 if the result is negative
    cmovs rax, rdi     ; if SF = 1 (i.e., rax < 0), replace rax with rdi
                       ; otherwise rax stays = -rdi, which is non-negative
    ; now rax = abs(rdi)
    ret

조건부 설정

setcc 명령어 계열은 특정 조건이 충족되면 대상 피연산자를 1로, 그렇지 않으면 0으로 설정해요. 대상은 항상 _8비트 피연산자_예요.

cc 접미사는 jcc와 cmovcc에서와 같은 이름 규칙을 따라요. 예를 들어 setz는 ZF == 1이면 대상을 1로, 그렇지 않으면 0으로 설정해요.

대상이 8비트이기 때문에, 더 넓은 값이 필요할 때는 setcc 뒤에 movzx 명령어를 쓰는 경우가 많아요:

cmp rdi, rsi
setg al             ; al = 1 if rdi > rsi (signed), 0 otherwise
movzx eax, al       ; eax (and rax) = 1 or 0, with the upper bits cleared

비교 결과를 정수 0이나 1로 바꾸는 흔한 관용구예요.

분기 없는 코드를 사용할 때

분기 없는 코드가 항상 분기 있는 코드보다 빠른 것은 아니에요. 분기를 거의 확실하게 예측할 수 있으면 예측기가 거의 항상 맞고, jcc는 사실상 비용이 들지 않아요. 그런 분기를 대체하는 분기 없는 코드는 오히려 더 느려요. 두 후보 계산을 항상 모두 실행하기 때문이에요.

대표적인 예가 루프 카운터예요. rdi에서 시작하는 64비트 정수 rsi개를 모두 더하는 함수를 생각해 봐요:

sum_array:
    xor rax, rax
.loop:
    add rax, [rdi]
    add rdi, 8
    dec rsi
    jnz .loop          ; taken on every iteration except the last
    ret

이런 패턴이 바로 분기 예측기가 잘 처리하는 유형이라서, sum_array가 원소를 몇 개 처리하든 분기는 사실상 공짜예요.

분기 없는 코드는 분기를 예측하기 어려울 때, 또는 입력과 상관없이 일정한 실행 시간이 필요할 때 효과를 봐요.