VS Code가 1GB 파일을 여는 방법: Rope에서 Piece Table까지

VS Code에서 500MB짜리 로그 파일을 열어보면, 생각보다 잘 열린다. 중간에 글자를 삽입해도 버벅임이 없다.

대부분의 프로그래밍 언어에서 문자열은 연속된 메모리 공간에 저장된다. 읽기엔 좋지만, 중간에 삽입하려면 뒷부분을 전부 밀어야 한다. 파일이 100MB면 한 글자 삽입에 100MB 복사가 필요하다. 그런데 왜 VS Code는 괜찮은 걸까?

이 문제를 해결하기 위해 텍스트 에디터들은 저마다 다른 자료구조를 선택해왔다. Emacs는 Gap Buffer를, Xi Editor는 Rope를, VS Code는 Piece Table을 쓴다.

일반 문자열의 한계

문자열 "Hello World"가 메모리에 어떻게 저장되는지 보자.

[ H | e | l | l | o |   | W | o | r | l | d ]
  0   1   2   3   4   5   6   7   8   9   10

연속된 공간에 나란히 들어있다. 5번 위치에 "Beautiful "을 삽입하고 싶다면 어떻게 해야 할까?

const s = "Hello World";
const result = s.slice(0, 5) + " Beautiful" + s.slice(5);

코드는 간단하지만, 내부에서 일어나는 일은 간단하지 않다. 앞부분을 복사하고, 새 문자열을 붙이고, 뒷부분을 다시 복사한 다음, 전체를 새 메모리에 할당한다. 시간복잡도는 $O(n)$이다.

작은 파일에서는 이 비용이 느껴지지 않는다. 하지만 파일이 커지면 문제가 드러난다. VS Code 팀은 2016년경 35MB 파일(1,370만 줄)을 열다가 Out-Of-Memory 크래시를 경험했다. 당시 VS Code는 각 줄을 별도의 객체로 저장하는 방식을 썼는데, 줄마다 40-60바이트의 오버헤드가 붙어서 원본의 거의 20배에 달하는 메모리를 소비했다. 문제는 명확했다. 더 나은 자료구조가 필요했다.

Rope: 문자열을 트리로 표현하기

Rope는 문자열을 작은 조각으로 나누어 이진 트리 형태로 관리하는 자료구조다. 1995년 Boehm, Atkinson, Plass가 발표한 논문에서 처음 소개되었고, 이름 그대로 '밧줄'처럼 여러 가닥을 엮어 하나의 문자열을 표현한다.

"Hello World"를 Rope로 표현하면 이런 모습이 된다.

        [11]
       /    \
   "Hello"  " World"

루트 노드의 숫자 11은 전체 문자열 길이다. 실제 문자열은 리프 노드에만 저장되고, 내부 노드는 서브트리의 길이 정보만 갖고 있다.

이 구조에서 삽입은 어떻게 동작할까? 5번 위치에 " Beautiful"을 넣는다고 해보자.

           [21]
          /    \
       [15]    " World"
      /    \
  "Hello"  " Beautiful"

기존 문자열을 복사하지 않았다. 새 노드를 만들고 트리 구조만 재배치한 것이다. 삽입 연산은 트리 높이에 비례하므로 $O(\log n)$이 된다.

주요 연산을 보자.

연결(Concat): 두 Rope를 합칠 때는 새 부모 노드를 만들어 양쪽을 자식으로 연결한다. 기존 트리를 건드리지 않으므로 $O(1)$이다.

분할(Split): 특정 위치에서 트리를 둘로 나눈다. 루트에서 해당 위치까지 트리를 타고 내려가면서 분리하므로 $O(\log n)$이다.

삽입(Insert): 분할 후 연결의 조합이다. 위치 $k$에서 Split하고, 새 문자열을 중간에 끼워 Concat 두 번. 역시 $O(\log n)$이다.

