Rustdoc의 성능 병목을 찾아 필터링, 원시 타입, 합성 impl, self type 처리를 개선해 평균 33% 속도 향상을 달성한 과정입니다.
저는 Rustdoc 팀의 일원이며, 최근 Rustdoc에 일련의 PR을 적용했습니다. 그 결과 평균 wall-time이 25% 감소했습니다(이는 33% 속도 향상에 해당합니다).
hyper,bitmaps같은 일부 실제 크레이트에서는 최대 40%, helloworld 같은 마이크로벤치마크에서는 최대 **60%**까지 개선되었습니다. 이 글에서는 이러한 성능 개선을 어떻게 발견하고 구현했는지 꽤 자세히 다룹니다. 이 경우 Rustdoc을 포함해 Rust 자체를 작업하는 일이 어떤 것인지 더 알고 싶다면 흥미로울 것입니다. 다만 마지막의 최종 결과를 보여 주는 멋진 차트로 바로 넘어가고 싶다면, 편하게 그렇게 하세요!
지난달 Rust 릴리스 팀 구성원 @theemathas가 최신 베타에서 발생한 이상한 회귀에 관해 Rustdoc Zulip에 글을 올렸습니다. 익숙하지 않은 분을 위해 설명하자면, Rustdoc은 cargo doc의 기반이 되는 도구입니다. 표준 라이브러리 문서나 docs.rs의 크레이트 문서를 열어 본 적이 있다면, 보고 있는 것이 바로 Rustdoc의 출력입니다. 아무튼 Rust의 안정 버전이 게시되기 전에 릴리스 팀은 공개 Rust 생태계 전반에서 새 버전을 시험하는 Crater라는 도구를 실행합니다. Crater는 indented-blocks라는 크레이트에서 Rustdoc이 새롭게 오류를 내는 것을 발견했으며, 코드는 다음과 같았습니다.
#![recursion_limit = "8"]
이 코드만 포함한 크레이트에서 Rustdoc은 core::fmt의 내부용 트레이트를 분석하다가 “구성된 최대 스택 프레임 수에 도달했습니다”라는 오류와 함께 실패했습니다. 반면 Rustc는 컴파일을 성공적으로 마쳤습니다. 이 recursion_limit 속성은 많은 언어 기능이 컴파일 시 과도한 재귀를 유발할 수 있으므로, 사용자가 Rustc의 자체 재귀를 제어할 수 있게 합니다.1 예를 들어 깊게 중첩된 매크로나 복잡한 트레이트 로직을 사용할 경우, 사용자는 기본값보다 재귀 한도를 높여야 할 때가 있습니다. Rustc가 사용하는 스택 프레임 수는 안정성 보장의 일부가 아니므로, 이 회귀가 반드시 문제였던 것은 아닙니다.
하지만 저는 즉시 경고 신호를 느꼈습니다. Rustdoc의 상당 부분은 Rustc API를 호출한 뒤 그 결과 정보를 정리하여 사용자에게 제시하는 일과 관련되어 있습니다. 따라서 Rustc가 이 코드를 성공적으로 컴파일하고 있는데 Rustdoc이 실패한다는 점은 우려스러웠습니다. 크레이트가 재노출하는 항목의 문서를 인라인하는 것 같은 크레이트 간 기능도 있습니다. std::vec::Vec는 실제로 alloc::vec::Vec이지만 문서에서는 자연스럽게 보입니다. 또한 워크스페이스 전반의 어떤 impl이 크레이트의 타입에 적용되는지도 표시합니다. 하지만 core::fmt의 무작위 트레이트가 거의 비어 있는 크레이트에 문서로 인라인될 이유는 전혀 떠오르지 않았습니다!
그런데 실제로 Rustdoc 로그는 이 트레이트의 문서를 인라인하려 하고 있음을 보여 주었습니다.
DEBUG rustdoc::clean::inline record_extern_trait: DefId(2:13427 ~ core[195b]::fmt::num_buffer::NumBufferTrait)
DEBUG rustdoc::clean trait_ref=Binder { value: <Self as core::fmt::num_buffer::NumBufferTrait>, bound_vars: [] }
외부 impl을 인라인하는 역할을 맡은 collect_trait_impls.rs 파일을 열어 보니 다음 코드가 있었습니다.
// "build_extern_trait_impls"라는 패스 안
for &cnum in tcx.crates(()) {
for &impl_def_id in tcx.trait_impls_in_crate(cnum) {
cx.with_param_env(impl_def_id, |cx| {
inline::build_impl(cx, impl_def_id, None, &mut new_items_external);
});
}
}
현재 크레이트의 모든 의존성에 대해 이 코드는 그곳에 정의된 각 트레이트 impl을 순회하고, 문서에 표시하기 적합한 impl 표현을 구성합니다. 따라서 알고리즘의 복잡도는 전체 의존성 그래프에 있는 트레이트 impl 수에 선형 비례하며, build_impl이 상당히 복잡한 함수이므로 큰 상수 계수도 붙습니다. 비용이 큽니다!
물론 Rustdoc은 이들 impl을 전부, 심지어 대부분도 실제 문서에 표시하지 않습니다. impl 수집 뒤 파일의 후반부에서 필터링하기 때문입니다. 이때 번뜩이는 생각이 들었습니다. 필터링을 먼저 수행하고 실제로 필요한 impl에 대해서만 build_impl을 호출하면 어떨까? 필터링 코드가 이미 처리된 표현을 받는다고 가정하고 있었고, 중간에는 Deref impl의 연쇄를 따라가는 까다로운 로직도 있어서 아무도 이전에 시도하지 않았던 것이라 추측했습니다. 그래도 에라 모르겠다, 그냥 해 보자고 생각했습니다.
먼저 너무 관대한 버전의 필터링 로직을 Rustc의 원시 rustc_middle::ty 데이터 구조에서 동작하도록 바꾼 뒤, 각 build_impl 호출 앞에 가드로 배치했습니다. Rustdoc의 주 테스트 모음을 실행했고… 통과했습니다. 와. 정말 고무적이었습니다.
이제 중복이 된 수집 후 필터를 삭제했습니다. 새 필터링 규칙이 너무 느슨했는데도 테스트 모음은 여전히 통과했습니다. 사실 필요하지 않은 impl을 남겨 두어도 항상 괜찮다는 점을 깨달았습니다. 이들은 자신이 관련된 문서 페이지, 예를 들어 self type이나 트레이트의 페이지에서만 실제로 나타납니다. 즉, 추가 impl은 Rustdoc을 느리게 할 뿐 정확성에는 영향을 주지 않습니다.
Deref impl의 연쇄를 따라가는 무서운 코드를 마주할 시간이었습니다. 대담해진 기분이었습니다. 그냥 삭제하면 어떨까? 이는 개선하려는 코드 조각에 얼마나 많은 동작이 의존하는지 확인하기 위해 제가 자주 시도하는 방법이기도 합니다. 빨간색으로 가득한 테스트 결과를 기다렸지만, 끝내 오지 않았습니다. 다음으로 Puppeteer를 사용해 실제 GUI 동작을 시험하는 확장 테스트 모음을 실행했습니다. 단 하나의 테스트만 실패했고, 이상하게도 Deref와는 아무 관련이 없었습니다. 대신 #[doc(notable_trait)] 테스트였습니다.
좋습니다. 배경 설명을 위한 짧은 곁가지 이야기입니다. Rustdoc에는 특수 속성으로 표시된 트레이트가 이를 구현하는 타입이 함수에서 반환될 때마다 작은 주석을 표시하게 하는 “주목할 만한 트레이트”라는 불안정 기능이 있습니다. 이것이 유용한 이유를 보려면 Iterator::map()을 생각해 보세요. 이 메서드는 Map이라는 타입을 반환하는데, 사용자에게는 딱히 의미 있는 이름이 아닙니다. 하지만 Iterator는 주목할 만한 트레이트로 표시되어 있으므로, Map 옆에 작은 정보 아이콘 ⓘ이 나타나 이것 역시 Iterator임을 알려 줍니다.
알고 보니 트레이트 impl 인라인 코드는 결정을 내릴 때 주목할 만한 트레이트 상태를 전혀 고려하지 않았습니다. 따라서 해당 툴팁을 검사하던 GUI 테스트는 우연히 통과했던 것입니다. 이 테스트는 Vec<u8>를 반환하는 함수가 Write의 주목할 만한 트레이트 툴팁을 표시하는지 확인했습니다. 제네릭 Vec<T>에서 &[T]로의 deref impl을 통해 Vec<u8>는 &[u8]로 deref되고, 이는 다시 Write를 구현합니다. 그 결과 Write impl이 Rustdoc의 컨텍스트에 로드되어 주목할 만한 트레이트 팝업에서 사용할 수 있게 되었던 것입니다!
필요한 #[doc(notable_trait)] 고려 사항을 추가하자 GUI 테스트는 통과했습니다. 하지만 이전에는 없던 많은 곳에 주목할 만한 트레이트 팝업이 갑자기 나타나면서 스냅샷 테스트 하나를 업데이트해야 했습니다. 코드를 정리하다가 잠재 버그까지 뜻밖에 수정하게 되면 언제나 기분이 좋습니다!
하지만 당연히 이 PR에서 가장 흥미로운 부분은 성능 결과였습니다. 벤치마크는 평균 **20%**의 wall-time 개선을 보여 주었습니다. 최대 상주 세트 크기(최대 메모리 사용량의 척도) 역시 12% 감소했습니다. 이 변경의 영향이 매우 컸던 이유는 build_extern_trait_impls 패스가 Rustdoc 실행 시간에서 상당한 비중을 차지하기 때문입니다. 아래는 변경 전의 flamegraph입니다.
이 성능 향상은 실증적 프로파일링 데이터와 기존 코드에 의문을 제기하려는 태도를 결합하는 힘을 잘 보여 준다고 생각합니다. 이 성공에 고무되어 더 밀어붙이기로 했습니다.
다음 두 PR은 원시 타입과 합성 impl을 더 똑똑하게 처리하여 성능을 개선했습니다. Rustdoc은 라이브러리 코드 어디에도 정의되어 있지 않고 컴파일러에 내장된 usize, str, [T] 같은 원시 타입을 문서화하기 위한 특별 지원을 갖추고 있습니다. 타입 자체는 내장이지만 표준 라이브러리는 그 위에 impl을 정의합니다. 예를 들어 str::as_bytes를 생각해 볼 수 있습니다. 이러한 문서를 표시하기 쉽게 하려고 표준 라이브러리는 Rustdoc이 이를 배치할 장소를 갖도록 특별한 #[rustc_doc_primitive] 속성을 사용합니다. collect_trait_impls.rs의 원시 타입 impl 인라인 로직이 원시 타입을 선언하지 않은 크레이트에서도 모든 크레이트에서 실행된다는 점을 발견했습니다. 거의 모든 크레이트가 원시 타입을 선언하지 않습니다. 복잡한 기술적 이유로 이 패스는 비용이 크므로 Rustdoc 실행 시간에 유의미한 부담을 더했습니다. 이를 로컬 원시 타입에서만 실행하도록 변경하여(따라서 대부분의 크레이트에서는 건너뛰도록 하여), 평균적으로 Rustdoc의 wall-time을 12%, 최대 RSS를 6% 개선했습니다.
다른 PR은 합성 impl에 관한 것이었습니다. 이는 자동 트레이트와 blanket impl을 위해 문서 페이지에서 우리가 합성하는 impl을 Rustdoc 코드베이스 내부에서 부르는 이름입니다. 이 용어가 무엇을 뜻하는지 설명하겠습니다. Send와 Sync는 자동 트레이트의 예입니다. 요구 사항을 충족하는 타입에 대해 컴파일러가 즉석에서 구현을 결정하므로, impl이 코드에 정의되어 있지 않습니다. 하지만 Rustdoc은 이러한 impl을 일반 impl처럼 문서에 표시할 수 있도록 표현을 구성합니다.
Blanket impl은 약간 다르지만 정신은 비슷합니다. 사용자 코드에 정의는 있지만 제네릭 타입에 대해 구현됩니다. 예를 들어 모든 타입 T에는 T: Clone인 경우 blanket impl<T> ToOwned for T가 적용됩니다. 따라서 이를 적용되는 각 타입의 페이지에 복사합니다.
이 모든 자동 및 blanket impl을 합성하는 일은 크레이트에 정의된 모든 타입을 순회한 뒤 각각에 대해 각 자동 트레이트와 각 blanket impl을 확인해야 하므로 비용이 큽니다. Rustdoc이 최종 문서에 전혀 나타나지 않는 타입, 예를 들어 비공개 타입에 대해서도 이 분석을 수행하고 있음을 발견했습니다. 문서화된 타입만 분석하도록 필터를 추가하여 wall-time을 평균 6%, hyper 같은 일부 실제 크레이트에서는 최대 13% 줄였습니다.
이 연작의 마지막 PR은 이전 변경 후 수집한 Rustdoc flamegraph를 검토하다가 시작되었습니다. Rustc의 param_env 쿼리가 build_extern_trait_impls 패스 시간의 무려 50%를 차지한다는 점을 발견했습니다.
이 쿼리는 본질적으로 항목(여기서는 impl)의 where 절과 부모로부터 상속한 절을 계산하고 정규화합니다. 이 작업이 싸지는 않지만 특별히 비싼 작업도 아닙니다. 시간이 그렇게 많이 걸린 이유는 크레이트 의존성 그래프의 모든 impl에서 호출되었기 때문입니다. 이전처럼 모든 impl을 실제로 _인라인_하는 것보다는 낫지만, 여전히 좋지 않습니다. impl 인라인을 결정하려면 impl의 self type을 살펴 그 타입이 인라인되는지 확인해야 합니다. 이 타입에 대한 Rustdoc 버전을 계산하려면 정규화가 필요할 수 있으므로 매개변수 환경이 필요합니다. 정규화란 타입에 관해 알고 있는 정보를 바탕으로 가능한 한 단순한 형태로 타입을 줄이는 것을 뜻합니다. 예를 들어 MyIter: Iterator<Item = MyStruct>임을 안다면 <MyIter as Iterator>::Item을 MyStruct로 정규화할 수 있습니다.
하지만 대부분의 경우 타입의 완전한 Rustdoc 버전을 계산하지 않아도 된다는 점을 깨달았습니다. self type의 _헤드_만 검사하면 됩니다. 여기서 “헤드”란 해당 타입이 가리키는 문서 페이지를 결정하는 가장 본질적인 부분을 의미합니다. Vec<i32>의 Vec나 &'a mut String의 String 같은 것입니다. 그리고 self type의 헤드가 정규화해야 하는 <MyIter as Iterator>::Item 같은 경우일 때만 param_env를 호출하면 됩니다.2 이 원칙에 따라 Rustdoc을 변경한 결과, clap_derive 같은 실제 크레이트를 포함한 벤치마크 모음 전반에서 평균 **18%**의 wall-time 속도 향상을 얻었습니다. 이 변경 뒤의 다른 flamegraph를 사용해, 인라인되지 않는 impl에 대한 param_env 호출을 피한 것이 개선의 원인임을 검증했습니다.
param_env가 차지하는 실행 시간 비율이 크게 줄어들고 build_impl이 지배적인 기여자로 남은 점에 주목하세요. 이제 이 패스의 실행 시간은 결국 건너뛸 impl이 아니라 실제로 인라인하려는 impl을 위한 작업이 지배합니다.
이 모든 변경 뒤 Rustdoc은 어떤 상태가 되었을까요? 벤치마크 모음 전반의 Rustdoc wall-time을 보여 주는 다음 그래프가 이를 가장 잘 보여 준다고 생각합니다.3
이 네 번의 하락은 각각 제 PR 하나에 대응합니다. Rustdoc은 이제 평균 33% 더 빨라졌습니다! 이 개선은 이미 nightly에 적용되었으며 Rust 1.99에서 stable에 반영될 예정입니다.
Flamegraph에서도 영향이 눈에 띕니다. 가장 많이 개선된 벤치마크 중 하나인 hyper에서 변경 전 build_extern_trait_impls가 차지하는 실행 시간 비율을 살펴보세요.
…그리고 변경 후입니다…
최근 Rustdoc 작업을 엿볼 수 있는 이 글을 즐겁게 읽으셨기를 바랍니다. 어떤 기술적 세부 사항보다도, 여러분이 가장 가져가기를 바라는 교훈은 직감을 믿고 가정에 의문을 제기하라는 것입니다. 코드 조각이든 무엇이든, 오랫동안 특정 방식으로 존재해 왔다는 사실이 그것이 최적이거나 심지어 올바르다는 뜻은 아닙니다. 직감이 무언가를 말한다면 귀 기울이고, 무엇을 발견할 수 있는지 깊이 파고드세요. 발견을 기다리는 큰 개선을 우연히 찾아낼지도 모릅니다.
추신: 이 프로젝트에 참여하는 일을 즐겁게 만들어 준 Rust 동료들에게 감사합니다.
정정: 처음 제목은 “한 주 만에 Rustdoc을 25% 더 빠르게 만든 방법”이었습니다. Nicholas Nethercote가 시간 25% 감소는 실제로 33% 속도 향상에 해당한다고 지적했습니다(). 더 좋네요! 이에 따라 글을 업데이트했습니다.
결국 우리의 트레이트 시스템은 _유명하게도 튜링 완전_합니다. ↩
사실 Rustdoc의 알고리즘은 <MyIter as Iterator>::Item 같은 한정 경로의 문서 페이지(따라서 인라인 결정)를 정규화된 값(MyStruct)이 아니라 self type(MyIter)만을 바탕으로 결정합니다. 그러므로 실제로는 self type 헤드를 정규화할 필요가 전혀 없으며 언제나 param_env를 건너뛸 수 있습니다. 이 동작은 다소 놀랍지만, 과거에 정규화를 활성화할 때 마주했던 문제 때문에 Rustdoc에는 정규화와 관련한 오래된 제한 사항이 있습니다. 따라서 지금은 이것이 최적이 아님에도 이 기존 동작을 재현하는 데 집중했습니다. ↩
데이터는 여러 벤치마크에 걸쳐 집계되므로, 그래프의 첫 시점 평균에 1.0이 대응하도록 수치가 정규화됩니다. ↩