Rust arena로 Gleam의 3년 묵은 성능 이슈 해결하기

 (giacomocavalieri.me)
1P by GN⁺ | ★ favorite | 댓글 1개
  • Gleam 포매터의 재귀적 Document 구조에서 반복되던 개별 힙 할당을 arena 기반 참조로 바꿔, 3년간 남아 있던 성능 개선 이슈를 해결함
  • Box<Self>를 arena에 저장된 &Self로 교체하고, Rust의 수명 검사로 arena가 제거된 뒤 내부 데이터가 참조되지 않도록 보장함
  • 언어 키워드와 쉼표처럼 반복되는 Document 수백 개를 한 번만 할당해 재사용하면서 프리티 프린터 실행 시간이 13ms에서 9.8ms로 줄어 24% 빨라짐
  • 소스 읽기와 파싱을 포함한 전체 gleam format 실행 시간도 13% 단축됐으며, 최대 메모리 사용량은 8.4MB에서 7.6MB로 약 10% 감소함
  • arena를 전달하도록 함수와 호출부를 광범위하게 고쳐야 해 +2963/-1032 규모의 수작업이 필요했지만, 반복적인 개별 할당을 줄이는 방식으로 속도와 메모리 사용량을 함께 개선할 수 있었음

재귀적 Document 구조에서 발생한 할당 비용

  • Gleam의 프리티 프린터는 코드를 어떻게 출력하고, 줄 제한을 넘을 때 어디서 나눌지를 나타내는 재귀적 Document 자료구조를 사용함
  • 주요 variant는 출력할 문자열을 담는 String, 줄바꿈 전후 문자열을 정의하는 Break, 여러 문서를 묶는 Group, 줄바꿈 시 들여쓰기를 늘리는 Nest 등으로 구성됨
  • 리스트 [1, 2]도 String, Break, Nest, Group을 조합해 표현함
    • 현재 줄에 들어가면 [1, 2]처럼 한 줄로 출력함
    • 줄 제한을 넘으면 지정된 Break에 따라 여러 줄로 나누고 들여쓰며 마지막 쉼표도 출력함
  • Nest처럼 다른 Document를 내부에 담는 variant는 기존에 Box<Self>를 사용했기 때문에 중첩 문서마다 힙에 개별 할당해야 했고, 이 작업이 실행 시간의 상당 부분을 차지할 수 있었음
  • Gleam 프리티 프린터의 기반 알고리듬은 Strictly Pretty 논문에서 확인할 수 있음