인덱스 접근: 대신 느려지는 게 있다. $k$번째 문자를 찾으려면 루트부터 시작해서 왼쪽 서브트리 길이와 비교하며 내려가야 한다. 일반 문자열의 $O(1)$이 $O(\log n)$이 된다.

수정이 빈번한 상황에서는 Rope가 유리하고, 읽기가 대부분인 상황에서는 일반 문자열이 유리하다. 텍스트 에디터는 전자에 해당한다. 타이핑, 백스페이스, 복사-붙여넣기 모두 중간 수정이다.

Gap Buffer: 단순함의 미학

Rope보다 훨씬 단순한 해법도 있다. Emacs가 1970년대부터 써온 Gap Buffer다.

아이디어는 직관적이다. 커서 위치에 빈 공간(gap)을 미리 확보해둔다.

"Hello World"를 편집 중이고, 커서가 "Hello" 뒤에 있다면:
 
[ H | e | l | l | o | _ | _ | _ | _ | _ | W | o | r | l | d ]
                     ↑ gap 시작      ↑ gap 끝

여기서 타이핑을 하면? gap을 채우면 된다. $O(1)$이다.

"Beautiful " 입력 후:
 
[ H | e | l | l | o | B | e | a | u | t | i | f | u | l |   | _ | _ | W | o | r | l | d ]
                                                         ↑ gap (줄어듦)

연산별로 뜯어보면:

삽입(Insert): gap의 시작 위치에 문자를 쓰고, gap 시작 포인터를 한 칸 뒤로 옮긴다. gap이 줄어들 뿐 다른 문자를 건드리지 않는다. $O(1)$이다.

삭제(Delete): 커서 앞 문자를 지우려면? gap 시작 포인터를 한 칸 앞으로 옮기면 된다. 그 문자는 이제 gap의 일부가 되어 "논리적으로 삭제"된다. 역시 $O(1)$이다.

커서 이동(Move): 문제는 여기다. 커서를 $k$칸 옮기려면 gap도 $k$칸 이동해야 한다. gap 앞뒤의 문자들을 하나씩 반대편으로 복사해야 하므로 $O(k)$다. 커서를 한 칸씩 움직이면 $O(1)$이지만, 문서 끝에서 처음으로 점프하면 $O(n)$이 된다.

Gap 확장: gap이 꽉 차면 더 큰 버퍼를 할당하고 전체를 복사해야 한다. amortized $O(1)$이지만, 그 순간에는 $O(n)$이 든다.

문제는 커서를 멀리 옮길 때다. 문서 끝으로 점프하면 gap도 따라가야 하고, 그 사이의 모든 문자를 이동시켜야 한다. $O(n)$이다.

Emacs 시대에는 이게 합리적인 선택이었다. 마우스로 여기저기 클릭하는 게 아니라, 순차적으로 타이핑하는 경우가 대부분이었으니까. 하지만 현대 에디터에서는 다중 커서, 마우스 클릭, Find & Replace 같은 기능이 필수가 됐고, Gap Buffer의 한계가 드러났다. 그래도 구현이 간단하고 메모리 오버헤드가 거의 없다는 장점 덕분에, 작은 파일을 다루는 에디터나 단순한 텍스트 입력 위젯에서는 여전히 쓰인다.

Piece Table: 발상의 전환

수정이 빠르면서, 메모리도 효율적이고, Undo 구현도 쉬운 구조가 있을까?

Piece Table은 완전히 다른 관점에서 문제에 접근한다. 원본 파일을 절대 수정하지 않는다.

구조는 세 가지 요소로 이루어진다.

• Original buffer: 원본 파일 내용. 읽기 전용.
• Add buffer: 새로 추가된 텍스트들. append만 가능.
• Piece table: "어느 버퍼의 어디서부터 어디까지"를 기록한 조각 목록.

파일을 처음 열면 이런 상태다.

Original buffer: "Hello World"
Add buffer: (비어있음)
 
