Branchless Computing 둘째 어셈블리

1.
프로그램 개발과 관련해서는 비전문가이지만 글을 읽으면서 어셈블리언어라는 단어를 자주 접했습니다. Branchless Programming을 설명하여서 어셈블리코드를 소개하는 경우가 많았기때문입니다. 여기에 더하여 간단히 어셈블리코드를 확인할 수 있는 Compiler Explorer라는 서비스를 확인하였기때문이기도 합니다.

Compiler Explorer is an interactive online compiler which shows the assembly output of compiled C++, Rust, Go (and many more) code.

2.
Branchless와 관련한 Before 및 After 코드가 어떻게 CPU에서 처리하는지 확인해보았습니다. 먼저 가장 단순한 코드를 예제로 보여준 Branchless programming입니다.

가장 일반적인 코드예제입니다.

void toUpper(char* d, int count)
{
  for (int i = 0; i < count; i++)
    if (d[i] >= 'a' && d[i] <= 'z')
      d[i] -= 32;
}

void toUpper(char* d, int count)

{

for (int i = 0; i < count; i++)

if (d[i] >= 'a' && d[i] <= 'z')

d[i] -= 32;

}

위 소스의 어셈블리코드입니다.

toUpper(char*, int):
        push    rbp
        mov     rbp, rsp
        mov     QWORD PTR [rbp-24], rdi
        mov     DWORD PTR [rbp-28], esi
        mov     DWORD PTR [rbp-4], 0
        jmp     .L2
.L4:
        mov     eax, DWORD PTR [rbp-4]
        movsx   rdx, eax
        mov     rax, QWORD PTR [rbp-24]
        add     rax, rdx
        movzx   eax, BYTE PTR [rax]
        cmp     al, 96
        jle     .L3
        mov     eax, DWORD PTR [rbp-4]
        movsx   rdx, eax
        mov     rax, QWORD PTR [rbp-24]
        add     rax, rdx
        movzx   eax, BYTE PTR [rax]
        cmp     al, 122
        jg      .L3
        mov     eax, DWORD PTR [rbp-4]
        movsx   rdx, eax
        mov     rax, QWORD PTR [rbp-24]
        add     rax, rdx
        movzx   eax, BYTE PTR [rax]
        lea     ecx, [rax-32]
        mov     eax, DWORD PTR [rbp-4]
        movsx   rdx, eax
        mov     rax, QWORD PTR [rbp-24]
        add     rax, rdx
        mov     edx, ecx
        mov     BYTE PTR [rax], dl
.L3:
        add     DWORD PTR [rbp-4], 1
.L2:
        mov     eax, DWORD PTR [rbp-4]
        cmp     eax, DWORD PTR [rbp-28]
        jl      .L4
        nop
        nop
        pop     rbp
        ret

toUpper(char*, int):

push rbp

mov rbp, rsp

mov QWORD PTR [rbp-24], rdi

mov DWORD PTR [rbp-28], esi

mov DWORD PTR [rbp-4], 0

jmp .L2

.L4:

mov eax, DWORD PTR [rbp-4]

movsx rdx, eax

mov rax, QWORD PTR [rbp-24]

add rax, rdx

movzx eax, BYTE PTR [rax]

cmp al, 96

jle .L3

mov eax, DWORD PTR [rbp-4]

movsx rdx, eax

mov rax, QWORD PTR [rbp-24]

add rax, rdx

movzx eax, BYTE PTR [rax]

cmp al, 122

jg .L3

mov eax, DWORD PTR [rbp-4]

movsx rdx, eax

mov rax, QWORD PTR [rbp-24]

add rax, rdx

movzx eax, BYTE PTR [rax]

lea ecx, [rax-32]

mov eax, DWORD PTR [rbp-4]

movsx rdx, eax

mov rax, QWORD PTR [rbp-24]

add rax, rdx

mov edx, ecx

mov BYTE PTR [rax], dl

.L3:

add DWORD PTR [rbp-4], 1

.L2:

mov eax, DWORD PTR [rbp-4]

cmp eax, DWORD PTR [rbp-28]

jl .L4

nop

pop rbp

ret

같은 소스를 Branchless 개념을 재정의한 코드입니다.

void toUpper_branchless(char* d, int count)
{
  for (int i = 0; i < count; i++)
    d[i] = (d[i] * !(d[i] >= 'a' && d[i] <= 'z')) + (d[i] - 32) * (d[i] >= 'a' && d[i] <= 'z');
}

void toUpper_branchless(char* d, int count)

{

for (int i = 0; i < count; i++)

d[i] = (d[i] * !(d[i] >= 'a' && d[i] <= 'z')) + (d[i] - 32) * (d[i] >= 'a' && d[i] <= 'z');

}

역시 어셈블리코드입니다.

toUpper_branchless(char*, int):
        push    rbp
        mov     rbp, rsp
        mov     QWORD PTR [rbp-24], rdi
        mov     DWORD PTR [rbp-28], esi
        mov     DWORD PTR [rbp-4], 0
        jmp     .L2