Box를 arena 참조로 교체

  • 기존 Nest(Box<Self>)를 Nest(&'doc Self)로 바꿔 arena에 저장된 다른 Document를 참조하도록 구조를 변경함
  • 참조를 담기 위해 문자열 수명 'string과 별도로 문서 데이터의 수명 'doc을 Document에 추가함
  • 구현에는 typed_arena 크레이트를 사용함
    • alloc으로 값을 arena에 저장하면 해당 값의 참조가 반환됨
    • 할당된 데이터는 arena가 살아 있는 동안 사용할 수 있음
    • arena가 범위를 벗어나면 내부 데이터도 함께 제거됨
  • alloc(&self, value: T) -> &mut T가 반환하는 참조는 arena보다 오래 살 수 없으며, Rust의 대여 검사기(borrow checker) 가 arena 제거 후의 잘못된 참조를 차단함

반복되는 문서를 한 번만 할당해 재사용

  • arena는 다른 문서를 참조하는 용도뿐 아니라 코드 전반에서 반복되는 Document를 캐시하는 데도 활용됨
  • String("fn"), String("pub"), String("type")처럼 언어 키워드를 나타내는 문서를 매번 새로 만들 필요가 없어짐
  • 목록 항목 사이에 쓰는 Break { unbroken: ", ", broken: "," } 같은 문서도 한 번 할당한 뒤 재사용함
  • 기존에는 계속 Box에 넣어야 했던 수백 개의 작은 문서를 각각 한 번만 할당할 수 있게 됨

단순한 API와 광범위한 호출부 변경

  • arena API 자체는 단순하지만, 기존 코드의 큰 부분을 전환하는 과정에는 반복적인 수정이 필요했음
  • 이전에 Box::new만 호출하던 함수들은 이제 데이터를 할당할 arena 인수를 추가로 받아야 함
  • format_list 같은 함수는 목록 항목을 포맷하는 하위 함수에도 같은 arena를 전달하고, 중첩 문서를 Box::new 대신 arena.alloc으로 생성하도록 바뀜
  • 며칠간 신중하게 검색·치환한 끝에 +2963/-1032 규모의 pull request로 작업을 완료함
  • 반복적이고 수동적인 작업이었으며, 이 과정에서 LLM은 사용하지 않았음

속도와 최대 메모리 사용량 개선

  • 실제 Gleam 프로젝트인 squirrel을 포맷할 때 프리티 프린터 실행 시간이 13ms에서 9.8ms로 감소함
    • 프리티 프린터만 비교하면 24% 성능 향상임
  • gleam format은 포맷 외에도 프로젝트 소스 코드를 읽고 파싱하므로 프리티 프린터가 전체 작업의 일부만 차지하지만, 전체 실행 시간도 13% 단축됨
  • 최대 메모리 사용량은 8.4MB에서 7.6MB로 줄어 약 10% 감소함
  • arena로 개별 힙 할당 횟수를 줄인 결과, 포매터의 실행 속도가 빨라지고 메모리 사용량도 함께 감소함

함께 보면 좋은 글 β

GN⁺   [-]
Lobste.rs 의견들

  • 최고 메모리 사용량을 10% 더 줄이고 싶다면 참조 대신 불투명 핸들을 반환하는 다른 아레나를 고려할 만함. 핸들을 64비트 대신 16비트나 32비트로 만들 수 있어 작은 할당이 많을 때 효과가 큼
    https://donsz.nl/blog/arenas/ 에 따르면 이를 지원하는 크레이트는 compact_arena뿐이지만, 요구에 맞지 않으면 직접 구현하기도 어렵지 않음

    • 불투명 핸들을 쓰면 데이터를 더 조밀하게 저장할 수도 있음. 개인 프로젝트인 columnar는 Option<T> 목록을 항목당 1비트 남짓의 존재 여부와 실제로 존재하는 항목의 T로 나눠 저장함
      대신 참조형으로 &Option<T>가 아니라 Option<&T>를 반환하며, 더 일반적으로는 구조적 재귀 안에 참조를 두기보다 참조를 따라 구조적으로 재귀하는 방식임
    • 해당 글은 2년 전 조사를 바탕으로 했고 모든 크레이트를 완벽히 다루지는 못했으니, 오류나 빠진 새 라이브러리를 발견하면 PR을 보내주면 됨
      아레나는 더 널리 쓰일 가치가 있으며, 핸들이나 스마트 포인터 대신 참조를 반환하면 Rust에서 재귀 열거형 패턴 매칭이 매우 편해짐. 보통 if let MyAst::Add(MyAst::Multiply(a, b), c) = expr {}처럼 쓰려 해도 중간의 박스나 포인터 때문에 불가능하지만, 참조는 nightly 기능 없이 투명하게 패턴 매칭할 수 있음. 모든 참조가 한 아레나를 가리키면 트리 전체를 연결하는 수명도 일관되게 유지됨
    • 결과가 좋아서 컴파일러의 다른 부분도 아레나 방식으로 전환하는 방안을 고려 중이며, 이 접근을 계속 살펴볼 예정임

  • 이 방식은 또 다른 Wadler 방식의 예쁜 출력 라이브러리인 pretty가 지원하는 접근과 꽤 비슷함. 다만 여러 메모리 할당 방식을 지원하다 보니 API가 다소 부담스럽게 느껴질 수 있음

  • 글에서 인용한 논문의 저자가 Brunswick의 평범한 IT 회사에서 일한다니 놀라움

    • 이것이 오픈소스의 묘미임. 전문성과 생업은 서로 큰 상관이 없는 경우가 많음
답변달기