Piece table:
  [1] original, 0, 11  → "Hello World"

5번 위치에 " Beautiful"을 삽입하면?

Original buffer: "Hello World"     ← 그대로!
Add buffer: " Beautiful"           ← 새 텍스트 추가
 
Piece table:
  [1] original, 0, 5    → "Hello"
  [2] add, 0, 10        → " Beautiful"
  [3] original, 5, 6    → " World"

Hello World

이 구조의 장점:

Undo가 거의 공짜다. 버퍼 내용은 절대 삭제되지 않는다. 삭제한 텍스트도 original buffer에 그대로 남아있다. piece table의 이전 상태만 기억하면 되돌리기가 그냥 된다. 버퍼를 뒤져서 삭제된 내용을 복구할 필요가 없다.

메모리 효율적이다. 100MB 파일을 열어서 한 글자만 수정해도, 추가로 필요한 메모리는 그 한 글자와 piece table 엔트리뿐이다. 원본을 복사하지 않으니까.

파일 로딩이 빠르다. 파일을 메모리에 올리면 그게 곧 original buffer다. 줄 단위로 쪼개거나 별도의 자료구조를 구축할 필요가 없다.

VS Code의 진화: Piece Table에서 Piece Tree로

VS Code 팀은 2018년에 기존 라인 배열 방식을 버리고 Piece Table을 도입했다. 하지만 교과서적인 Piece Table을 그대로 쓴 게 아니다. 실제 에디터에서 마주치는 문제들을 해결하기 위해 여러 최적화를 거쳤다.

줄바꿈 캐싱

텍스트 에디터는 줄(line) 단위로 동작한다. 뷰 렌더링, 토큰화, 링크 검출 모두 getLineContent를 호출한다. 전통적인 Piece Table은 오프셋만 저장하므로, $n$번째 줄을 찾으려면 처음부터 줄바꿈을 세어가야 한다. 이건 $O(n)$이다.

VS Code는 각 piece에 줄바꿈 위치 정보를 캐싱했다. 이제 특정 줄을 찾을 때 문자 단위가 아니라 piece 단위로 건너뛸 수 있다.

다중 버퍼로 V8 한계 우회

Node.js에서 파일을 읽으면 64KB 청크 단위로 전달된다. 64MB 파일이면 1000개 청크가 온다. 전통적인 구현대로라면 이걸 하나의 문자열로 합쳐서 original buffer에 저장해야 하는데, V8의 문자열 최대 길이 제한 때문에 500MB 파일을 열면 터진다.

VS Code는 original buffer를 단일 문자열이 아닌 버퍼 배열로 바꿨다. 64KB 청크를 받을 때마다 그대로 배열에 push하고, piece가 이 청크들을 참조하게 했다. 문자열 연결 비용도 사라지고, V8 한계도 우회했다.

Red-Black Tree로 탐색 속도 개선

piece가 수천 개로 늘어나면 선형 탐색이 병목이 된다. VS Code는 piece 목록을 Red-Black Tree로 관리하도록 바꿨다. 각 노드에 왼쪽 서브트리의 텍스트 길이와 줄바꿈 개수를 캐싱해서, 오프셋이나 줄 번호로 검색할 때 $O(\log n)$을 보장한다.

VS Code 팀은 이 구조를 Piece Tree라고 부른다.

객체 할당 최소화

piece를 분할할 때마다 줄바꿈 위치 배열을 새로 만들면 성능이 떨어진다. 예를 들어 999개의 줄바꿈을 가진 piece를 반으로 나누면, 500개짜리 배열 두 개를 새로 할당해야 한다.

하지만 버퍼는 불변이다. 줄바꿈 위치도 버퍼 내에서 절대 바뀌지 않는다. VS Code는 piece가 줄바꿈 배열을 직접 갖는 대신, 버퍼의 줄바꿈 배열을 참조만 하도록 바꿨다. 이 변경 하나로 텍스트 버퍼 연산이 3배 빨라졌다.