.L8:
        mov     eax, DWORD PTR [rbp-4]
        movsx   rdx, eax
        mov     rax, QWORD PTR [rbp-24]
        add     rax, rdx
        movzx   eax, BYTE PTR [rax]
        mov     ecx, eax
        mov     eax, DWORD PTR [rbp-4]
        movsx   rdx, eax
        mov     rax, QWORD PTR [rbp-24]
        add     rax, rdx
        movzx   eax, BYTE PTR [rax]
        cmp     al, 96
        jle     .L3
        mov     eax, DWORD PTR [rbp-4]
        movsx   rdx, eax
        mov     rax, QWORD PTR [rbp-24]
        add     rax, rdx
        movzx   eax, BYTE PTR [rax]
        cmp     al, 122
        jle     .L4
.L3:
        mov     eax, 1
        jmp     .L5
.L4:
        mov     eax, 0
.L5:
        mov     edx, eax
        mov     eax, ecx
        imul    eax, edx
        mov     ecx, eax
        mov     eax, DWORD PTR [rbp-4]
        movsx   rdx, eax
        mov     rax, QWORD PTR [rbp-24]
        add     rax, rdx
        movzx   eax, BYTE PTR [rax]
        movsx   eax, al
        sub     eax, 32
        mov     esi, eax
        mov     eax, DWORD PTR [rbp-4]
        movsx   rdx, eax
        mov     rax, QWORD PTR [rbp-24]
        add     rax, rdx
        movzx   eax, BYTE PTR [rax]
        cmp     al, 96
        jle     .L6
        mov     eax, DWORD PTR [rbp-4]
        movsx   rdx, eax
        mov     rax, QWORD PTR [rbp-24]
        add     rax, rdx
        movzx   eax, BYTE PTR [rax]
        cmp     al, 122
        jg      .L6
        mov     eax, 1
        jmp     .L7
.L6:
        mov     eax, 0
.L7:
        mov     edx, eax
        mov     eax, esi
        imul    eax, edx
        add     ecx, eax
        mov     eax, DWORD PTR [rbp-4]
        movsx   rdx, eax
        mov     rax, QWORD PTR [rbp-24]
        add     rax, rdx
        mov     edx, ecx
        mov     BYTE PTR [rax], dl
        add     DWORD PTR [rbp-4], 1
.L2:
        mov     eax, DWORD PTR [rbp-4]
        cmp     eax, DWORD PTR [rbp-28]
        jl      .L8
        nop
        nop
        pop     rbp
        ret

toUpper_branchless(char*, int):

push rbp

mov rbp, rsp

mov QWORD PTR [rbp-24], rdi

mov DWORD PTR [rbp-28], esi

mov DWORD PTR [rbp-4], 0

jmp .L2

.L8:

mov eax, DWORD PTR [rbp-4]

movsx rdx, eax

mov rax, QWORD PTR [rbp-24]

add rax, rdx

movzx eax, BYTE PTR [rax]

mov ecx, eax

mov eax, DWORD PTR [rbp-4]

movsx rdx, eax

mov rax, QWORD PTR [rbp-24]

add rax, rdx

movzx eax, BYTE PTR [rax]

cmp al, 96

jle .L3

mov eax, DWORD PTR [rbp-4]

movsx rdx, eax

mov rax, QWORD PTR [rbp-24]

add rax, rdx

movzx eax, BYTE PTR [rax]

cmp al, 122

jle .L4

.L3:

mov eax, 1

jmp .L5

.L4:

mov eax, 0

.L5:

mov edx, eax

mov eax, ecx

imul eax, edx

mov ecx, eax

mov eax, DWORD PTR [rbp-4]

movsx rdx, eax

mov rax, QWORD PTR [rbp-24]

add rax, rdx

movzx eax, BYTE PTR [rax]

movsx eax, al

sub eax, 32

mov esi, eax

mov eax, DWORD PTR [rbp-4]

movsx rdx, eax

mov rax, QWORD PTR [rbp-24]

add rax, rdx

movzx eax, BYTE PTR [rax]

cmp al, 96

jle .L6

mov eax, DWORD PTR [rbp-4]

movsx rdx, eax

mov rax, QWORD PTR [rbp-24]

add rax, rdx

movzx eax, BYTE PTR [rax]

cmp al, 122

jg .L6

mov eax, 1

jmp .L7

.L6:

mov eax, 0

.L7:

mov edx, eax

mov eax, esi

imul eax, edx

add ecx, eax

mov eax, DWORD PTR [rbp-4]

movsx rdx, eax

mov rax, QWORD PTR [rbp-24]

add rax, rdx

mov edx, ecx

mov BYTE PTR [rax], dl

add DWORD PTR [rbp-4], 1

.L2:

mov eax, DWORD PTR [rbp-4]

cmp eax, DWORD PTR [rbp-28]

jl .L8

nop

pop rbp

ret

위 코드를 비교한 글쓴이는 위 코드를 이렇게 비교했습니다.

