C++ Devirtualization

JunTak Lee·2023년 5월 17일
cppdevirtualization
0

최근 공부를 하던 도중 문뜩 이런 생각이 들었다
'Virtual function이 Vtable을 참조하지 않고 호출될 수는 없을까?'

결론부터 말하자면 '가능하다'이다
물론 가능하긴 위해선 한가지 조건이 필요하다
'Devirtualization이 가능할 것'

사실 따지고 보면 당연한 이야기이긴 하다
Virtual function은 function에서 분기점과 같은 역할을 수행한다
즉, 올바른 function을 찾을 수 있도록 유도한다
그런데 devirtualization이 불가하다는 것은, 해당 분기점의 결과를 쉽게 알지 못한다는 것이다
해당 상황은 compile time에 연산을 수행할 수 없음을 의미하고, vtable에 의존해야 한다

이러한 상황을 배제할 경우, 아래와 같은 결과를 도출할 수 있다
Assembly의 경우 편의상 필요한 부분만을 기록하였다

  • variable = new T(); -> 객체를 동적 생성하는 부분
  • variable.print(); -> 객체의 print 함수 호출 부분

Devirtualization이 가능한 경우

아래 C++ code는 compile에 사용된 code이다

#include <iostream>

class base {
public:
    base() = default;
    virtual ~base() = default;
    virtual void print() = 0;
};

class A : public base {
public:
    A() = default;
    virtual ~A() = default;
    void print() override {
        std::cout << "A" << std::endl;
    }
};

class B : public base {
public:
    B() = default;
    virtual ~B() = default;
    void print() override {
        std::cout << "B" << std::endl;
    }
};

class C : public A, B {
public:
    C() = default;
    ~C() = default;
    void print() final {
        std::cout << "C" << std::endl;
    }
};


int main() {
    int input;
    std::cin >> input;
    base* a;

    if (input > 1) {
        a = new A();
        a->print();
        delete a;
    }
    else {
        a = new B();
        a->print();
        delete a;
    }

    a = (A*)new C();
    a->print();
    delete a;
}

GCC -O0

우선 optimization을 하지 않은 결과는 다음과 같이 나왔다
GCC-12.2 (-std=c++2b -O0)

		call    operator new(unsigned long)
        mov     rbx, rax
        mov     QWORD PTR [rbx], 0
        mov     rdi, rbx
        call    A::A() [complete object constructor]
        mov     QWORD PTR [rbp-24], rbx
        mov     rax, QWORD PTR [rbp-24]
        mov     rax, QWORD PTR [rax]
        add     rax, 16
        mov     rdx, QWORD PTR [rax]
        mov     rax, QWORD PTR [rbp-24]
        mov     rdi, rax
        call    rdx
vtable for A:
        .quad   0
        .quad   typeinfo for A
        .quad   A::~A() [complete object destructor]
        .quad   A::~A() [deleting destructor]
        .quad   A::print()

위 문맥상 rbp-24가 객체의 pointer로 보였다
따라서 위 명령어를 해석하면 객체에서 vtable을 참조하고 vtable에서 다시 print 함수를 참조한다
결과적으로 원하는 print 함수의 function address을 얻게 되면 call 한다
그렇다면 optimization을 넣으면 어떻게 될까

GCC -O3

GCC 12.2 (-std=c++2b -O3)

        call    operator new(unsigned long)
        mov     QWORD PTR [rax], OFFSET FLAT:vtable for A+16
        mov     rbx, rax
        mov     rdi, rax
        call    A::print()
vtable for A:
        .quad   0
        .quad   typeinfo for A
        .quad   A::~A() [complete object destructor]
        .quad   A::~A() [deleting destructor]
        .quad   A::print()

위 assembly에서 호출을 A::print()로 직접하는 것을 확인할 수 있다
즉, vtable을 참조하지 않는 것이다
그렇다면 다른 compiler는 어떨까

msvc도 final 키워드를 사용하면 해준다는 blog post를 찾을 수 있었다
근데 별로 싫어하는 Compiler라 그냥 패스했다
Clang의 경우 non-optimized 결과는 GCC와 비슷하다

Clang -O0

Clang 16.0.0 (-std=c++2b -O0)

        call    operator new(unsigned long)@PLT
        mov     rdi, rax
        mov     qword ptr [rbp - 32], rdi       # 8-byte Spill
        xor     esi, esi
        mov     edx, 8
        call    memset@PLT
        mov     rdi, qword ptr [rbp - 32]       # 8-byte Reload
        call    A::A() [base object constructor]
        mov     rax, qword ptr [rbp - 32]       # 8-byte Reload
        mov     qword ptr [rbp - 16], rax
        mov     rdi, qword ptr [rbp - 16]
        mov     rax, qword ptr [rdi]
        call    qword ptr [rax + 16]
