Github의 Atom에디터 '마커'기능 성능 향상 사례

---

원문
Nathan Sobo, https://blog.atom.io/2015/06/16/optimizing-an-important-atom-primitive.html

지난 몇 달 동안 에디터의 성능 최적화 작업을 진행했다. 진행 도중 '마커' 기능 개선하는 약간은 어려운 이슈를 해결하는 작업이 계획되었다. '마커'는 논리적 영역을 지정하여 수정과 상관 없이 계속 추적하는 기능이다. 예를 들어 아래 gif 에서 녹색 영역이 '마커' 인데 텍스트가 변경되어도 계속 녹색으로 지정되어 있다.

'마커'는 에디터에서 가장 많이 쓰는 기본적인 기능이다. 하이라이팅 된 검색 결과를 변경할때에도 쓰고, Snippet기능에선 텍스트가 변경될때마다 tap stop 을 추적하는데 쓰이고, 철자 검사 기능에서 문제가 된 단어를 마킹하고 다시 검사할때도 쓰이고, 에디터 자체에서도 selection과 cursor를 구현하는데 쓴다. '마커'는 지금 나열한 기능들 외에도 상당히 많이 쓰는 기능이다.

하지만 '마커'는 지난 출시 버전들에서 '찾아 바꾸기'와 같은 한번에 많은 '마커'를 만들어내야 하는 기능에 최악의 성능 이슈를 발생시키는 원인이었다. 때문에 지난 몇 달간 개선 작업을 진행했고 진행 내역을 공유하고자 글을 썼다.

'마커'가 느린 이유

'마커'의 성능 최적화 작업을 이해하기 위해 먼저 기존 구현의 문제점을 짚고 넘어가려고 한다. 버퍼가 변경될때마다 단순히 모든 '마커'를 순회하며 위치를 조정했었다. 여기에 설상가상으로 range 쿼리의 데이터 구조 내의 모든 '마커'에 대해 위치를 조정했고 이는 O(n*log(n))의 복잡도가 되었다. (n이 '마커'의 수이다)

'마커'가 그렇게 많지 않을때는 이 방법의 성능은 어느정도 괜찮았다. 하지만 '마커'가 굉장히 많이 나타날 수 있는 특정 상황에서는 심각한 문제가 되었다. 예를 들어 대용량의 문서에서 사용자가 '찾아 바꾸기' 로 'e'를 타이핑했을 때 하이라이팅을 위해 '마커'를 만든다. 매 키스트로크때마다 '마커' 업데이트에 기다리기 어려운 고통스러운 시간이 흘렀다. 다음 스크린샷은 Atom 0.198.0 버전에서 jQuery 소스 파일의 'e'에 개행을 할 때의 CPU 프로파일이다.

성능 개선

성능 문제를 해결하기 위해 '마커'를 조금 더 덜 집중적으로 사용하기로 했다. 예를 들어 검색 결과 '마커'를 실제로 화면에 보이는 영역에 대해서만 만들고 스크롤되었을 때 업데이트 하도록 하는것이다. 하지만 '마커'는 매우 중요한 기능이기 때문에 어떤 악조건에서도 쉽게 사용할 수 있는 추상적 기능을 제공하는 것이 포인트이다.

'마커'의 가장 큰 문제점은 위치를 단순한 절대값으로 만들어 두고 각 '마커'들이 업데이트 될 때 강제적으로 계산한다는 점이었다. 하지만 모든 '마커'의 위치를 매번 전부 계산할 필요는 없다. 대부분의 경우 화면에 실제로 보이는 '마커'의 위치만 알면 되고, 그렇게 되면 화면을 다시 그릴때까지의 시간동안 계산하게 할 수 있게 되었다.

우린 버퍼가 변경될때마다 모든 '마커'를 계산하는 방법보다 이 계산을 선택적으로 할 수 있도록 만들어야 했다. 실제적으로 필요한 계산 외 나머지를 필요해지기 전까지 지연시키는 것이다. 이를 위해 우리는 '마커'의 위치를 다른 방법으로 표현하도록 수정해야 했다.

상대적 위치 표현

문제를 해결하기 위한 키 포인트를 그림으로 나타내 보았다. 문장이 수정되는 초기 시점에 각 '마커'의 절대적인 위치는 변경된다. 하지만 각 '마커'의 간격은 아직 남아있다.

'마커' 사이의 텍스트가 수정되기 전 까지 이 간격은 계속 유지된다. 이 사실을 버퍼가 변경되기 전에 대부분의 계산을 지연하는 데 활용할 수 있다는 사실을 깨달았다.

이전에 언급했던것 처럼 '마커'의 위치는 아래 그림과 같이 절대적으로 표현되고 있었다.

