Rust의 메모리 관리 특성에 더 잘 맞추면서도 Wadler 스타일 문서 트리의 표현력을 유지하는 pretty printer 구현 설계를 제안하고, 성능 비교 결과를 소개합니다.
Rustc의 pretty printer를 연구하고, 직접 pretty printer 라이브러리를 구현한 뒤(cgrammar 크레이트에서 사용되며, 이 크레이트는 C23 구문을 파싱하고 처리하기 위한 것이다), 나는 더 나은 pretty printer 라이브러리를 어떻게 설계할 수 있을지 계속 고민해 왔다. 특히 학계의 연구 성과 1 1.J. Hughes, “The Design of a Pretty-Printing Library,” Advanced Functional Programming, vol. 925. Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 53–96, 1995. doi: 10.1007/3-540-59451-5_3.2 2.P. Wadler, “A Prettier Printer,” The Fun of Programming. Macmillan Education UK, London, pp. 223–243, 2003. doi: 10.1007/978-1-349-91518-7_11.3 3.J.-P. Bernardy, “A Pretty but Not Greedy Printer (Functional Pearl),” Proceedings of the ACM on Programming Languages, vol. 1, no. ICFP, pp. 1–21, Aug. 2017, doi: 10.1145/3110250.를 실용적인 Rust 라이브러리 설계에 적용하는 방향으로 생각해 왔다.
중요한 장애물 하나는 학술 연구가 흔히 함수형 프로그래밍 언어를 기반으로 하며, 특히 가비지 컬렉션의 존재를 전제한다는 점이다. 반면 Rust는 가비지 컬렉션이 없는 시스템 프로그래밍 언어다. 이는 이런 설계를 Rust에서 구현할 때 메모리 관리가 추가로 고려해야 할 요소가 된다는 뜻이다.
예를 들어, 전형적인 Wadler 스타일 4 4.Wadler 스타일과 Oppen 스타일 pretty printer의 차이에 대해서는 elegance 크레이트 문서의 이 설명을 보라. pretty printer에서는 문서 구조가 보통 재귀적 데이터 타입으로 표현된다:
type doc =
| Nil
| Append of doc * doc
| Group of doc
| FlatAlt of doc * doc
| Nest of int * doc
| Hardline
| Text of string
| Union of doc * doc
| Fail
그다음 이 문서 구조는 레이아웃 함수를 통해 문자열 출력으로 변환된다:
let rec layout (d : doc) (width : int) : string
= (* implementation omitted *)
이런 알고리즘을 Rust에서 구현하려면, 가장 직접적인 접근은 같은 패턴을 채택하는 것이다. 예를 들어 pretty 크레이트는 Wadler의 고전 알고리즘(그리고 이후 추가된 몇 가지 보완)을 구현하며, 그 문서 구조 정의는 다음과 같다(단순화됨):
pub enum Doc<T> {
Nil,
Append(T, T),
Group(T),
FlatAlt(T, T),
Nest(isize, T),
Hardline,
Text(Box<str>),
Union(T, T),
Fail,
}
type BoxDoc = Box<Doc<BoxDoc>>;
type RcDoc = Rc<Doc<RcDoc>>;
위에서 보듯이 pretty 크레이트는 Doc 열거형을 타입 T에 대해 제네릭하게 만든다. 이 T는 BoxDoc, RcDoc, 또는 Doc을 가리키는 다른 포인터 타입이 될 수 있다. 이렇게 하면 사용자는 더 유연하게 메모리 관리 방식을 선택할 수 있다. 더 가벼운 BoxDoc, 더 유연하지만 더 무거운 RcDoc, 또는 어떤 arena allocator든 사용할 수 있다. 5 5.또 다른 장점은 이 설계가 사실상 Doc을 하나의 타입이 아니라 functor로 바꾼다는 점이며, 그 결과 functor 관련 추상화(예를 들어 catamorphism)를 사용해 효율적인 재귀 알고리즘을 구현할 수 있게 된다. recursion 크레이트를 보라. 하지만 이 설계에도 한계는 있다. 예를 들어 문서 트리의 모든 노드가 동일한 메모리 관리 전략을 사용해야 하므로, 어떤 상황에서는 유연성이 부족할 수 있다.
Oppen 스타일 pretty printer(Rustc의 pretty printer와 elegance 크레이트 등)는 문서의 입력과 출력을 완전한 문서 트리를 만들지 않고 스트림으로 처리하므로 이런 문제가 없다. 하지만 Oppen 스타일 pretty printer의 스트리밍 방식은 표현력도 제한한다. Sorawee Porncharoenwase 등 6 6.S. Porncharoenwase, J. Pombrio, and E. Torlak, “A Pretty Expressive Printer,” Proceedings of the ACM on Programming Languages, vol. 7, no. OOPSLA2, pp. 1122–1149, Oct. 2023, doi: 10.1145/3622837.의 연구는 일반적인 pretty printing 문제가 전역 최적화 문제임을 지적한다. 스트리밍 pretty printer는 탐욕 알고리즘을 통해 국소적으로 최적인 해만 구할 수 있으며, 전역 최적성을 보장할 수 없다. 따라서 전역적으로 최적인 pretty printer를 구현하려면 완전한 문서 트리를 구축해야 한다.
이 글에서는 Rust에서 pretty printer를 구현하기 위한 새로운 설계를 제안한다. 목표는 Wadler 스타일 문서 트리의 표현력을 유지하면서도, Rust의 메모리 관리 방식에 더 잘 맞는 형태로 이를 구현하는 것이다.
이 구현의 영감은 함수형 프로그래밍의 한 개념에서 왔다. 어떤 데이터 타입은 그것을 소비하는 방식들로 동등하게 표현될 수 있다.7 7.내 다른 블로그 글 Church Encoding, Parametricity, and the Yoneda Lemma를 보라. 우리가 वास्तव로 관심 있는 것은 문서 트리의 구체적인 구조가 아니라, 그것을 이용해 어떻게 출력을 만들어 내느냐이다.
따라서 Doc을 재귀적 데이터 구조로 정의하는 대신, Doc을 trait로 정의하고 문서를 소비해 출력을 만들어 내는 메서드를 두는 방식을 취할 수 있다.
pub trait Doc {
fn layout(&self, renderer: &mut Render) -> RenderOutput;
}
그렇다면 다양한 문서 구성은 이 trait를 구현하는 서로 다른 타입이 된다. 예를 들어 다음과 같다:
#[derive(Clone)]
pub struct Text {
s: String,
}
impl Doc for Text {
fn layout(&self, renderer: &mut Render) -> RenderOutput {
renderer.text(&self.s)
}
}
pub fn text(s: impl Into<String>) -> impl Doc {
Text { s: s.into() }
}
그리고 다음과 같은 것도 가능하다:
#[derive(Clone)]
pub struct Concat<A, B> {
a: A,
b: B,
}
impl<A: Doc, B: Doc> Doc for Concat<A, B> {
fn layout(&self, renderer: &mut Render) -> RenderOutput {
// fn Render::concat(
// self: &Render,
// left: RenderOutput,
// right: impl Fn(&Render) -> RenderOutput
// ) -> RenderOutput;
renderer.concat(self.a.layout(renderer), |r| self.b.layout(r))
}
}
pub fn concat<A: Doc, B: Doc>(a: A, b: B) -> impl Doc {
Concat { a, b }
}
이 모델에서도 문서 트리의 구조는 여전히 존재한다. 하지만 재귀적 데이터 구조 접근과 비교하면, 메모리 간접 참조와 동적 할당 오버헤드를 크게 줄일 수 있다.
동시에 이 방식은 더 유연한 메모리 관리도 지원한다. 예를 들어 Box<dyn Doc>과 Rc<dyn Doc>은 둘 다 Doc trait를 구현하므로, 하나의 문서 트리 안에서 이 둘을 섞어 사용할 수 있다.
impl Doc for Box<dyn Doc> {
fn layout(&self, renderer: &mut Render) -> RenderOutput {
self.as_ref().layout(renderer)
}
}
impl Doc for Rc<dyn Doc> {
fn layout(&self, renderer: &mut Render) -> RenderOutput {
self.as_ref().layout(renderer)
}
}
다른 관점에서 보면, 이것은 객체지향 언어(예를 들어 C++)에서 열거형 타입을 구현하는 방식과 다소 비슷하다. 모든 문서를 위한 기반 클래스를 정의하고, 각 문서 구성이 이 기반 클래스의 하위 클래스가 되는 방식이다.
나는 위 설계를 위한 개념 증명 구현(아래에서는 pye라고 부른다)8 8.AI의 도움을 받았다. pye의 코드는 아직 완전히 검토하고 정리하지 않았기 때문에 공개하지 않았다.을 작성했고, 논문 A pretty expressive printer (OOPSLA’23) 9 9.S. Porncharoenwase, J. Pombrio, and E. Torlak, “A Pretty Expressive Printer,” Proceedings of the ACM on Programming Languages, vol. 7, no. OOPSLA2, pp. 1122–1149, Oct. 2023, doi: 10.1145/3622837.의 알고리즘 , 즉 일반적이며 전역적으로 최적인 pretty printing 알고리즘을 구현했으며, 다음 크레이트들과 성능 비교를 수행했다:
78kB JSON 포매팅 작업에서 pye는 pe보다 60배 빠른 성능 향상을 달성했고, pretty 크레이트 성능의 약 57% 수준에 도달했다. pye가 pretty 크레이트보다 느린 이유는 주로 pye가 전역 최적 알고리즘을 구현한 반면, pretty 크레이트는 더 단순한 탐욕 알고리즘을 사용하기 때문이다. 그러나 같은 알고리즘을 사용하는 pe와 비교했을 때 pye의 성능 향상은 이 새로운 설계가 Rust에서 충분히 경쟁력이 있음을 보여 준다.
아래는 JSON 레코드, JSON 배열, 깊게 중첩된 JSON, 혼합 JSON, Lisp 코드 등을 포함한 더 많은 포매팅 작업에 대한 성능 비교다. 각 작업에는 여러 변형이 있다: wide(한 줄에 들어갈 만큼 줄 너비가 충분함), middle(일반적인 사용 사례와 같은 보통 줄 너비), narrow(매우 작은 줄 너비). 이 작업들에서 pye의 성능은 대체로 pretty 및 elegance와 비슷한 수준이며, 일부 작업에서는 두 크레이트를 모두 능가하기도 하고, 대다수 작업에서는 pe를 크게 앞선다.
업데이트:
나는 더 많은 성능 비교를 포함한 새로운 실험을 추가했다. 여기에는 다음이 포함된다:
실험 결과는 아래와 같다:
여기서 몇 가지 더 흥미로운 사실을 볼 수 있다: