----------------
title : Rust 의 다형성 - static 과 dynamic dispatch (C++ 을 곁들인..)
cat_title : Rust 의 다형성 - static 과 dynamic dispatch
path : /Rust
publish_date : 2021-08-15
--------------

C++ 에서 Rust 로 넘어가면서 배웠던 것들 중에서 가장 신기했던 점은 Rust 에는 상속(inheritance) 가 없다는 점이였습니다. 보통 C++ 나 Java 같은 언어들에서는 클래스의 인터페이스를 보통 Base 클래스로 삼고 (Java 의 경우 Interface 겠죠.) 각각의 클래스에서 이를 상속하면서 구현하게 됩니다.

예를 들어서 C++ 에서

```cpp-formatted
class Animal {
 public:
  virtual std::string MakeSound() const = 0;
};
```

위와 같이 가상 함수 `MakeSound` 를 제공하는 `Animal` 클래스를 생각해봅시다. 그리고 이 `Animal` 클래스를 구현하는 `Dog` 클래스를 정의합시다.

```cpp-formatted
class Dog : public Animal {
 public:
  std::string MakeSound() const override { return "멍멍"; }
};
```

물론 `Dog` 클래스가 `Animal` 클래스를 상속받지 않고, 그냥 `MakeSound` 함수 자체를 구현해도 됩니다.

```cpp-formatted
class Dog {
 public:
  std::string MakeSound() const { return "멍멍"; }
};
```

위 두 경우 모두 `Dog` 클래스에 `MakeSound` 가 정의되어 있는 것은 같습니다. 하지만 왜 굳이 `Animal` 을 상속받는 것을까요? 그 이유는 `Animal` 을 상속받는 모든 클래스들에 대해서 공통적인 인터페이스를 정의하기 위함이죠. 예를 들어서

```cpp-formatted
Animal* dog = new Dog;
dog->MakeSound();  // 멍멍

Animal* cat = new Cat;
cat->MakeSound();  // 야옹
```

위 `dog` 와 `cat` 모두 `Animal` 포인터 이지만, 각각이 실제로 무슨 클래스의 객체에냐에 따라서 올바른 `MakeSound` 함수가 호출이 되는 것입니다. 만일 `Animal` 을 상속받지 않았더라면 공통의 포인터인 `Animal*` 로 위 객체들을 가리킬 수 없겠죠.

이 처럼 `dog` 와 `cat` 모두 같은 `Animal*` 타입 이지만, 실제로 이들이 가리키는 객체가 뭐냐에 따라서 호출되는 함수가 달라지게 됩니다. **이렇게 다른 타입들에 대해서 같은 코드로 다른 일들을 수행하는 것을 다형성(Polymorphism) 이라고 합니다**. `C++/Java` 와 같은 언어에서는 이러한 다형성을 클래스의 상속을 통해서 제공하고 있습니다.

하지만 Rust 는 조금 특이하게도 다형성을 클래스의 상속 대신에 조금 다른 개념을 사용해서 제공하고 있습니다. 바로 trait 입니다.

### Trait