vtable for A:
        .quad   0
        .quad   typeinfo for A
        .quad   A::~A() [base object destructor]
        .quad   A::~A() [deleting destructor]
        .quad   A::print()

optimize를 하지 않을 경우, vtable을 참조하여 함수를 호출한다
그렇다면 optimization level을 올리면 어떻게 될까
이 부분이 Clang에서 상당히 흥미롭다
우선 O1~O2의 경우는 다음과 같다

Clang -O1/O2

Clang 16.0.0 (-std=c++2b -O1/-O2)
(main 함수에서의 if 분기점 부분에서 약간의 차이가 발생하나, vtable과 관련되지 않아 생략하였다)

        call    operator new(unsigned long)@PLT
        mov     rbx, rax
        cmp     ebp, 2
        jl      .LBB0_2
        lea     rax, [rip + vtable for A+16]
        mov     qword ptr [rbx], rax
        mov     rdi, rbx
        call    A::print()
vtable for A:
        .quad   0
        .quad   typeinfo for A
        .quad   A::~A() [base object destructor]
        .quad   A::~A() [deleting destructor]
        .quad   A::print()

GCC와 동일하게 vtable을 참조하지 않고 함수를 직접 호출함을 확인할 수 있다
그렇다면 O3의 경우는 어떨까

Clang -O3

Clang 16.0.0 (-std=c++2b -O3)

        call    operator new(unsigned long)@PLT
        mov     rbx, rax
        cmp     ebp, 2
        jl      .LBB0_4
        lea     r15, [rip + vtable for A+16]
        mov     qword ptr [rbx], r15
        mov     r14, qword ptr [rip + std::cout@GOTPCREL]
        lea     rsi, [rip + .L.str]
        mov     edx, 1
        mov     rdi, r14
        call    std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert...
        ...
        movsx   esi, al
        mov     r14, qword ptr [rip + std::cout@GOTPCREL]
        mov     rdi, r14
        call    std::basic_ostream<char, std::char_traits<char> >::put(char)@PLT
        mov     rdi, rax
        call    std::basic_ostream<char, std::char_traits<char> >::flush()@PLT
vtable for A:
        .quad   0
        .quad   typeinfo for A
        .quad   A::~A() [base object destructor]
        .quad   A::~A() [deleting destructor]
        .quad   A::print()

그 어디에서도 A::print() 함수를 호출하지 않는다
그리고 해당 string literal이 그대로 cout으로 넘겨진다
즉, 해당 함수가 자동 inline된 것이다
그럼 더 나아가서 if 분기점을 안만들면 어떻게 될까

Clang 16.0.0 (-std=c++2b -O3)
(GCC는 위와 동일한 결과를 도출하여 생략하였다)

#include <iostream>

class base {
public:
    base() = default;
    virtual ~base() = default;

    virtual void print() = 0;
};

class A : public base {
public:
    void print() override {
        std::cout << "A" << std::endl;
    }
};

class B : public base {
public:
    void print() override {
        std::cout << "B" << std::endl;
    }
};


int main() {
    base* a;

    a = new A();
    a->print();
    delete a;

    a = new B();
    a->print();
    delete a;
}
        mov     rbx, qword ptr [rip + std::cout@GOTPCREL]
        lea     rsi, [rip + .L.str]
        mov     edx, 1
        mov     rdi, rbx
        call    std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert...
        ...
        movsx   esi, al
        mov     rdi, rbx
        call    std::basic_ostream<char, std::char_traits<char> >::put(char)@PLT
        mov     rdi, rax
        call    std::basic_ostream<char, std::char_traits<char> >::flush()@PLT

이번에는 동적 생성 과정 자체가 없어졌다..!
따라서 vtable 자체가 없다..?
위 코드가 단순한 2줄(혹은 1줄..)짜리 코드와 동일하게 바뀐 것이다
만약 위 상황과 반대로 devirtualization이 불가한 경우에는 어떨까

Devirtualization이 불가하다면?

Devirtualization이 불가한 상황을 만들기 위해 아래와 같이 code를 수정하였다
Upcasting 후 container에 담는과정에서 type에 대한 손실이 일어나기에 devirtualization이 불가한 상황이다

#include <iostream>
#include <vector>

class base {
public:
    base() = default;
    virtual ~base() = default;

    virtual void print() = 0;
};

class A : public base {
public:
    void print() override {
        std::cout << "A" << std::endl;
    }
};