벤치마크

VS Code 팀이 실제로 측정한 결과를 보자. 테스트에 사용한 파일들은 다음과 같다.

• TypeScript 컴파일러의 checker.ts (1.46MB, 2.6만 줄)
• SQLite 소스코드 sqlite.c (4.31MB, 12.8만 줄)
• 러시아어-영어 사전 파일 (14MB, 55.2만 줄)
• VS Code 힙 스냅샷 (54MB, 300만 줄)
• checker.ts × 128 (184MB, 300만 줄)

메모리 사용량: 기존 라인 배열은 54MB 파일에 약 600MB를 사용했다. Piece Tree는 원본 크기에 가까운 메모리만 사용한다.

파일 열기: 줄바꿈으로 split하는 것보다 청크를 그대로 쌓는 게 훨씬 빠르다.

편집: 작은 파일에서는 라인 배열이 빠르다. 배열 인덱스 접근과 짧은 문자열 조작은 정말 빠르니까. 하지만 10만 줄이 넘어가면 라인 배열이 버벅이기 시작한다. Piece Tree는 파일 크기에 관계없이 안정적인 성능을 보인다.

줄 읽기: 여기가 Piece Tree의 약점이다. 편집을 수천 번 하면 노드가 수만 개로 늘어나고, getLineContent 호출마다 트리 탐색이 필요하다. $O(1)$이던 게 $O(\log n)$이 된다. 다만 VS Code 팀은 이 약점이 실제로는 크게 문제되지 않는다고 판단했다. getLineContent 호출 자체는 마이크로초 단위고, 그 결과를 가지고 하는 DOM 렌더링이나 토큰화가 수십 밀리초가 걸린다. 전체 시간의 1% 미만이라는 것이다.

다른 에디터들은 어떤 선택을 했나

VS Code만 보면 Piece Table이 정답처럼 보인다. 하지만 다른 에디터들을 보면, 각자 다른 선택을 하고 있다는 걸 알 수 있다.

Xi Editor: Rope를 선택한 이유

Xi Editor는 Google의 Raph Levien이 만든 실험적 에디터다. 프로젝트는 2020년에 중단됐지만, 그 과정에서 나온 기술적 결정들은 여전히 참고할 가치가 있다.

Raph Levien은 Rope를 선택한 이유를 이렇게 설명했다.

"Rope는 기본적으로 성능이 나쁜 케이스가 없다. Piece Table은 파일을 처음 열 때는 성능이 아주 좋지만, 편집이 누적될수록 성능이 저하된다."

Piece Table은 piece가 쌓이면 탐색 비용이 증가한다. VS Code는 이를 Red-Black Tree로 해결했지만, Raph Levien은 처음부터 균형 잡힌 트리 구조인 Rope를 선택하는 게 더 자연스럽다고 본 것이다.

또 하나의 이유는 Rust의 불변성 모델과의 궁합이다. Rope는 불변 자료구조로 구현하기 쉽고, Rust의 copy-on-write와 잘 맞는다. 협업 편집(CRDT)을 염두에 두고 있었다면 이 특성이 중요했을 것이다.

Zed: SumTree 위의 Rope

최근 화제가 된 Zed 에디터도 Rope를 쓴다. 하지만 일반적인 Rope가 아니다. Zed는 SumTree라는 B+ 트리 변형 위에 Rope를 구축했다.

SumTree는 B+ 트리 기반으로 thread-safe하고 copy-on-write를 지원한다. 리프 노드에 16~32바이트 텍스트 청크가 들어가고, 내부 노드는 서브트리의 요약 정보를 저장해서 오프셋↔줄/칼럼 변환이 $O(\log n)$에 가능하다.

더 재밌는 건 Zed가 두 개의 Rope를 유지한다는 점이다. 하나는 현재 버퍼 상태, 다른 하나는 삭제된 모든 텍스트. 이 두 Rope를 조합해서 과거 상태를 복원할 수 있다. Piece Table의 "원본 불변" 아이디어와 비슷하지만, 구현 방식이 다르다.

