코드 에디터는 줄을 왜 연결 리스트가 아니라 배열에 저장하는가

모든 텍스트 에디터는 재미있는 기능을 만들기 전에 먼저 아주 기본적인 질문 하나에 답해야 합니다. 줄을 어디에 둘 것인가? 텍스트 파일을 편집하려면 파일을 줄 단위로 나눠야 하고, 그 이후에는 거의 모든 작업 — 캐럿 이동, 문자 입력, 검색, 화면 다시 그리기 — 이 *“N번째 줄을 찾는 작업”*부터 시작합니다.

Crimson Editor는 1999년에 이 문제를 이중 연결 리스트로 해결했고, 그 방식을 25년 동안 유지했습니다. 올해는 이를 배열 기반으로 바꿨습니다. 이 글은 그 이유를 설명하려고 합니다. 알고 보니 연결 리스트는 자기가 가장 잘한다고 알려진 작업에서도 배열보다 느렸습니다.

처음엔 줄을 연결 리스트에 저장했다

정확히는 두 개의 MFC CList를 사용했습니다. 하나는 각 줄의 텍스트와 구문 토큰을, 다른 하나는 화면 레이아웃을 담았습니다.

텍스트 편집이라면 연결 리스트는 자연스러운 선택처럼 보입니다. 편집은 결국 중간에 삽입하고 삭제하는 작업이고, 연결 리스트의 삽입은 O(1)이니까요. 하지만 N번째 줄을 찾으려면 FindIndex(N)이 O(n)입니다. 학교에서 배우는 전형적인 트레이드오프죠.

하지만 파일이 커지자 문제가 드러났습니다.

N번째 줄을 찾는 게 O(n)보다 더 느렸다

아래는 900,000줄 문서에서의 FindIndex()를 수행한 결과입니다.

줄	FindIndex
1,000	2.4 µs
100,000	367 µs
450,000	3,220 µs
899,999	6,984 µs

줄을 찾는 비용이 선형이 아니었습니다. 9배 더 안쪽에 있는 줄을 찾는 데에 시간은 19배가 더 들었습니다.

이론적으로 줄을 찾는 비용이 O(n)이지만 실제 측정 결과는 기대보다 훨씬 가파르게 증가했습니다. 원인은 캐시 지역성이었습니다.

각 노드는 힙 여기저기에 흩어져 있습니다. 리스트를 따라간다는 건 흩어진 메모리를 하나씩 방문하는 일이고, 그때마다 CPU 캐시를 놓치기 쉽습니다. 결국 next 포인터 하나를 따라갈 때마다 메모리 왕복 비용을 치르게 됩니다.

게다가 에디터에서는 줄을 찾는 작업이 아주 자주 일어납니다. 캐럿 이동, 편집, 검색, 강조, 다시 그리기까지 모두 이 과정을 거칩니다. 큰 파일의 아래쪽에서 키 하나를 누를 때마다 약 7ms가 소비됐습니다.

리스트는 중간 삽입도 배열에 졌다

보통은 조회 성능을 희생하더라도 중간 삽입이 빠르기 때문에 연결 리스트를 선택합니다.

그런데 생각해보면 중간에 줄을 삽입하려면 먼저 삽입할 자리를 찾아야 합니다.

900,000줄에서	연결 리스트	포인터 배열
마지막 줄에 접근하기	6,879 µs	~0 µs
중간에 한 줄 삽입	3,378 µs	187 µs
맨 앞에 한 줄 삽입	0.3 µs	265 µs

InsertBefore() 자체는 O(1)이지만, 그 전에 FindIndex()를 수행해야 합니다. 결국 위치 탐색 비용이 전체를 지배했고, 파일 절반을 memmove() 하는 배열이 오히려 18배 빨랐습니다.

무엇으로 바꿨나, 그리고 새로 생긴 문제

Crimson Editor의 새로운 컨테이너 CLineList는 std::vector<Line*>입니다. 객체가 아니라 포인터를 저장합니다.

포인터를 사용하는 이유는 두 가지입니다.

1. 삽입 시 줄 전체가 아니라 8바이트 포인터만 이동합니다.
2. 줄 객체의 주소가 변하지 않아 기존 참조가 깨지지 않습니다.

조회와 삽입 성능은 모두 개선됐습니다. 하지만 새로운 문제가 생겼습니다.

연결 리스트의 POSITION은 노드를 가리키는 포인터라 안정적입니다. 반면 배열에서는 인덱스입니다. 중간에 줄을 삽입하거나 삭제하면 이후 인덱스가 모두 바뀝니다.

이런 버그는 디버깅하기 가장 어려운 종류입니다. 프로그램은 멀쩡히 동작하지만 엉뚱한 줄을 수정합니다.

그래서 디버그 빌드에서는 POSITION마다 버전 번호를 붙여, 구조가 변경된 뒤 예전 인덱스를 다시 사용하면 즉시 assert가 발생하도록 했습니다.

대량 편집

배열에서는 한 줄씩 반복해서 삭제하면 memmove()를 반복 수행하게 됩니다.

그래서 InsertGap(), RemoveRange(), ReplaceRange() 같은 대량 연산 API를 만들었습니다. 구조 변경은 한 번만 일어나고, 성능도 크게 개선됐습니다.

특히 워드랩처럼 한 줄이 여러 화면 행으로 바뀌는 작업에서 효과가 컸습니다.

• 한 행씩: 90,000개의 줄에 적용 2,779 ms
• ReplaceRange()에 한 번에 넘기면: 168 ms

돌아보며

이번 작업을 하면서 가장 크게 깨달은 건 Big-O만으로는 실제 성능을 설명할 수 없다는 점이었습니다.

텍스트 에디터에서는 위치를 먼저 찾는 비용이 항상 존재합니다. 그래서 O(1) 삽입이라는 장점은 실제로는 거의 빛을 보지 못했습니다. 반면 캐시 지역성은 성능을 결정하는 핵심 요소였습니다.

자료구조를 바꾸는 것보다 더 어려웠던 일은 POSITION이었습니다. 안정적인 노드 포인터를 인덱스로 바꾸는 순간 기존 코드의 전제가 모두 바뀌었고, 컴파일러는 아무런 도움도 주지 않았습니다.

오랫동안 ‘텍스트 에디터에는 연결 리스트’가 정답처럼 여겨졌습니다. 작은 파일에서는 지금도 충분히 좋은 선택입니다. 하지만 큰 파일에서는 오히려 병목이 되었고, 해결책은 생각보다 훨씬 평범한 자료구조인 배열이었습니다.