Of Boxes and Trees - Smart Pointers in Rust

2017-08-12

박스와 트리 이야기 - 러스트의 스마트 포인터

최근 러스트로 이진 트리 자료구조를 구현해 보았습니다. 각 이진 트리는 루트 값과 왼쪽, 오른쪽 서브트리를 가집니다. 꽤 직관적인 이 파이썬 구현에서 출발했습니다.

class Tree:
  def __init__(self, val, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right

이를 이용하면 이렇게 멋진 트리 객체를 선언할 수 있습니다:

t = Tree(15,
      Tree(12,
           None,
           Tree(13)),
      Tree(22,
           Tree(18),
           Tree(100)))

결과는 아름답게 시각화할 수 있습니다.
(네, 제가 직접 그렸습니다.)

그 코드를 러스트로 옮기는 일은 생각보다 조금… 까다로웠습니다. 첫 시도는 꽤 무해해 보였습니다.

struct Tree {
  root: i64,
  left: Tree,
  right: Tree,
}

파이썬 정의를 거의 일대일로 옮긴 것에 불과한데 — 하지만 rustc 가 안 된다고 합니다.

error[E0072]: recursive type `Tree` has infinite size
 --> src/main.rs:1:1
  |
1 | struct Tree {
  | ^^^^^^^^^^^ recursive type has infinite size
  |
  = help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `Tree` representable

파이썬, PHP, 루비 같은 메모리 관리 언어에 익숙해서 처음에는 당황했습니다. 하지만 문제는 이해하기 쉽습니다. 컴퓨터의 메모리는 한정되어 있습니다. 각 항목에 얼마나 많은 메모리를 할당할지 파악하는 건 컴파일러의 역할입니다.

우리의 경우 컴파일러는 다음과 같이 추론합니다:

트리는 i64 하나와 두 개의 트리를 담는 구조체입니다. 이 트리들 각각은 다시 i64 하나와 두 개의 트리를 담는 구조체입니다. 그리고 각각은 또…
감 잡으셨을 겁니다.

Tree { i64, Tree, Tree }
Tree { i64, Tree { ... }, Tree { ... } }
// The next expansion won't fit on the page anymore

트리가 몇 개의 서브트리를 가질지 미리 알 수 없으니, 사전에 얼마나 많은 메모리를 할당해야 할지 알 방법이 없습니다. 런타임에 가서야 알 수 있을 뿐입니다!

러스트는 해결 방법을 알려줍니다. Box, Rc 또는 & 같은 간접 참조를 넣으라는 것입니다. 이들은 러스트의 서로 다른 “포인터 타입”입니다. 모두 메모리의 어딘가를 가리킵니다. 따라서 트리 구조체 전체 크기를 알 필요 없이, 트리가 위치한 메모리의 지점만 알면 됩니다. 하지만 트리 구조체를 정의하기에는 그걸로 충분합니다. 이런 포인터 타입 덕분에 수동 메모리 관리 없이도 안전하게 그렇게 할 수 있습니다. 각 타입은 서로 다른 보장을 제공하므로, 요구사항에 가장 잘 맞는 것을 선택해야 합니다.

&는 러스트 용어로 borrow라고 부릅니다. 셋 중 가장 흔한 타입입니다. 메모리의 어딘가를 참조하지만, 가리키는 데이터를 소유하지는 않습니다. 따라서 빌림의 수명은 소유자에 따라 달라집니다. 그러므로 여기서는 라이프타임 매개변수를 추가해야 합니다. 이 때문에 사용이 번거로워질 수 있습니다.
```
struct Tree<'a> {
  root: i64,
  left: &'a Tree<'a>,
  right: &'a Tree<'a>,
}
```
Box는 런타임 오버헤드가 전혀 없는 스마트 포인터입니다. 가리키는 데이터를 소유하며 힙에 저장합니다. 스코프를 벗어날 때 가리키던 데이터를 먼저 드롭하고 자신을 정리하기 때문에 스마트하다고 부릅니다. 수동 메모리 관리가 필요 없어서 정말 편리합니다. ✨
```
struct Tree {
  root: i64,
  left: Box<Tree>,
  right: Box<Tree>,
}
```
Rc도 스마트 포인터입니다. “reference-counting”의 약자입니다. 자료구조에 대한 참조 개수를 내부적으로 추적합니다. 참조 개수가 0이 되는 즉시 스스로 정리합니다. 한 스레드 안에서 같은 데이터에 대해 여러 소유자가 필요할 때 Rc를 선택하세요. 멀티스레딩을 위해서는 Arc(atomic reference count)도 있습니다.
```
struct Tree {
  root: i64,
  left: Rc<Tree>,
  right: Rc<Tree>,
}
```

트리를 박스에 넣기

세 가지 방법 모두 완전히 유효합니다. 어떤 것을 선택해야 할지는 사용 사례에 따라 달라집니다. 경험상 단순하게 유지하는 것이 좋습니다. 저는 특별한 보장이 필요하지 않았기 때문에 Box를 선택했습니다.

서브트리를 선택 사항으로 만들기

다음으로 마주한 문제는 트리 구조체를 인스턴스화할 수 없다는 것이었습니다. 왼쪽과 오른쪽 서브트리의 타입이 Box<Tree>인데, 어느 시점에서는 빈 서브트리가 필요하기 때문입니다.

파이썬 예제에서는 자료구조의 끝을 나타내기 위해 None을 사용했습니다. 러스트의 Option 타입 덕분에 같은 방식을 사용할 수 있습니다:

struct Tree {
  root: i64,
  left: Option<Box<Tree>>,
  right: Option<Box<Tree>>,
}

이 모든 과정을 거치면 첫 번째 트리를 만들 수 있습니다:

Tree {
    root: 15,
    left: Some(Box::new(Tree {
            root: 12,
            left: None,
            right: Some(Box::new(Tree {
                    root: 13,
                    left: None,
                    right: None,
            })),
    })),
    right: Some(Box::new(Tree {
            root: 22,
            left: Some(Box::new(Tree {
                    root: 18,
                    left: None,
                    right: None,
            })),
            right: Some(Box::new(Tree {
                    root: 100,
                    left: None,
                    right: None,
            })),
    })),
};

관점에 따라 이를 장황하다고 할 수도 있고 명시적이라고 할 수도 있습니다. 파이썬 버전과 비교하면 제 취향에는 조금 복잡해 보였습니다.

더 나아질 수 있을까요? Chris McDonald의 도움으로 다음과 같은 표현을 만들었습니다:

Tree::new(15)
  .left(
    Tree::new(12)
      .right(Tree::new(13))
  )
  .right(
    Tree::new(22)
      .left(Tree::new(18))
      .right(Tree::new(100))
  );

제 눈에는 이쪽이 훨씬 보기 편합니다.
이를 가능하게 하는 전체 트리 구현은 다음과 같습니다:

#[derive(Default)]
struct Tree {
  root: i64,
  left: Option<Box<Tree>>,
  right: Option<Box<Tree>>,
}

impl Tree {
  fn new(root: i64) -> Tree {
    Tree {
      root: root,
      ..Default::default()
    }
  }

  fn left(mut self, leaf: Tree) -> Self {
    self.left = Some(Box::new(leaf));
    self
  }

  fn right(mut self, leaf: Tree) -> Self {
    self.right = Some(Box::new(leaf));
    self
  }
}

업데이트: Danny Grein이 트위터에서 From<i64> for Tree를 구현하면 다음 구문을 지원할 수 있다고 언급했습니다:

root(15)
  .left(
    root(12)
      .right(13)
   )
  .right(
    root(22)
      .left(18)
      .right(100)
  );

왜 파이썬에서는 그냥 동작했을까?

이제 왜 파이썬에서는 트리 구현이 그렇게 매끄럽게 동작했는지 궁금하실 겁니다. 이유는 파이썬이 런타임에 트리 객체를 위한 메모리를 동적으로 할당하기 때문입니다. 또 파이썬은 모든 것을 PyObject로 감싸는데, 이는 위에서 본 Rc와 비슷한 — 참조 카운트 방식의 스마트 포인터입니다.

러스트는 이 부분에서 훨씬 더 명시적입니다. 필요를 표현하는 데 더 많은 유연성을 주지만, 이를 잘 활용하려면 가능한 모든 대안을 알고 있어야 합니다. 제 조언은 단순한 빌림으로 충분하다면 스마트 포인터는 피하라는 것입니다.

하지만 라이프타임이 방해가 되거나 스레드 안전성 같은 추가 보장이 필요하다면, 스마트 포인터는 툴킷에 추가하면 훌륭한 도구가 됩니다. 스마트 포인터에 대해 더 알아보려면 러스트 문서가 좋은 출발점입니다. 또한 트리를 런타임에 가변적으로 만들어야 한다면, 할당자를 영리하게 활용하는 방법을 다룬 “Idiomatic tree and graph-like structures in Rust”도 읽어보세요.