대신 '마커' 서로간의 거리를 나타내는 방식으로 변경했다. 이를 위해서 버퍼를 여러 구역을 분리했다. 분리된 구역들은 몇 개의 문자가 사용되고 있는지에 대한 '넓이'를 저장하고 있다. 그리고 '마커'의 경우 별도로 ID를 지정하도록 했다.

'마커'는 여러 방법으로 겹칠 수 있기 때문에 구역은 하나 이상의 '마커' ID를 가질 수 있게 되었고 같은 '마커' ID가 연속된 여러 구역에 나타날 수 있게 되었다.

쓰기

이 변경으로 인해 텍스트의 변경을 표현하기 위해서 변경이 이뤄진 단일 구역과 그 다음 구역에만 얼만큼 변경되었는지를 적용하면 되었다.

이 구현의 문제점은 '마커'의 범위를 찾기 위해선 시작점부터 구역을 하나하나 찾아야 한다는 점이었다. 또한 버퍼가 변경될 때 어떤 구역의 extent가 변경되어야 하는지 찾는 것도 문제였다. 이 문제를 해결하지 않는 한 '마커'업데이트 동작의 복잡도는 O(n)을 벗어날 수 없기 때문이다.

읽기

이 단계에서 문제가 되었던 선형 검색을 제거하기 위해 '마커'를 저장하는 구조를 단순 리스트에서 B트리 형태로 바꿨다. B트리를 구현하는데는 많은 방법이 있지만, 약간 수정된 버전의 B+트리를 사용했다.

트리 검색의 기본적인 개념은 노드들이 하위 노드들에 대한 필수 정보만 유지하고 있고 검색해 내려가면서 검색 범위를 큰 폭으로 줄일 수 있다는 점이다. 우리가 사용한 트리는 각 노드들의 하위 노드를 포함해 총 몇 글자의 너비를 가지고 있는지와 하위 노드들의 '마커' ID를 중첩한 정보를 가지고 있다. 이 화려한 중복 트리는 아래와 같이 생겼다.

이 구조는 다양한 작업을 좀 더 효율적으로 처리할 수 있도록 해 준다 (O(n)보다 O(log(n))에 가깝다). 텍스트가 삽입될 때 모든 구역을 전부 훑지 않아도 된다. 대신 각 구역의 요약 정보를 토대로 실제 변경이 필요한 구역으로 직접 찾아갈 수 있게 되었다.

예를 들어 글자를 22번 인덱스에 삽입한다고 할 때 아래처럼 extent를 참고하여 원하는 구역으로 바로 갈 수 있는 것이다.

이 정도는 규모가 작은 형태여서 크게 차이가 없는 것처럼 보인다. 하지만 이 트리가 커질수록 이 접근법은 많은 노드를 건너뛸수 있게 해 준다. 아래는 얼마나 많은 노드를 건너뛸 수 있는지 볼 수 있는 예이다.

만약 특정 '마커'의 범위를 찾아야 할 경우 역시 '마커'를 가진 노드를 찾아 내려가면 된다.

이 방법은 range 쿼리에도 적용할 수 있다. 주어진 범위 내의 '마커' 세트를 반환하는 것이다. 결과적으로 그려야 할 '마커'의 수를 큰 수에서 작은 수로 줄여내는 것이다. 편집기가 임의의 마커들을 강제로 그리도록 한 후 실제로 보이는 '마커'에 대해서만 효율적인 계산을 수행하고 나머지는 신경쓰지 않는 것이다.

이 방법은 jQuery의 소스에서 모든 'e'를 개행하는 과정에서 아래의 CPU프로파일 결과를 보여주었다. 전체 수행 시간이 800ms 에서 50ms대로 줄었다.

언급한 내용들은 전체 최적화 과정에서 일부 내용일 뿐이다. 하지만 전체 구현의 기본적인 아이디어라고 볼 수 있다. marker-index Class가 B+Tree를 구현하고 있고, marker-store-wrapper Class에서 상세 구현을 볼 수 있다.

결론

에디터 초기의 최적화는 주로 DOM인터렉션에 관한 내용이 많았다. 이런 렌더링 성능 향상에 대한 내용도 앞으로 많이 올릴 생각이다. 이 글을 통해 조금 더 깊은 시스템에 대한 나용을 다룰 수 있었다. Electron과 Node 의 통합은 Atom에디터의 성능 이슈를 가진 일부 컴포넌트에 대해 C++ 코드를 사용할 수 있는 기능을 제공하긴 하지만 이번 '마커'에 대한 내용은 단순히 알고리즘 개발만으로 가능한 성능 개선의 좋은 예다. Atom 데이터는 몇달 전보다 많이 빨라졌고 본문의 내용과 같은 성능 개선 작업을 계속 진행하고 있다.