JavaScript 컴파일러를 만들면서의 성능 추구

원문 게시물: https://rustmagazine.org/issue-3/javascript-compiler/

성능에 관하여

두 해 동안 루스트를 쓰면서 성능은 저에게 내재된 습관이 되었습니다 — 결국은 메모리 할당을 최소화하고 CPU 사이클 사용을 줄이는 것입니다.

그러나 문제 영역에 대한 지식이나 가능한 해결책에 대한 인지가 없다면, 최적의 성능을 달성하는 것은 어려울 수 있습니다.

다음 섹션에서는 제가 경험한 성능과 최적화에 관한 여정을 소개하겠습니다.
저의 학습 방식은 연구, 시행착오의 조합이므로, 다음 섹션들은 이러한 구조로 구성될 것입니다.

파싱

Oxc는 추상 구문 트리 (AST), 렉서, 그리고 재귀 하강 파서를 포함하는 표준 컴파일러입니다.

추상 구문 트리 (AST)

컴파일러의 첫 번째 아키텍처 설계는 그 자체의 AST입니다.

모든 자바스크립트 도구는 이 트리 기반으로 동작합니다. 예를 들어:

• 리너 (예: ESLint)는 오류를 찾기 위해 트리를 검사합니다
• 포맷터 (예: prettier)는 트리를 다시 자바스크립트 텍스트로 출력합니다
• 마이너 (예: terser)는 트리를 변환합니다
• 번들러는 서로 다른 파일들의 트리 간의 모든 import 및 export 문을 연결합니다

만약 트리가 사용자 친화적이지 않다면, 이런 도구들을 만드는 것은 매우 고통스러울 것입니다.

자바스크립트에서 가장 많이 사용되는 트리 사양은 estree입니다.
제가 처음으로 만든 트리 버전은 이 사양을 복제했습니다:

pub struct Program {
    pub node: Node,
    pub body: Vec<Statement>,
}

pub enum Statement {
    VariableDeclarationStatement(VariableDeclaration),
}

pub struct VariableDeclaration {
    pub node: Node,
    pub declarations: Vec<VariableDeclarator>,
}

루스트에서는 트리를 정의하는 것은 비교적 간단합니다. 구조체와 열거형을 사용하기 때문입니다.

메모리 할당

저는 파서를 작성하면서 몇 달 동안 이 트리 버전을 다뤄왔습니다.
어느 날, 프로파일링을 시도하게 되었고, 프로파일러는 프로그램이 drop 호출에 많은 시간을 소비하고 있음을 보여주었습니다.

💡 트리의 노드는 Box 또는 Vec를 통해 힙에 할당되며, 개별적으로 할당되기 때문에 순차적인 순서로 드롭됩니다.

이 문제를 완화할 수 있는 방법이 있을까요?

그때 저는 파서 작업 중에 루스트로 작성된 다른 자바스크립트 파서를 살펴보았습니다. 주로 ratel과 jsparagus.

이 두 파서 모두 자신의 트리에 라이프타임 주석을 사용합니다:

pub enum Statement<'ast> {
    Expression(ExpressionNode<'ast>),
}

또한 arena.rs라는 보조 파일을 가지고 있습니다.

제가 이 파일의 역할을 이해하지 못해, 그들이 메모리 아레나 사용에 대해 읽기 전까지 무시했습니다:
bumpalo와 toolshed.

요약하자면, 메모리 아레나는 미리 크기 단위나 페이지 단위로 메모리를 할당하며, 아레나가 드롭될 때 함께 해제합니다.
이 트리는 아레나에 할당되어 있으므로, 트리 드롭은 매우 빠른 연산입니다.

또 다른 좋은 부가 효과는, 트리가 특정 순서로 구성되고, 트리 순회도 같은 순서를 따르기 때문에 방문 과정에서 선형 메모리 접근이 발생한다는 점입니다.
이 접근 패턴은 인접한 메모리가 페이지 단위로 CPU 캐시에 로드되기 때문에 효율적이며, 더 빠른 접근 시간을 제공합니다.