branchl implementation: upon disassembly, this is very slow. Many ja (jump if above) commands.
branchless implementation: it’s not pretty and it’s way too clever (not clean code), but it’s 3x faster.

ja 명령어가 많다고 했는데.. 위 결과를 보면 ㅠㅠㅠㅠㅠ

다른 글에선 jl, jmp, jle 등과 같은 명령어를 눈여겨 보라고 합니다.Jump명령어라고 하네요. 어떻게 다른지 [Assembly] Jxx 구문 총정리에서 정리한 비교를 옮깁니다.

어셈명령어 의 미 점프 조건

JA 결과가 1보다 클 경우 점프 CF=0 and ZF=0
JAE 결과가 1보다 크거나 같을경우 점프 CF=0
JB 결과가 1보다 작을 경우 점프 CF=1
JBE 결과가 1보다 작거나 같을경우 점프 CF=1 or ZF=1
JC 캐리 플래그가 1일경우 점프 CF=1

JCXZ CX가 0일경우 점프 CX=0
JE 결과가 같을 경우 점프 ZF=1
JG 결과가 클경우 점프(signed) ZF=0 and SF=OF
JGE 결과가 크거나 같을 경우 점프 (signed) SF=OF
JL 결과가 작을 경우 점프(signed) SF != OF
JLE 결과가 작거나 같을 경우 점프 (signed) ZF=1 or SF != OF
JMP 무조건 점프 조건없음

JNA 결과가 작을 경우 점프 CF=1 or ZF=1
JNAE 결과가 작거나 같을경우 점프 CF=1
JNB 결과가 클 경우 점프 CF=0
JNBE 결과가 크거나 같을경우 점프 CF=0 and ZF=0
JNC 캐리 플래그가 0일경우 점프 CF=0
JNE 결과가 클 경우 점프 ZF=0
JNG 결과가 작을 경우 점프(signed) ZF=1 or SF != OF

JNGE 결과가 작거나 같을 경우 점프(signed) SF != OF
JNL 결과가 클 경우 점프(signed) SF=OF
JNLE 결과가 크거나 같을 경우 점프(signed) ZF=0 and SF=OF
JNO 오버 플로우 하지 않으면 점프(signed) OF=0
JNP Jump if No Parity(Parity가 뭔지 모르겠어요 ㅠ) PF=0
JNS 결과가 Signed 가 아닐때 점프(signed) SF=0
JNZ 결과가 0 이 아닐때 점프Jump if Not Zero ZF=0

JO 오버 플로우 일 경우 점프(signed) OF=1
JP Jump if Parity PF=1
JPE Jump if Parity Even PF=1
JPO Jump if Parity Odd PF=0
JS Signed 이면 점프 (signed) SF=1
JZ 0 이면 점프 ZF=1

위 설명아래에 이런 문장이 있습니다.

점프하는것이 그냥 내려오며 실행되는것보다 실행하는데 더 많은 시간을 소요하므로 코드를 정리하여 원하는 대로 점프 없이 실행되도록 하는것은 좋은 프로그래밍 연습입니다.

참고로 구글링하다 보니까 아래와 같은 글이 있네요. 좋은 프로그래머가 되는 길은 역시나 험합니다.

초보자를 위한 리버스 엔지니어링 상식 – 리버스 엔지니어링이란? 1부
초보자를 위한 리버스 엔지니어링 상식 – 리버스 엔지니어링이란? 2부
초보자를 위한 리버스 엔지니어링 상식 – 어셈블리 명령어

어찌되었든 글 마지막에 있던 아래 문장이 기억에 남습니다.

Note that it’s important to check the compiled code in order to ensure the code is actually optimal

3.
Brancless와 관련한 여러 글중 stackoverflow에 있는 Why is processing a sorted array faster than processing an unsorted array?은 Branchless와 관련한 다양한 의견을 접할 수 있습니다.

질문은 C++로 된 아래코드를 Java로 개발했을 때 “왜 비슷한 성능이 나오지 않냐”는 내용입니다.

#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)
    {
        for (unsigned c = 0; c < arraySize; ++c)
        {   // Primary loop.
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock()-start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << '\n';
    std::cout << "sum = " << sum << '\n';
}

#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)

{

for (unsigned c = 0; c < arraySize; ++c)

{ // Primary loop.

if (data[c] >= 128)

sum += data[c];

}

double elapsedTime = static_cast<double>(clock()-start) / CLOCKS_PER_SEC;

std::cout << elapsedTime << '\n';

std::cout << "sum = " << sum << '\n';

}

달린 글들이 훌륭합니다. Branchless, Branch Prediction을 주제로 많은 의견이 올라왔습니다. 재미있게 읽었습니다. 마지막 댓글중 훌륭한 프로그램머가 되려면 하드웨어를 이해하라고 조언하네요. 그러면서 아래 책을 추천합니다.

Computer Systems: A Programmer’s Perspective

구글링하시면 원문을 찾을 수 있습니다.

이 글 공유하기:

Leave a Comment 응답 취소