Helix: Ropey 크레이트

Helix는 Rust로 만든 모달 에디터인데, ropey라는 크레이트를 쓴다. 직접 구현하지 않고 라이브러리를 가져다 쓴 케이스다. Helix 24.03에서는 regex-cursor라는 스트리밍 정규식 엔진을 도입해서, Rope 청크 위에서 직접 정규식을 돌린다. 자료구조 선택이 나중에 어떤 최적화가 가능한지를 결정한다는 좋은 예다.

에디터별 자료구조 비교

Rust 진영에서 Rope가 인기 있는 건 우연이 아니다. Rust의 소유권 모델과 불변 자료구조가 잘 맞기 때문이다. 반면 VS Code는 JavaScript/TypeScript 환경에서 GC 부담을 줄이기 위해 Piece Table을 선택했다. 언어와 런타임 특성이 자료구조 선택에 영향을 준다.

2025년 VS Code 코드를 뜯어보니

블로그 글은 2018년에 쓰였다. 7년이 지난 지금, 실제 코드는 어떻게 생겼을까?

VS Code의 Piece Tree 구현은 src/vs/editor/common/model/pieceTreeTextBuffer/ 디렉토리에 있다. 핵심 파일인 pieceTreeBase.ts를 열어보면 약 1,500줄 정도 된다.

몇 가지 눈에 띄는 점이 있다.

1. 노드 색상이 숫자로 정의되어 있다

const enum NodeColor {
  Black = 0,
  Red = 1,
}

Red-Black Tree 구현이 실제로 들어있다. leftRotate, rightRotate 같은 메서드들이 교과서 그대로다.

2. CRLF 처리 코드가 상당히 복잡하다

_normalizeCRLF라는 메서드가 있는데, 블로그에서 "CRLF는 악몽"이라고 한 이유를 알 것 같다. 줄바꿈이 \r\n인 경우를 처리하는 조건문이 여러 곳에 흩어져 있다.

3. 성능 최적화 흔적이 곳곳에

// pieceTreeBase.ts에서 발췌
// We intentionally create objects as late as possible

객체 생성을 최대한 미루는 패턴이 보인다. GC 부담을 줄이기 위한 것으로 보인다. 블로그에서 언급한 "불필요한 문자열 할당 줄이기" 작업의 흔적이다.

4. 테스트 케이스가 방대하다

같은 디렉토리에 pieceTreeTextBuffer.test.ts가 있는데, 엣지 케이스 테스트가 수백 개다. 특히 CRLF, 유니코드, 큰 파일 관련 테스트가 많다. 실제로 버그를 많이 겪었다는 증거다.

코드를 읽으면 알겠지만 역시나 실제 구현은 아이디어를 표현한 코드에 비해 훨씬 지저분하다.

실전에서 배운 것들

VS Code 블로그에서 가장 인상적인 부분은 기술적 설명이 아니라, 팀이 겪은 시행착오다.

최적화할 곳을 잘못 짚었다. Peng Lyu는 처음에 insert, delete, search 세 가지 기본 연산 최적화에 집중했다. 하지만 실제로 VS Code에 통합하고 프로파일링해보니, 핫스팟은 getLineContent였다. 이론적으로 중요한 연산과 실제로 자주 호출되는 연산은 달랐다.

CRLF 처리가 예상보다 어려웠다. Windows의 줄바꿈은 \r\n 두 문자다. piece 경계에서 \r과 \n이 분리되면? 두 piece를 합쳐서 줄바꿈인지 확인해야 한다. 블로그에서 "여러 번의 시도가 필요했다"고 한 부분이 이해가 간다.

GC가 CPU를 잡아먹는다. 기존 코드는 첫 글자의 charCode만 필요해도 getLineContent로 전체 줄을 가져왔다. Piece Tree에서는 이게 매번 서브스트링을 생성하고, 바로 버려지면서 GC 부담이 된다.