불행히도, 루스트 초보자에게는 메모리 아레나 사용이 어렵습니다. 모든 데이터 구조와 관련 함수는 라이프타임 주석으로 매개변수화되어야 하기 때문입니다.
저는 bumpalo 내부에 트리를 할당하기까지 5번의 시도를 해야 했습니다.

아레나 방식으로 트리 구조를 변경함으로써 약 20%의 성능 향상을 얻을 수 있었습니다.

열거형 크기

트리의 재귀적 특성 때문에, "간접 없이 재귀" 에러를 피하기 위해 타입을 정의해야 합니다:

오류[E0072]: 재귀적인 타입 `Enum`과 `Variant`는 무한한 크기를 가짐
 --> crates/oxc_linter/src/lib.rs:1:1
  |
1 | enum Enum {
  | ^^^^^^^^^
2 |     Variant(Variant),
  |             ------- 간접 없이 재귀
3 | }
4 | struct Variant {
  | ^^^^^^^^^^^^^^
5 |     field: Enum,
  |            ---- 간접 없이 재귀
  |
도움말: 사이클을 깨기 위해 어떤 간접성(예: `Box`, `Rc`, 또는 `&`)을 삽입하십시오
  |
2 ~     Variant(Box<Variant>),
3 | }
4 | struct Variant {
5 ~     field: Box<Enum>,

이 문제를 해결하는 방법은 두 가지입니다. 먼저 열거형 변수 안에 열거형을 박싱하거나, 구조체 필드를 박싱하는 것입니다.

저는 2017년 루스트 포럼에서 비슷한 질문을 발견했습니다:
추상 구문 트리를 표현하는 더 나은 방법이 있을까?

Aleksey (matklad)는 Expression 열거형을 작게 유지하기 위해 열거형 변수를 박싱하라고 제안했습니다. 하지만 이 말은 무엇을 의미할까요?

실제로, 루스트의 열거형 메모리 레이아웃은 모든 변형의 크기에 따라 달라지며, 전체 바이트 크기는 가장 큰 변형에 의해 결정됩니다.
예를 들어 다음 열거형은 56바이트를 차지합니다 (태그용 1바이트, 페이로드용 48바이트, 정렬용 8바이트):

enum Enum {
    A, // 0바이트 페이로드
    B(String), // 24바이트 페이로드
    C { first: String, last: String }, // 48바이트 페이로드
}

일반적인 자바스크립트 트리에서 Expression 열거형은 45개의 변형을, Statement 열거형은 20개의 변형을 포함합니다. 이들은 열거형 변수로 박싱되지 않았다면 200바이트 이상을 차지합니다.
이 200바이트는 항상 전달되어야 하며, matches!(expr, Expression::Variant(_)) 확인 시마다 접근해야 하므로, 성능 면에서 캐시 친화적이지 않습니다.

따라서 메모리 접근을 효율적으로 만들기 위해서는 열거형 변수를 박싱하는 것이 가장 좋습니다.

perf-book에는 큰 타입을 찾는 방법에 대한 추가 정보가 있습니다.

또한 작은 열거형 크기를 제한하는 테스트도 복사했습니다.

#[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
#[test]
fn no_bloat_enum_sizes() {
    use std::mem::size_of;
    use crate::ast::*;
    assert_eq!(size_of::<Statement>(), 16);
    assert_eq!(size_of::<Expression>(), 16);
    assert_eq!(size_of::<Declaration>(), 16);
}

열거형 변수 박싱으로 인해 약 10%의 속도 향상이 이루어졌습니다.

스팬

때로는 데이터 구조를 더 깊이 분석해보지 않으면, 더 작은 메모리 프로필이 가능하다는 것을 알 수 없습니다.

이 경우, 모든 트리 노드의 리프에는 소규모 데이터 구조인 “스팬”이 포함되어 있으며, 원본 텍스트로부터의 바이트 오프셋을 저장하고, 두 개의 usize로 구성됩니다.

pub struct Node {
    pub start: usize,
    pub end: usize,
}

이 문제를 지적받았습니다: usize를 u32로 변경하면 피크 메모리 사용량을 줄일 수 있습니다.
왜냐하면 u32보다 큰 값은 4GB 파일을 의미하기 때문입니다.

u32로 변경함으로써 대용량 파일에서 약 5%의 성능 향상이 이루어졌습니다 (더 자세한 내용 보기).

문자열과 식별자

트리 내부에서 식별자 이름과 문자열 리터럴에 원본 텍스트의 문자열 참조를 사용하려 할 수 있습니다.

pub struct StringLiteral<'a> {
    pub value: &'a str,
}