Rust 에서 trait 은 타입들 간에 공통의 기능들을 정의하는데 사용됩니다. [Rust book 을 인용하자면](https://doc.rust-lang.org/book/ch10-02-traits.html)

> Traits 는 다른 언어들에서 흔히 인터페이스(interface) 라고 부르는 기능들과 유사합니다만 약간의 차이가 있습니다.(Note: Traits are similar to a feature often called interfaces in other languages, although with some differences.)

trait 이란 단어를 직역하자면 **형질** 인데, 보통 어떠한 사물이나 사람이 가지는 고유의 특징들을 이야기 합니다. 예를 들어서 사람의 경우를 예시로 치자면, 키큰 사람과 키 작은 사람으로 나뉘듯이 키 높이 자체가 형질이 될 수 도 있고, 아니면 인종 역시 형질이 될 수 있습니다.

Rust 에서는 타입들에게 이러한 형질들을 부여할 수 있습니다.

먼저 trait 을 정의하는 방법은 간단합니다. 예를 들어서 위 C++ 예시를 trait 으로 만든다면

```rust
trait Animal {
  fn make_sound(&self) -> String;
}
```

처럼 표현할 수 있겠죠. 설명하자면 `Animal` 이라는 형질을 가지는 타입은 반드시 `make_sound` 함수를 리턴해야 된다는 의미 입니다.

그럼 `Dog` 라는 타입에 `Animal trait` 을 붙이기 위해서는 아래와 같이 `impl` 을 통해서 `Dog` 타입에 `Animal` 을 구현하기만 하면 됩니다.

```rust
impl Animal for Dog {
  fn make_sound(&self) -> String {
    "멍멍".to_string()
  }
}
```

C++ 의 경우 클래스의 정의 자체에 무엇을 상속하는지 반드시 명시되어 있어야 합니다. 만일 `Dog` 클래스에 `Animal` 클래스와 `Pet` 클래스를 모두 추가하고 싶다면

```cpp-formatted
class Dog : public Animal, public Pet {};
```

과 같이 정의해야죠. 따라서 타입을 보면 어떠한 형질들을 가지는지 쉽게 알 수 있습니다. 하지만, 클래스에 다른 형질을 부여하고 싶다면, 해당 클래스를 추가로 상속 해야 합니다. 만일 기존에 만들어진 타입을 바꿀 수 없다면, 새로운 클래스를 만드는 수 밖에 없습니다. 반면에 Rust 의 경우는 정 반대로,

```rust
impl Pet for Dog {}
impl Cute for Dog {}
```

와 같이 타입에 내가 원하는 trait 들을 **붙일 수 있습니다**. \sidenote{엄밀히 이야기 하자면 아무 타입들에나 trait 들을 구현할 수 있는 것은 아닙니다. *Orphan rule* 에 따르면 타입이나 trait 둘 중 하나는 반드시 해당 crate 에 정의되어 있어야 합니다. 만일 해당 crate 에 타입과 trait 둘 다 정의되어 있지 않는 경우 wrapper 을 사용해서 이 규칙을 우회하는 방법이 있습니다. 자세한 내용은 [여기](https://doc.rust-lang.org/book/ch19-03-advanced-traits.html#using-the-newtype-pattern-to-implement-external-traits-on-external-types) 를 참조} `Dog` 의 자체 정의만 보면 `Dog` 가 어떠한 trait 들을 가지고 있는지 쉽게 알 수 는 없지만, 그 대신 원하는 trait 들을 `Dog` 에 구현할 수 있습니다. C++ 과 Rust 의 차이는 아래 그림을 보시면 이해가 되실 것입니다.

![caption=C++ 과 Rust 의 차이](/img/rust/1.1.png)

### 정적 다형성 (Static polymorphism)

Rust 에서 다형성을 제공하는 방법은 정적 다형성과 동적 다형성 이 두 가지를 꼽을 수 있습니다. \sidenote{이들을 각각 정적 디스패치(static dispatch) 와 동적 디스패치 (dynamic dispatch) 라고도 합니다.} 이 두 다형성의 차이점은 어느 시점에서 어떤 타입의 함수가 호출되는지 결정되는 것으로 정해집니다. 정적 다형성의 경우 **컴파일 타임** 에 어느 함수에 호출이 바인딩 되는지 결정되는 것이고, 반대로 동적 다형성의 경우 **런타임**에 해당 정보가 결정 됩니다.

그렇다면 먼저 정적 다형성이 Rust 에서 어떠한 방식으로 이루어지는지 살펴봅시다.

```rust
fn make_animal_sound(animal: &impl Animal) {
    println!("{}", animal.make_sound())
}
```

위 `make_animal_sound` 함수의 경우 `Animal` 을 구현하고 있는 타입을 인자로 받는 함수 입니다. 예를 들어서

```rust
trait Animal {
    fn make_sound(&self) -> String;
}

pub struct Dog {}

impl Animal for Dog {
    fn make_sound(&self) -> String {
        "멍멍".to_string()
    }
}

pub struct Cat {}

impl Animal for Cat {
    fn make_sound(&self) -> String {
        "야옹".to_string()
    }
}

fn make_animal_sound(animal: &impl Animal) {
    println!("{}", animal.make_sound())
}

fn main() {
    let dog = Dog {};
    let cat = Cat {};

    make_animal_sound(&dog);
    make_animal_sound(&cat);
}
```

위와 같은 코드를 컴파일 하게 되면

```exec
멍멍
야옹
```

와 같이 `make_animal_sound` 가 전달된 타입에 맞는 함수들을 잘 호출했음을 알 수 있습니다. 이 정적 다형성의 경우 컴파일러가 `make_animal_sound` 에 전달된 인자의 타입을 보고 각각의 경우에 맞는 코드들을 따로 생성하게 됩니다.

쉽게 말해서 `make_animal_sound(&dog)` 의 경우 *`make_animal_sound` 에 `Dog` 가 전달된 버전의 함수* 가 실행되고, `make_animal_sound(&cat)` 의 경우 *`make_animal_sound` 에 `Cat` 이 전달된 버전의 함수* 가 실행되는 셈이지요.

따라서 컴파일러는 각각의 경우에 대해서 가능한 모든 코드들을 생성하고 컴파일 하게 됩니다. 이 때문에 컴파일 시간이 길어지고, 또 바이너리의 크기가 커질 수 있으며 CPU 명령어 캐시 최적화에도 방해가 되겠죠.

하지만 `make_animal_sound` 를 호출 할 때 특별한 오버헤드 없이 바로 해당 함수를 호출할 수 있다는 장점이 있습니다. 또한 컴파일러가 각각의 타입들에 대해서 다른 코드를 생성하기 때문에 각각의 타입에 맞춘 최적화를 수행할 수 도 있겠죠.

```objdump
fn main() {
    5e00:	48 83 ec 18          	sub    $0x18,%rsp
    let dog = Dog {};
    let cat = Cat {};

    make_animal_sound(&dog);
    5e04:	48 8d 7c 24 08       	lea    0x8(%rsp),%rdi
    5e09:	e8 32 f7 ff ff       	callq  5540 <_ZN5hello17make_animal_sound17h8bb37ab9cd9f82ccE>
    make_animal_sound(&cat);
    5e0e:	48 8d 7c 24 10       	lea    0x10(%rsp),%rdi
    5e13:	e8 08 f8 ff ff       	callq  5620 <_ZN5hello17make_animal_sound17hed76787fb7d09f14E>
}
```

실제로 `main` 함수의 명령어만 봐도 두 `make_animal_sound` 함수가 각기 다른 위치에 있는 함수들을 호출하고 있는 것을 볼 수 있습니다.

#### C++

C++ 에서 굳이 정적 다형성을 구현하자면 아래와 같은 코드와 가장 유사하다고 볼 수 있습니다.

```cpp-formatted
#include <iostream>
#include <string>

class Animal {
 public:
  virtual std::string MakeSound() const = 0;
};

class Dog : public Animal {
 public:
  std::string MakeSound() const override { return "멍멍"; }
};

class Cat : public Animal {
 public:
  std::string MakeSound() const override { return "야옹"; }
};

// enable_if_t 부분을 통해 AnimalType 이 반드시 Animal 을 상속 받는 클래스 임을
// 강제할 수 있습니다. 이를 사용하지 않는다면 AnimalType 자리에 그냥 MakeSound
// 함수가 구현되어 있는 임의의 클래스가 올 수 있습니다.
template <typename AnimalType,
          std::enable_if_t<std::is_base_of_v<Animal, AnimalType>, bool> = true>
void MakeAnimalSound(const AnimalType& animal) {
  std::cout << animal.MakeSound() << std::endl;
}

int main() {
  Dog dog;
  Cat cat;

  MakeAnimalSound(dog);
  MakeAnimalSound(cat);
}
```

C++ 에서 각 타입들이 대해서 따로 코드를 생성하라면 템플릿을 사용하는 방법 밖에 없습니다. 이 때 Rust 에서는 간단히 타입 인자가 `Animal` 을 구현하는 것을 `impl Animal` 을 통해서 강제할 수 있었지만, C++ 의 경우 `enable_if_t` 와 `is_base_of` 를 사용하는 수 밖에 없습니다. 따라서 템플릿 정의 부분이 상당히 난해하죠.. (물론 C++ 20 의 concept 을 사용하면 되기는 하지만...) 여러모로 Rust 에서 정적 다형성을 구성하는 것이 훨씬 깔끔하고 쉽습니다.

아무튼 `Rust 1`승!

### 동적 다형성

정적 다형성을 적용하기 위해서는 컴파일 타임에 `make_animal_sound` 에 전달되는 인자의 타입이 결정되어야 합니다. 하지만 컴파일 시에 `Dog` 를 전달할지, 아니면 `Cat` 을 전달할지 알 수 없는 경우가 있죠.

C++ 에서는 기반 클래스의 포인터로 상속 받는 클래스를 가리킬 수 있습니다. 예를 들어서

```cpp-formatted
Animal* dog = new Dog;
```

가 아무 문제없는 코드 인것 처럼 말이죠.

Rust 에도 비슷하게도, 해당 trait 을 구현하는 모든 타입은 `Trait object` 를 정의해서 참조할 수 있습니다.

```rust
fn make_animal_sound(animal: &dyn Animal) {
    println!("{}", animal.make_sound())
}
```

`Trait object` 를 정의하기 위해서는 간단히 `impl` 을 `dyn` 으로 바꿔주시면 됩니다. \sidenote{`dyn` 은 Dynamic 의 준말로, animal 이 동적으로 dispatch 됨을 의미한다고 생각하시면 됩니다.} 여기서 한 가지 중요한 점은 trait 객체의 크기를 컴파일 타임에 알 수 없기 때문에 반드시 포인터의 형태로 & 를 붙여줘야 된다는 점입니다. \sidenote{쉽게 말해 `dyn Animal` 은 `!Sized` 입니다.}

그러면 런타임 시에 `make_animal_sound` 에 `Dog` 가 전달될 때랑 `Cat` 이 전달될 때랑 알아서 **동적(Dynamic)으로** 해당 타입들의 `make_sound` 를 호출하게 됩니다.

```rust
trait Animal {
    fn make_sound(&self) -> String;
}

pub struct Dog {}

impl Animal for Dog {
    fn make_sound(&self) -> String {
        "멍멍".to_string()
    }
}

pub struct Cat {}

impl Animal for Cat {
    fn make_sound(&self) -> String {
        "야옹".to_string()
    }
}

fn make_animal_sound(animal: &dyn Animal) {
    println!("{}", animal.make_sound())
}

fn main() {
    let dog = Dog {};
    let cat = Cat {};

    make_animal_sound(&dog);
    make_animal_sound(&cat);
}
```

실행 해보면

```exec
멍멍
야옹
```

와 같이 잘 나오죠. 동적 다형성을 사용하였을 때 가장 큰 장점은, 입력 받는 타입 마다 `make_animal_sound` 를 만들 필요 없이 `&dyn Animal` 을 인자로 받는 함수 딱 하나만 만들면 된다는 점입니다. 따라서 앞서 정적 다형성을 사용했을 때와는 다르게 컴파일 해야 되는 코드의 양도 줄고, 실행 파일의 크기도 줄어듭니다.

```objdump
fn main() {
    5d30:	48 83 ec 18          	sub    $0x18,%rsp
    5d34:	48 8d 05 9d 27 04 00 	lea    0x4279d(%rip),%rax        # 484d8 <__do_global_dtors_aux_fini_array_entry+0x48>
    let dog = Dog {};
    let cat = Cat {};

    make_animal_sound(&dog);
    5d3b:	48 8d 4c 24 08       	lea    0x8(%rsp),%rcx
    5d40:	48 89 cf             	mov    %rcx,%rdi
    5d43:	48 89 c6             	mov    %rax,%rsi
    5d46:	e8 f5 fe ff ff       	callq  5c40 <_ZN5hello17make_animal_sound17h48b7a1f5eb9e2a5fE>
    5d4b:	48 8d 05 a6 27 04 00 	lea    0x427a6(%rip),%rax        # 484f8 <__do_global_dtors_aux_fini_array_entry+0x68>
    make_animal_sound(&cat);
    5d52:	48 8d 4c 24 10       	lea    0x10(%rsp),%rcx
    5d57:	48 89 cf             	mov    %rcx,%rdi
    5d5a:	48 89 c6             	mov    %rax,%rsi
    5d5d:	e8 de fe ff ff       	callq  5c40 <_ZN5hello17make_animal_sound17h48b7a1f5eb9e2a5fE>
}
```

위 처럼 objdump 로 어셈블리를 까 보아도 두 군데의 `make_animal_sound` 함수의 호출 부분이 모두 같은 함수를 가리키고 있음을 볼 수 있죠.

C++ 에서 `make_animal_sound` 를 구현한다면

```cpp-formatted
// 혹은 const Animal& 도 됩니다.
void MakeAnimalSound(const Animal* animal) {
  std::cout << animal->MakeSound() << std::endl;
}
```

위와 같이 `Animal` 의 레퍼런스로 받던지 아니면 포인터를 받으면 됩니다.

C++ 에서는 동적 다형성을 위해서 객체의 주소값을 아는 것 만으로도 충분합니다. 왜냐하면 함수의 인자에 전달되는 포인터 타입이 명시되어 있기 때문이죠. 타입이 정해진다면 해당 타입의 가상 함수 테이블과 데이터 필드들의 위치가 결정되기 때문에 컴파일러가 손쉽게 동적 디스패치를 사용하는 코드를 생성할 수 있습니다.

하지만 Rust 의 경우는 조금 다릅니다. 왜냐하면 trait 객체 안에는 어떤 타입에 이 trait 이 붙는지에 대한 정보가 하나도 없기 때문입니다. 예를 들어서 간단히 `Dog` 타입의 객체가 메모리 상에서 어떻게 존재하는지 살펴봅시다.

![caption=Dog 의 메모리에서의 모습](/img/rust/1.2.png)

예를 들어서 `Dog` 에 `Cute` 와 `Animal` trait 들이 구현되어 있다고 해봅시다. 그러면, `Dog` 타입의 객체에는 먼저 데이터 필드들이 있을 것이고, 그 다음에 각각의 trait 들에 대한 함수 테이블들이 있을 것입니다. 함수 테이블에는 해당 trait 에 정의된 함수들의 위치가 쓰여져 있겠죠.

![caption=객체의 주소값만을 전달했을 때 문제점](/img/rust/1.3.png)

하지만 문제는 타입들 마다 trait 들의 함수 테이블 위치가 다 다르다는 것입니다. 예를 들어서 위 `Dog` 의 경우 `Animal` trait 의 함수 테이블이 맨 위에 있었지만, 만일 (`Animal` 을 포함한) 다른 trait 들을 구현하는 타입들의 경우 `Animal` 의 함수 테이블이 다른 위치에 있을 수 도 있다는 것이죠 (마치 `Cute` trait 의 함수 테이블 처럼 말이죠.) \sidenote{참고로 Rust 에는 가상 함수 개념이 없으므로 가상 함수 테이블이 아니라 그냥 함수 테이블이라 부르겠습니다}

따라서 객체의 주소값 만으로 동적 다형성을 구현하는 것이 불가능 합니다.

### Fat pointer

여러분이라면 이 문제를 어떻게 해결할 것인가요? 한 가지 아이디어로 `Animal` 타입 안에 조그마한 테이블을 만들어서 trait 별 테이블의 위치를 기록해 놓을 수 있을 것입니다. 하지만 이렇게 된다면 매 번 함수 호출 시에 또 다른 테이블을 참조해야되기 때문에 속도 문제가 발생하겠죠. 또 해당 테이블이 객체에서 차지하는 크기가 있을 테니 객체마다 메모리도 더 많이 쓰겠죠.

Rust 에서는 이 문제를 **Fat pointer** 를 도입함으로써 해결합니다. 일반적으로 포인터는 어떠한 객체의 주소값 딱 하나를 보관합니다. 하지만 Rust 의 경우 주소값 하나만 가지고는 동적 다형성을 구현하는 것이 불가능 하므로, 포인터에 객체의 주소값 외에도 **trait 의 함수 테이블에 대한 정보** 까지 같이 전달하게 됩니다. 따라서 우리가 흔히 생각하는 포인터 보다 크기가 더 크기 때문에 뚱뚱한 포인터 라는 이름이 붙게 된거죠.

![caption=Trait 객체에는 객체의 주소값 뿐만이 아니라, 해당 trait 의 함수 테이블 주소 까지 포함하고 있다.](/img/rust/1.4.png)

따라서 Rust 의 경우 trait 객체를 사용할 때 C++ 에서 포인터를 복사하는 것 보다 8 바이트 더 많이 복사하게 됩니다.

한 가지 짚고 넘어갈 점은 모든 trait 들을 trait 객체로 만들 수 있는 것은 아닙니다. trait 에 정의된 함수들 중에서 `Self` 를 리턴하는 함수가 있다면 trait 객체로 만들 수 없습니다. 왜냐하면 `Self` 는 실제 trait 을 구현하고 있는 타입을 의미하기 때문에 trait 객체에서 해당 함수를 사용했을 경우 그 함수의 리턴 타입을 컴파일 타임에 결정할 수 없기 때문이죠.

그러한 trait 들을 사용하기 위해서는 앞서 이야기한 정적 디스패치를 사용하는 수 밖에 없습니다.

### 정리

그러면 간단히 Rust 와 C++ 의 두 가지 다형성에 대해서 정리해보자면 아래와 같습니다.

||Rust|C++|
|----|----|----|
|정적 디스패치|\ref{rust-static}|\ref{cpp-static}|
|동적 디스패치|\ref{rust-dyn}|\ref{cpp-dyn}|

```ref-rust-static
* `impl Trait` 으로 원하는 Trait 을 가지는 타입을 받을 수 있다.
* 컴파일 타임에 디스패치가 이루어지므로 런타임 오버헤드가 없다.
* 대신 타입 마다 코드를 생성해야 하므로, 컴파일 시간이 길어지고 바이너리의 크기가 커진다. (결과적으로 CPU 명령어 캐시 Hit 을 낮출 수 있기에 런타임 오버헤드가 생길 수 있음.)
```

```ref-cpp-static
* C++ 상에서 템플릿을 통해서 구현할 수 있지만, 조금 번잡하다. C++ 20 에서 concept 를 사용하면 조금 나을 수 도?
* Rust 와 같이 각 타입들에 대해 모든 코드를 생성하므로 옆과 장단점이 동일하다.
```

```ref-rust-dyn
* `&dyn Trait` 으로 원하는 Trait 을 가지는 타입을 동적으로 디스패치 할 수 있다.
* 정적 디스패치에 비해 컴파일 오버헤드가 없다. 
* 다만 런타임 시에 Fat pointer 를 전달하고 또 함수 테이블을 참조하는 과정에서 오버헤드가 존재한다. 
```

```ref-cpp-dyn
* Rust 와 유사하지만 Fat pointer 가 아니라 객체의 주소값 자체만으로 가능하다. 
```

### 결과적으로 뭘 써야되나?

정해진 답은 없지만 보통 라이브러리 코드에서는 정적 디스패치, 바이너리 코드에서는 동적 디스패치를 사용하는 것이 좋다고 합니다.

보통 라이브러리의 경우 라이브러리를 사용하는 사람으로 하여금 선택의 여지를 주는 것이 좋습니다. 이 때 정적 디스패치를 사용할 경우, 라이브러리 사용자가 이를 바탕으로 정적 혹은 동적 디스패치 코드를 작성할 수 있습니다. 왜냐하면 `impl A` 라는 객체는 `&dyn A` 로 변환 가능하기 때문이죠. 하지만 그 반대는 불가능 합니다. 반면에 동적 디스패치를 사용하면 이를 기반으로 하는 코드들이 전부다 동적 디스패치를 사용해야 하죠.

하지만 바이너리 코드의 경우, 동적 디스패치를 사용하는 것이 좋은데 물론 런타임 오버헤드를 고려하더라도 대부분의 경우 동적 디스패치를 사용할 때 코드가 좀 더 간결하기 때문입니다. 그리고 컴파일 타임이 줄어드는 것도 큰 장점이죠.

아무튼, 각각의 장단점을 잘 알고 적재 적소에 사용하는 것이 중요하다고 생각합니다.