class B : public base {
public:
    void print() override {
        std::cout << "B" << std::endl;
    }
};

class C : public base {
public:
    void print() override {
        std::cout << "C" << std::endl;
    }
};

class D : public base {
public:
    void print() override {
        std::cout << "D" << std::endl;
    }
};

class E : public base {
public:
    void print() override {
        std::cout << "E" << std::endl;
    }
};


int main() {
    std::vector<base*> nodes;
    for (int i = 0; i < 100; i++) {
        base* ptr;
        switch (i % 5) {
            case 0: ptr = new A(); break;
            case 1: ptr = new B(); break;
            case 2: ptr = new C(); break;
            case 3: ptr = new D(); break;
            case 4: ptr = new E(); break;
            default: ptr = nullptr;
        }
        nodes.push_back(ptr);
    }

    for (int i = 0; i < 100; i++) {
        nodes[i]->print();
    }

    for (int i = 0; i < 100; i++) {
        delete nodes[i];
    }
}

우선 GCC의 경우다
GCC와 후술할 Clang 모두 Optimization 과정에서 많이 변형되어 nodes[i]->print(); 부분만 가져왔다

GCC -Ofast

GCC 12.2 (-std=c++2b -Ofast)

.L71:
        mov     rdi, QWORD PTR [rbx]
        mov     rax, QWORD PTR [rdi]
        call    [QWORD PTR [rax+16]]
        add     rbx, 8
        cmp     r12, rbx
        jne     .L71

Clang -Ofast

Clang 16.0.0 (-std=c++2b -Ofast)

.LBB0_37:                               # =>This Inner Loop Header: Depth=1
        mov     rdi, qword ptr [r15 + 8*rbx]
        mov     rax, qword ptr [rdi]
        call    qword ptr [rax + 16]
        inc     rbx
        cmp     rbx, 100
        jne     .LBB0_37

순서와 instruction에 있어 약간의 차이를 보이지만 결국 둘 모두 동일한 동작을 수행하였다

  1. 반복문(for loop)이 끝나기 전까지 vector안에 존재하는 각 pointer를 방문
  2. 해당 pointer의 vtable을 참조하여 print 함수를 호출

위 결과를 종합하자면 다음과 같다
Compiler가 compile 과정에서 해당 pointer의 정확한 타입을 유추할 수 있다면 devirtualization이 가능, 즉 vtable이 필요하지 않다
따라서 compiler는 optimization 과정에서 자연스럽게 vtable을 참조하지 않고 함수를 호출한다
하지만 pointer의 정확한 타입을 유추할 수 없다면, devirtualization이 불가, 즉 vtable을 참조해야만 한다
그리고 이러한 판단은 compiler에 달려있다는 것을 알 수 있다

여담

Clang의 inline 같은 optimization은 devirtualization과 직접적인 관련은 없다
Devirtualization이 가능하기에 inline이 가능하고, 더 나아가 객체 생성 자체를 생략할 수 있다고 생각한다
이러한 부분은 Compiler, Instruction Set, Code의 복잡도 등 다양한 조건에 따라 언제든지 변할 수 있다
그럼에도 불구하고 devirtualization을 통해 다양한 이점이 있음을 확인할 수 있었다

여담이지만, Stack Overflow에서 어떤분은 virtual function의 성능 저하가 그다지 높지 않다고 하였다
그 분은 normal method call에 비해 약 10% 정도 증가한다고 언급하며, 신경쓰지 않아도 된다고 하였다
(글쎄..10%도 결코 적은 숫자는 아닌거 같은데..)
https://stackoverflow.com/a/23686304

추가적으로, Clang compiler가 어쩌면 굉장히 Aggressive하다고 생각한다
하지만 이러한 과정은 동일한 결과를 도출하면서 더 빠른 속도를 제공한다
더불어 C++ code는 최적화에 덜 신경쓰면서 가독성 및 유지보수성을 더 높일 수 있다고 생각한다
이러한 점에서 개인적으로 Clang의 Aggressive한 compile이 더 좋지 않나 생각한다

유용할수도 있는 링크들

위 모든 assembly code는 Compiler Explorer을 통해 생성했다
https://godbolt.org

https://stackoverflow.com/questions/12411218/optimization-of-virtual-table-lookups
https://stackoverflow.com/questions/30314645/c-devirtualization-at-runtime
https://marcofoco.com/blog/2016/10/03/the-power-of-devirtualization/

profile
JunTak Lee
하고싶은거 하는 사람
이전 포스트

Windows/macOS Keylogger

다음 포스트

C++ STL Container 성능 비교

0개의 댓글