pub struct Identifier<'a> {
    pub name: &'a str,
}

하지만 불행히도 자바스크립트에서는 문자열과 식별자가 이스케이프 시퀀스를 가질 수 있습니다.
예를 들어, '\251', '\xA9' 및 '©' 는 모두 저작권 기호에 해당합니다.

이는 이스케이프 값을 계산하고 새로운 String을 할당해야 함을 의미합니다.

문자열 인터닝

많은 힙에 할당된 문자열이 존재할 경우, 문자열 인터닝이라는 기술을 사용하여 동일한 문자열 값은 하나만 저장함으로써 전체 메모리 사용량을 줄일 수 있습니다.

string-cache는 Servo 팀에서 출시한 인기 있고 널리 사용되는 라이브러리입니다.
처음에는 제가 트리 내의 식별자와 문자열에 이 라이브러리를 사용했습니다.
단일 스레드에서는 파서 성능이 매우 빠르게 느껴졌지만, 여러 파서가 레이븐과 함께 병렬로 실행되는 리너를 구현하기 시작하면서, 모든 코어의 평균 50% 정도의 사용률이었습니다.

프로파일링 결과, parking_lot::raw_mutex::RawMutex::lock_slow 메서드가 실행 시간 상위에 나타났습니다.
저는 잠금과 멀티코어 프로그래밍에 대해 잘 몰랐지만, 글로벌 잠금 자체가 이미 이상했기 때문에, string-cache 라이브러리를 제거해 완전한 CPU 활용도를 확보하기로 결심했습니다.

트리에서 string-cache를 제거함으로써 병렬 파싱 성능이 약 30% 향상되었습니다.

string-cache

반 년 후, 또 다른 성능 중심 프로젝트를 진행하던 중, string-cache 라이브러리가 다시 등장했습니다.
병렬 텍스트 파싱 중 모든 스레드를 막고 있었습니다.

저는 이번에는 이 라이브러리가 어떻게 동작하는지 공부하기로 결심했습니다.
마라 보스의 책 루스트 아톰과 잠금을 읽은 덕분에 준비가 됐습니다.

아래는 잠금 주변의 관련 코드와 코드입니다.
참고로 이 코드는 2015년에 8년 전에 작성되었습니다.

