# ASTs 및 다른 컴파일러 데이터 구조의 평탄화

> Clean Markdown view of GeekNews topic #9609. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=9609](https://news.hada.io/topic?id=9609)
- GeekNews Markdown: [https://news.hada.io/topic/9609.md](https://news.hada.io/topic/9609.md)
- Type: GN+
- Author: [neo](https://news.hada.io/@neo)
- Published: 2023-07-04T09:56:11+09:00
- Updated: 2023-07-04T09:56:11+09:00
- Original source: [cs.cornell.edu](https://www.cs.cornell.edu/~asampson/blog/flattening.html)
- Points: 3
- Comments: 1

## Topic Body

- 아레나 또는 지역은 컴파일러와 컴파일러와 유사한 것들에 대한 간단하고 효과적인 기술입니다.
- 아레나를 사용하여 추상 구문 트리(AST)를 평면화하면 성능을 향상시키고 편의성을 제공할 수 있습니다.
- 평면화는 AST 노드를 단일 배열에 패킹하고 포인터 대신 배열 인덱스를 사용하는 것을 의미합니다.
- 평면화된 AST는 개선된 지역성, 더 작은 참조, 저렴한 할당 및 해제 등의 이점을 제공합니다.
- 평면화된 AST는 메모리 관리를 간소화하고 편리한 중복 제거를 가능하게 할 수 있습니다.
- 성능 결과는 평면화된 인터프리터 버전이 일반 버전보다 2.4배 빠를 수 있다는 것을 보여줍니다.
- AST의 평면 표현을 활용하여 재귀를 제거하고 선형 탐색을 활용하여 성능을 더욱 향상시킬 수 있습니다.
- 이 기사에서는 프로그래밍 언어 인터프리터에서 데이터 구조 평면화를 통해 달성한 성능 향상에 대해 논의합니다.
- 추가로 평면화된 인터프리터는 재귀 인터프리터에 비해 1.2초 대 1.3초로 8.2%의 성능 향상을 보입니다.
- 이 기술은 사실상 바이트코드 인터프리터의 아이디어를 재창조하며, Expr 구조체는 바이트코드 명령으로 사용됩니다.
- LuaJIT, Sorbet 타입 체커, Oil 셸 등과 관련된 데이터 구조 평면화에 대한 다른 글과 프로젝트가 언급됩니다.
- 비디오 게임, 직렬화된 데이터 처리, 데이터 지향 설계, 엔티티-컴포넌트 시스템과 같은 도메인에서도 평면화와 지역성 최적화와 관련된 유사한 개념이 등장합니다.
- 이 기사는 Rust로 구현된 장난감 "계산기" 언어에 동일한 기술을 적용한 Inanna Malick의 게시물을 확인하는 것을 추천합니다.
- Rust에서 이 기술을 사용하는 데 제한 사항이 논의되며, Expr 구조체 내부에 다른 Expr을 인라인으로 포함할 수 없다는 한계가 있습니다.
- 성능 비교는 M1 Max 프로세서와 32GB 메모리가 장착된 MacBook Pro에서 macOS 13.3.1과 Rust 1.69.0을 실행한 환경에서 수행되었습니다.

## Comments



### Comment 16957

- Author: neo
- Created: 2023-07-04T09:56:12+09:00
- Points: 1

###### [Hacker News 의견](http://news.ycombinator.com/item?id=36559346) 
- Blender는 빠르고 손실 없는 파일 로딩 및 저장을 위해 디스크와 메모리에서 동일한 표현을 사용합니다.
- 효율적인 인라인 마크업 파싱을 위해 pulldown-cmark에서 평탄화된 AST가 사용됩니다.
- 평탄화된 AST 표현은 노드 수나 스택 깊이에 관계없이 O(1) 트리 변환을 가능하게 합니다.
- pulldown-cmark의 성능은 다른 CommonMark 파서와 비교하여 탁월합니다.
- Warren Abstract Machine (WAM)은 Prolog 용 평탄화된 표현을 힙에 사용합니다.
- AST 평탄화는 Lisp와 같은 언어에서 이미 사용되고 있던 개념입니다.
- 크기 조정 가능한 배열에 노드를 저장하는 것은 메모리 할당 문제를 야기할 수 있지만, 페이지 크기 블록에서 풀링함으로써 완화할 수 있습니다.
- AST 노드가 코드에서 어떻게 표현되는지에 대해 주의가 필요하며, 불필요한 패딩을 피해야 합니다.
- 포인터 대신 인덱스를 사용하면 더 작고 빠른 코드를 얻을 수 있습니다.
- 특정 시나리오에서 유용한 사용자 정의 메모리 할당기를 사용하여 평탄화된 메모리를 구현할 수 있습니다.
- 메모리 제약이 있는 환경에서 JavaScript 파서와 인터프리터를 구현하기 위해 간결한 AST 구조가 사용되었습니다.