C++ 네이티브 모듈 시도는 실패했다. VS Code 팀은 C++로 텍스트 버퍼를 구현하고 네이티브 모듈로 연동하는 방법도 시도했다. 하지만 JS↔C++ 경계 비용이 너무 컸다. getLineContent처럼 자주 호출되는 메서드는 V8이 JS끼리 인라인하는 게 더 빠르다.

언제 무엇을 쓸 것인가

그래서 뭘 써야 할까? 상황에 따라 다르다. (뻔한 답이지만 사실이다.)

Gap Buffer는 구현이 단순하고, 연속 타이핑에 최적화되어 있다. 커서 점프가 드물고 파일이 크지 않다면 충분히 좋은 선택이다. Emacs가 수십 년간 잘 써왔다.

Rope는 수정 연산이 안정적으로 $O(\log n)$이고, 트리 구조 덕분에 불변성을 유지하기 쉽다. CRDT 기반 협업 편집을 구현할 때 유리하다. Xi Editor가 Rope를 선택한 이유도 이것이다.

Piece Table은 원본 불변이라는 특성 덕분에 Undo가 자연스럽고, 대용량 파일을 열 때 메모리 효율이 좋다. 다만 편집이 누적될수록 노드가 많아져서 읽기 성능이 저하될 수 있다. VS Code는 이를 Piece Tree로 발전시켜 $O(\log n)$ 탐색을 보장했다.

마지막으로 네 가지 자료구조의 시간복잡도를 정리하면 다음과 같다.

마치며

같은 문제를 두고 다른 팀들이 다른 답을 내놓았다. VS Code는 Piece Table, Xi Editor는 Rope, Zed는 SumTree 위의 Rope. 언어 특성, 팀의 경험, 우선순위에 따라 다른 길을 걸었다.

VS Code 팀의 블로그에서 인상적인 건 최종 결과물보다 과정이다. C++ 구현을 시도했다가 포기한 것, 최적화 지점을 잘못 짚었던 것, CRLF 처리에 여러 번 실패한 것. 실제 코드를 뜯어보면 블로그에서 느끼지 못한 지저분함이 보인다.

시각화를 직접 만들어보니 자료구조가 생각보다 단순하다는 걸 깨달았다. 글로 읽으면 복잡해 보이는 것들이, 손으로 조작해보면 "아, 이거구나" 싶어진다.

직접 텍스트 에디터를 만들 일은 드물겠지만, "어떤 연산을 빠르게 할 것인가, 무엇을 희생할 것인가"라는 질문은 어디서든 마주치게 된다. 더 파고들고 싶다면 Finseth의 The Craft of Text Editing이나 Crowley의 Data Structures for Text Sequences를 추천한다.

+ 더 파고들 거리

이 주제를 파다 보니 오히려 질문이 늘었다.

VS Code는 왜 Rope가 아니라 Piece Table을 선택했을까? Rope도 $O(\log n)$ 삽입이 가능하고, Xi Editor나 Zed처럼 잘 쓰는 에디터도 있다. 내 추측은 초기 로딩 속도(Piece Table은 파일을 그대로 올리면 됨)와 기존 라인 배열에서의 마이그레이션 용이성인데, 확실하진 않다.

getLineContent가 왜 병목이었을까? 렌더링은 보이는 줄만, 토큰화도 변경된 줄 근처만 하면 되는데, 어떤 기능이 그렇게 많이 호출하는 걸까? Find & Replace, 포맷팅, diff 계산, LSP 통신이 후보다.

편집이 누적되면 Piece Table 성능이 정말 저하될까? piece가 10만 개면 트리 높이가 17 정도. 작아 보이지만 초당 수천 번 호출되면? 직접 벤치마크를 돌려봐야 답이 나올 것 같다. 다음 글에서 해볼 예정이다.