pub(crate) static DYNAMIC_SET: Lazy<Mutex<Set>> = Lazy::new(|| {
    Mutex::new({

// ... 다른 위치
let ptr: std::ptr::NonNull<Entry> =
    DYNAMIC_SET.lock().insert(string_to_add, hash.g);

간단 명료합니다. 문자열을 삽입할 때마다 Set 데이터 구조를 잠금합니다.
이 함수는 파서 내에서 자주 호출되므로, 동기화로 인해 성능에 부정적인 영향을 받습니다.

이제 Set 데이터 구조를 살펴봅시다:

pub(crate) fn insert(&mut self, string: Cow<str>, hash: u32) -> NonNull<Entry> {
    let bucket_index = (hash & BUCKET_MASK) as usize;
    {
        let mut ptr: Option<&mut Box<Entry>> = self.buckets[bucket_index].as_mut();

        while let Some(entry) = ptr.take() {
            if entry.hash == hash && *entry.string == *string {
                if entry.ref_count.fetch_add(1, SeqCst) > 0 {
                    return NonNull::from(&mut **entry);
                }
                entry.ref_count.fetch_sub(1, SeqCst);
                break;
            }
            ptr = entry.next_in_bucket.as_mut();
        }
    }
    debug_assert!(mem::align_of::<Entry>() >= ENTRY_ALIGNMENT);
    let string = string.into_owned();
    let mut entry = Box::new(Entry {
        next_in_bucket: self.buckets[bucket_index].take(),
        hash,
        ref_count: AtomicIsize::new(1),
        string: string.into_boxed_str(),
    });
    let ptr = NonNull::from(&mut *entry);
    self.buckets[bucket_index] = Some(entry);

    ptr
}

이미 보이듯이, 문자열을 저장할 버킷을 찾아보고, 버킷에 없으면 삽입합니다.

💡 이것은 선형 탐색인가요? 만약 그렇다면 이 Set은 단지 HashMap이라고 말하지 않을 뿐, 사실상 HashMap입니다.
💡 만약 이것이 HashMap이라면, Mutex<HashMap>는 동시성 HashMap입니다.

이 문제를 알고 있다면 해결책은 간단해 보이지만, 저는 이 문제가 있다는 것을 몰라 한 달이 걸렸습니다.
이것이 단순히 동시성 HashMap이라는 점이 명확해지자, 전체 HashMap이 아닌 버킷에 Mutex를 적용하는 것이 명확하고 논리적인 해결책임을 알게 되었습니다.
이 변경을 실시한 지 1시간 만에 플러그인 요청을 제출하고, 결과에 매우 만족했습니다 😃.

https://github.com/servo/string-cache/pull/268

문자열 인터닝은 루스트 커뮤니티 내에서 경쟁이 치열한 분야입니다.
이 블로그 포스트의 예제처럼, 단일 스레드용 라이브러리로는 string-interner, lasso, lalrpop-intern, intaglio, strena 등이 있습니다.

파일을 병렬로 파싱하기 때문에, 멀티스레드용 문자열 인터너 라이브러리인 ustr를 사용하는 것도 옵션입니다.
하지만 ustr와 개선된 string-cache 버전을 프로파일링한 결과, 아래에서 설명할 방식보다는 여전히 성능이 부족함이 분명해졌습니다.

성능이 좋지 않은 것으로 추측되는 이유는 다음과 같습니다:

• 해시 처리 — 인터너는 중복 제거를 위해 문자열을 해시해야 함
• 간접 참조 — "멀리" 힙에서 문자열 값을 읽어야 하므로 캐시 친화적이지 않음

문자열 인라인

결국 우리는 많은 문자열 할당을 피해야 하는 초기 문제로 돌아옵니다.
다행히, 우리가 다루는 데이터의 종류를 살펴보면 부분적인 해결책이 있습니다:
짧은 자바스크립트 변수 이름과 일부 짧은 문자열.
이를 위해 문자열 인라인 기법을 사용할 수 있습니다.
이 기법은 문자열의 모든 바이트를 스택에 저장합니다.

핵심적으로, 우리는 다음 열거형을 사용해 문자열을 저장하고자 합니다.

enum Str {
    Static(&'static str),
    Inline(InlineReprensation),
    Heap(String),
}

열거형의 크기를 최소화하기 위해 InlineRepresentation은 String과 동일한 크기를 가져야 합니다.

#[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
#[test]
fn test_size() {
    use std::mem::size_of;
    assert_eq!(size_of::<String>(), size_of::<InlineReprensation>());
}

루스트 커뮤니티에는 많은 크레이트들이 메모리 사용량을 최적화하기 위해 노력하고 있습니다.
이 또한 또 다른 전장입니다.
가장 인기 있는 것은

• smol_str
• smartstring
• compact_str
• flexstr

각각의 크레이트는 고유한 특징과 메모리 최적화를 위한 접근 방식을 갖고 있어, 선택할 때 다양한 트레이드오프와 고려사항이 생깁니다.
예를 들어 smol_str과 flexstr는 복제가 O(1)입니다. flexstr는 22바이트, smol_str과 smartstring은 23바이트, compact_str는 64비트 시스템에서 24바이트까지 저장할 수 있습니다.

https://fasterthanli.me는 이 주제에 대해 깊이 있는 탐색을 제공합니다.

String을 compact_str::CompactStr로 변경함으로써, 메모리 할당량이 크게 감소했습니다.

렉서

토큰

렉서(또는 토크나이저)의 역할은 소스 텍스트를 구조화된 데이터인 토큰으로 변환하는 것입니다.

pub struct Token {
    pub kind: Kind,
}

이를 쉽게 다룰 수 있도록, 토큰 종류는 일반적으로 루스트에서 열거형으로 정의됩니다.
열거형의 변형은 각 토큰에 해당하는 데이터를 보유합니다.

pub enum Kind {
    // 키워드
    For,
    While,
    ...
    // 리터럴
    String(String),
    Num(f64),
    ...
}

현재 이 열거형은 32바이트를 사용하며, 렉서는 종종 수백만 개의 이 토큰 Kind를 생성해야 합니다.
매번 Kind::For 또는 Kind::While를 생성할 때마다 스택에 32바이트의 메모리를 할당해야 합니다.

이 문제를 개선하는 현명한 방법은 열거형 변형을 분리하여 Kind를 단일 바이트로 유지하고, 값은 다른 열거형으로 옮기는 것입니다.

pub struct Token<'a> {
    pub kind: Kind,
    pub value: TokenValue
}

pub enum TokenValue {
    None,
    String(String),
    Num(f64),
}

우리는 모든 파싱 코드를 제어하고 있으므로, 반드시 토큰 종류에 맞는 토큰 값이 항상 선언되도록 해야 합니다.

TokenValue가 32바이트인 것은 이미 꽤 작지만, 자주 할당되기 때문에 성능에 부정적인 영향을 줄 수 있습니다.

이제 String 형식을 살펴보고, 코드 에디터의 "정의로 이동" 기능을 이용해 따라가보겠습니다.
String → Vec → RawVec:

pub struct String {
    vec: Vec<u8>,
}

pub struct Vec {
    buf: RawVec<T, A>,
    len: usize,
}

pub struct RawVec {
    ptr: Unique<T>,
    cap: usize,
    alloc: A,
}

광고대로 String은 단지 u8의 Vec이며, Vec는 길이와 용량 필드를 갖습니다.
이 문자열을 수정하지 않을 것이므로, 메모리 사용량 최적화를 위해 용량 필드를 제거하고 문자열 슬라이스 (&str)를 사용하는 것이 좋습니다.

pub enum TokenValue<'a> {
    None,
    String(&'a str),
    Num(f64),
}

TokenValue는 24바이트로 줄어듭니다.

TokenValue에서 String 대신 &str를 사용하면 메모리 사용량이 줄어들지만, 라이프타임 주석을 추가해야 하는 단점이 있습니다.
이는 빌더 체커 문제를 일으키고, 라이프타임 주석이 코드베이스 전체로 전파되어 관리가 다소 어려워집니다.
저는 8개월 전에 빌더 체커 게임에서 진 적이 있지만, 이 문제를 다시 들여다볼 때 마침내 승리했습니다.

필요할 때마다 참조 대신 소유된 불변 데이터의 버전을 사용하는 것이 항상 좋습니다. 예를 들어 String에 Box<str>를, Vec<u8>에 Box<[u8]>을 사용할 수 있습니다.

요약하자면, 언제든지 우리의 데이터 구조를 작게 유지하기 위한 트릭을 생각할 수 있으며, 이를 통해 종종 성능 향상의 보상을 얻을 수 있습니다.

Cow

저는 Cow라는 용어를 처음 접한 것은 jsparagus의 코드를 공부할 때였습니다.
이 코드에는 AutoCow라는 인프라가 있습니다: [https://github.com/mozilla-spidermonkey/jsparagus/blob/212f6bdbc2cae909e7d5cfebf36284560c3c4ef4/crates/parser/src/lexer.rs#L2256]

저는 코드가 무엇을 하고 있는지 모호하게 이해했고,
자바스크립트 문자열이 토큰화될 때, 이스케이프 시퀀스를 만나면 새 문자열을 할당하고, 그렇지 않으면 원본 문자열 슬라이스를 반환합니다:

fn finish(&mut self, lexer: &Lexer<'alloc>) -> &'alloc str {
    match self.value.take() {
        Some(arena_string) => arena_string.into_bump_str(),
        None => &self.start[..self.start.len() - lexer.chars.as_str().len()],
    }
}

이렇게 하는 것은 똑똑한데, 99.9%의 경우 새 문자열을 할당하지 않기 때문입니다. 왜냐하면 이스케이프 문자열은 드물기 때문입니다.

하지만 Cow 또는 "클론-온-라이트 스마트 포인터"라는 용어는 제게는 여전히 의미가 없었습니다.

Cow는 클론-온-라이트 기능을 제공하는 스마트 포인터입니다. 이것은 빌림된 데이터를 포함하고 불변으로 접근할 수 있으며, 변경이나 소유권 요구 시 지연적으로 데이터를 복제합니다. 이 타입은 Borrow 트레이트를 통해 일반적인 빌림된 데이터와 함께 작동하도록 설계되었습니다.

루스트 초보자라면(저처럼), 이 설명은 도움이 되지 않습니다 (그래도 여전히 이게 무슨 말인지 모르겠네요).

이 문제를 지적받았습니다: 클론-온-라이트는 이 데이터 구조의 하나의 사용 사례일 뿐입니다. 더 나은 이름은 RefOrOwned이어야 합니다. 왜냐하면 이 타입은 소유 데이터 또는 참조를 포함하기 때문입니다.

SIMD

옛날 루스트 블로그를 읽다가, 포터블 SIMD 프로젝트 그룹 발표가 눈에 들어왔습니다.
항상 이 기술을 실험해보고 싶었지만 기회가 없었습니다.
조사를 통해 파서에 적용할 수 있는 사례를 발견했습니다:
문자열에서 공백을 얼마나 빠르게 제거할 수 있나요? — Daniel Lemire.

결국 이 기술은 이미 있었으며, 빠른 파서인 RapidJSON에서 SIMD를 사용해 공백을 제거했다고 합니다.

최종적으로 포터블 SIMD와 RapidJSON의 코드를 참고해,
공백을 건너뛰는 것뿐만 아니라 다중 줄 주석을 건너뛰는 것도 성공적으로 구현했습니다.

이 두 가지 변경으로 성능이 몇 % 향상되었습니다.

키워드 매칭

성능 프로파일 상단에는 총 실행 시간의 약 1~2%를 차지하는 핫 코드 경로가 있습니다.

이 코드는 문자열을 자바스크립트 키워드와 매칭하려 합니다:

fn match_keyword(s: &str) -> Self {
    match s {
        "as" => As,
        "do" => Do,
        "if" => If,
        ...
        "constructor" => Constructor,
        _ => Ident,
    }
}

타입스크립트가 추가되면서, 매칭해야 할 문자열은 84개가 됩니다.
조사를 통해, V8의 블로그 아주 빠른 파싱, 1부: 스캐너 최적화를 발견했습니다.
이 블로그는 키워드 매칭 코드에 대해 자세히 설명하고 있습니다.

키워드 목록은 정적일 수 있으므로, 각 식별자에 대해 최대 하나의 후보 키워드를 제공하는 완벽한 해시 함수를 계산할 수 있습니다. V8는 이 함수를 계산하기 위해 gperf를 사용합니다. 결과적으로 길이와 첫 두 식별자 문자를 기반으로 해시를 계산하여 단일 후보 키워드를 찾습니다. 입력 식별자 길이와 키워드 길이가 일치할 경우에만 식별자와 키워드를 비교합니다.

따라서 빠른 해시와 정수 비교는 84개의 문자열 비교보다 훨씬 빠릅니다.
하지만 다시 시도하고 다시 시도해봤지만, 아무런 성과 없었습니다.

결국 LLVM이 이미 코드를 최적화했음을 알게 되었습니다.
rustc에 --emit=llvm-ir를 사용하면 관련 코드를 확인할 수 있습니다:

switch i64 %s.1, label %bb6 [
  i64 2, label %"_ZN4core5slice3cmp81_$LT$impl$u20$core..cmp..PartialEq$LT$$u5b$B$u5d$$GT$$u20$for$u20$$u5b$A$u5d$$GT$2eq17h46d405acb5da4997E.exit.i"
  i64 3, label %"_ZN4core5slice3cmp81_$LT$impl$u20$core..cmp..PartialEq$LT$$u5b$B$u5d$$GT$$u20$for$u20$$u5b$A$u5d$$GT$2eq17h46d405acb5da4997E.exit280.i"
  ...
  i64 11, label %"_ZN4core5slice3cmp81_$LT$impl$u20$core..cmp..PartialEq$LT$$u5b$B$u5d$$GT$$u20$for$u20$$u5b$A$u5d$$GT$2eq17h46d405acb5da4997E.exit665.i"
], !dbg !191362

%s는 문자열이고, %s.1은 길이입니다 ... 컴파일러는 문자열 길이를 기준으로 분기하고 있습니다! 컴파일러가 우리보다 더 똑똑하네요 😃.

(네, 이 문제에 너무 진지하게 임해서, 실제로 LLVM IR과 어셈블리 코드까지 살펴보기 시작했습니다.)

후에 @strager는 이 주제에 대해 매우 교육적인 유튜브 영상 루스트와 C++보다 빠른: 완벽한 해시 테이블을 공유했습니다.
이 영상은 성능 문제를 세밀하게 최적화하는 체계적인 접근법을 알려주었습니다.

결국, 간단한 키워드 매칭이 충분하다는 결론을 내렸습니다. 왜냐하면 이 부분은 성능의 약 1~2%에 불과했고, 몇 일간 노력해도 그 가치가 없었기 때문입니다 — 루스트는 이 완벽한 해시맵을 만들기 위한 모든 요소를 갖추지 못했습니다.

리너

리너는 소스 코드에 문제를 분석하는 프로그램입니다.

가장 간단한 리너는 각 트리 노드를 방문하고 규칙을 검사합니다.
방문자 패턴을 사용할 수 있습니다:

pub trait Visit<'a>: Sized {
    // ... 많은 방문 함수

    fn visit_debugger_statement(&mut self, stmt: &'a DebuggerStatement) {
        // 오류 보고
    }
}

부모 포인터 트리

방문자를 사용해 트리를 아래로 내려가는 것은 쉬운 일이지만, 위로 올라가서 정보를 수집하고 싶다면 어떨까요?

이 문제는 특히 루스트에서 해결하기가 어렵습니다. 왜냐하면 트리 노드에 포인터를 추가하는 것이 불가능하기 때문입니다.

일단 트리를 잠시 잊고, 노드가 부모 포인터를 가지는 특성을 가진 일반 트리에 집중해보겠습니다.
일반 트리를 만들기 위해 각 트리 노드는 동일한 타입 Node여야 하며, 부모를 참조하기 위해 Rc를 사용할 수 있습니다:

struct Node {
    parent: Option<Rc<Node>>,
}

변경이 필요할 경우 이 패턴을 사용하는 것은 번거롭고, 노드가 서로 다른 시점에 드롭되어야 하므로 성능이 좋지 않습니다.

더 효율적인 해결책은 Vec를 배킹 스토리지로 사용하고, 인덱스를 포인터로 사용하는 것입니다.

struct Tree {
    nodes: Vec<Node>
}

struct Node {
    parent: Option<usize> // `nodes` 내 인덱스
}

indextree는 이 작업에 좋은 라이브러리입니다.

우리의 트리로 돌아와, 각 노드가 트리의 모든 종류의 노드를 래핑하는 열거형을 가리키도록 만들어 indextree를 만들 수 있습니다.
이 트리를 우리는 무형 트리라고 부릅니다.

struct Node<'a> {
    kind: AstKind<'a>
}

enum AstKind<'a> {
    BlockStatement(&'a BlockStatement<'a>),
    // ...
    ArrayExpression(&'a ArrayExpression<'a>),
    // ...
    Class(&'a Class<'a>),
    // ...
}

마지막으로, 이 트리를 만드는 방문자 패턴 내의 콜백이 필요합니다.

pub trait Visit<'a> {
    fn enter_node(&mut self, _kind: AstKind<'a>) {}
    fn leave_node(&mut self, _kind: AstKind<'a>) {}

    fn visit_block_statement(&mut self, stmt: &'a BlockStatement<'a>) {
        let kind = AstKind::BlockStatement(stmt);
        self.enter_node(kind);
        self.visit_statements(&stmt.body);
        self.leave_node(kind);
    }
}

impl<'a> Visit<'a> for TreeBuilder<'a> {
    fn enter_node(&mut self, kind: AstKind<'a>) {
        self.push_ast_node(kind);
    }

    fn leave_node(&mut self, kind: AstKind<'a>) {
        self.pop_ast_node();
    }
}

최종 데이터 구조는 indextree::Arena<Node<'a>>가 되며, 각 Node는 AstKind<'a>를 가리킵니다.
indextree::Node::parent를 호출하면 어떤 노드의 부모를 얻을 수 있습니다.

이 부모 포인터 트리를 만드는 장점은, 별도의 방문자 구현 없이도 트리 노드를 방문하기가 편리하다는 점입니다.
리너는 이제 indextree 내의 모든 노드를 단순히 반복하는 것으로 끝납니다:

for node in nodes {
    match node.get().kind {
        AstKind::DebuggerStatement(stmt) => {
        // 오류 보고
        }
        _ => {}
    }
}

완전한 예제는 여기에 제공됩니다.

처음에는 이 과정이 느리고 비효율적으로 보일 수 있습니다.
하지만 메모리 아레나를 통한 타입화된 트리 방문과 indextree에 포인터를 삽입하는 것은 효율적인 선형 메모리 접근 패턴입니다.
현재 벤치마킹 결과, 이 접근법은 ESLint보다 84배 빠르며, 우리의 목적에 충분히 빠릅니다.

병렬로 파일 처리

리너는 디렉토리 탐색을 위해 ignore 라이브러리를 사용합니다.
.gitignore를 지원하고, .eslintignore와 같은 추가 무시 파일도 추가할 수 있습니다.

이 라이브러리의 작은 문제는 병렬 인터페이스가 없다는 점입니다.
ignore::Walk::new(".")에는 par_iter가 없습니다.

대신, 기초적인 원시 제공이 필요합니다.

let walk = Walk::new(&self.options);
rayon::spawn(move || {
    walk.iter().for_each(|path| {
        tx_path.send(path).unwrap();
    });
});

let linter = Arc::clone(&self.linter);
rayon::spawn(move || {
    while let Ok(path) = rx_path.recv() {
        let tx_error = tx_error.clone();
        let linter = Arc::clone(&linter);
        rayon::spawn(move || {
            if let Some(diagnostics) = Self::lint_path(&linter, &path) {
                tx_error.send(diagnostics).unwrap();
            }
            drop(tx_error);
        });
    }
});

이 방식은 단일 스레드에서 모든 진단을 출력할 수 있는 유용한 기능을 활성화합니다. 이로 인해 이 문서의 마지막 주제로 이어집니다.

출력이 느림

진단을 출력하는 것은 빠르게 느껴졌지만, 저는 이 프로젝트에 너무 오래 몰두해 있어서, 거대한 모노레포에서 리너를 실행할 때마다 수천 개의 진단 메시지를 출력하는 것이 무척 오랜 시간처럼 느껴졌습니다.
그래서 저는 루스트의 깃허브 이슈를 검색하기 시작했고, 관련된 이슈를 발견했습니다:

• io::Stdout는 적절한 경우 블록 버퍼링을 사용해야 한다
• stdin 및 stdout 성능 고려 사항이 문서화되어 있지 않다

요약하자면, println! 호출은 줄 바꿈을 만나면 매번 stdout을 잠근다는 점입니다. 이를 줄 버퍼링이라고 합니다.
더 빠르게 출력하려면 블록 버퍼링을 사용해야 하며, 이는 여기에 문서화되어 있습니다.

use std::io::{self, Write};

let stdout = io::stdout(); // 전역 출력 엔티티를 가져옴
let mut handle = io::BufWriter::new(stdout); // 선택적으로 이 핸들을 버퍼로 감싸기
writeln!(handle, "foo: {}", 42); // 오류를 걱정한다면 `?`를 추가하세요

또는 stdout의 잠금을 획득할 수도 있습니다.

let stdout = io::stdout(); // 전역 출력 엔티티를 가져옴
let mut handle = stdout.lock(); // 잠금을 획득
writeln!(handle, "foo: {}", 42); // 오류를 걱정한다면 `?`를 추가하세요