Virtual DOM diffing complexity

hong·2026년 4월 17일

javascript

목록 보기

11/12

이전 Virtual DOM 트리와 새로운 Virtual DOM 트리를 비교하는 비용이 얼마나 드냐는 얘기이다.

일반적인 트리 diff 문제는 이론적으로 굉장히 비싸고, 단순하게 풀면 O(n³)까지 갈 수 있다.
근데 리액트 같은 라이브러리는 이걸 그대로 하지 않고, 몇 가지 가정을 둔 heuristic(휴리스틱) 으로 줄여서 보통 O(n) 수준에 가깝게 처리한다.

🙋‍♀️휴리스틱의 의미

정답을 완벽하게 찾는 방법은 아니지만, 현실적으로 빠르고 꽤 잘 맞는 경험적 규칙. (보통 이런 경우엔 이렇게 처리하면 대부분 괜찮더라)

예 :
- 스팸 메일 필터가 ‘광고 문구가 너무 많으면 스팸일 가능성이 높다’라고 판단
- 면접 볼 때 ‘프로젝트를 끝까지 운영해본 사람이 협업 경험도 있을 확률이 높다” 라고 판단

🐹 왜 원래는 비쌀까

DOM 트리는 그냥 배열 하나 비교가 아니라 트리 구조 비교다.

예를 들어 아래와 같은 걸 생각해보자. :

어떤 노드가 삭제됐는지
어떤 노드가 다른 위치로 이동했는지
자식 구조가 어떻게 달라졌는지
완전히 같은 서브트리인지

이걸 완벽하게 최소 비용으로 비교하려면, 트리 편집 거리(tree edit distance)같은 문제에 가까워져서 비용이 엄청 커질 수 있다.
그래서 naive하게 최적 diff를 구하면 O(n³)같은 복잡도가 나온다.

노드가 1000개면 이론상 10억 단위 비교까지 불어날 수 있어서, 실전에서는 너무 무겁다.

🙋‍♀️트리 편집 거리란?

Tree Edit Distance. 트리 A를 트리 B로 바꾸려면 최소 몇 번의 편집이 필요한가?를 나타내는 개념.
여기서 ‘편집’이란 노드 추가/노드 삭제/노드 변경(라벨 바꾸기) 같은걸 의미한다.
트리 두 개가 있을 때 가장 적게 수정해서 똑같이 만들려면?을 구하는 문제라서, 두 트리가 얼마나 비슷한지 측정할 수 있다.
주로 XML/HTML 구조 비교, AST(코드 구문 트리) 비교, UI 트리 비교, 변경점 분석, 버전 비교에 쓰인다.

(*AST : Abstract Syntax Tree. 추상 구문 트리. 코드를 문자열로 보는 것이 아닌 문법 구조를 가진 트리로 바꿔놓은 것.)

🙋‍♀️왜 naive하게 최적 diff를 구하면 O(n³)같은 복잡도가 나올까?

트리 편집 거리를 정확하게 구하려면 ‘이 노드를 저 노드와 대응시킬지’, ‘삭제로 볼지 변경으로 볼지’, ‘자식 구조를 어떻게 맞출지’ 같은 경우의 수를 많이 따져야해서 계산량이 커진다. 그래서 일반적인 트리 비교는 O(n³) 수준의 복잡도가 자주 언급된다.

예를 들어

트리 A
A
├─ B
└─ C

트리 B
A
├─ C
└─ B

이걸 보면 B랑 C가 위치만 바뀌었다고 생각되지만 알고리즘 입장에서는 B를 그대로 둔건지? C를 삭제하고 새 C를 만든건지? 둘 다 바뀐건지? 이동이라고 볼 수 있는지? 이런걸 다 따져봐야한다. 즉 최소 편집 비용이 되도록 노드 대응을 찾는 문제가 들어가는데, 이게 경우의 수를 폭증시킨다.

트리의 노드의 수가 n개 일 때 정확한 최소 편집 거리를 구하려면 노드 쌍 비교 / 서브트리 비교 / 부분 문제 조합이 반복된다.

한 노드와 다른 트리의 여러 노드를 대응 후보로 보고, 각 대응마다 자식 서브트리들을 또 비교하고, 그 결과를 DP처럼 누적해서 최소 비용을 구해야한다.

(*DP : Dynamic Programming, 동적 계획법. 큰 문제를 작은 문제들로 쪼개고, 이미 계산한 작은 문제의 답을 저장했다가 다시 써먹는 방식)

🐹 리액트는 왜 괜찮을까

리액트는 ‘완벽한 최소 diff는 포기하고, 대부분의 UI가 보통 이런 식으로 바뀐다고 가정하자’라고 생각한다.

대표 가정

🐻‍❄️ 타입이 다르면 아예 다른 트리다.

예를 들면,

<div />
<span />

이 둘은 구조가 비슷해보여도 리액트는 ‘태그 타입이 다르네, 갈아엎자’ 라고 판단한다. 즉, 세밀하게 내부 비교는 안 하고 그 노드 이하를 통째로 교체한다. 이 덕분에, 복잡한 비교를 안 해도 된다.

🐻‍❄️ 같은 레벨의 자식들은 key로 대응시킨다.

리스트 비교에서 제일 중요하다.

예를 들어,

<li key="a">A</li>
<li key="b">B</li>
<li key="c">C</li>

다음 렌더에서 순서가 바뀌어도 key가 있으면 리액트가 ‘아 이건 삭제 + 생성이 아니라 같은 애가 이동한거구나’라고 추적할 수 있다. 그래서 리스트 diff가 훨씬 효율적이게 된다.

🐹 그래서 실제 복잡도는?

이론적으로 일반 트리 diff: O(n³)
React heuristic diff: 대체로 O(n)

(*여기서 n은 비교해야할 노드 수)

즉 리액트는 각 레벨을 쭉 훑으면서 비교하고, 타입 다르면 버리고, 같은 타입이면 props 비교하고, 자식은 순서대로 보거나 key 기준으로 맞춰보는 식이라서 거의 선형적으로 처리된다.

(*선형적 : 입력 크기가 커질수록 처리량도 거의 비례해서 늘어난다는 뜻.)

🐹 진짜 항상 O(n)?

무조건이라고 말하긴 좀 위험하다.
실제 비용은 아래와 같은 것들에 따라 달라진다.

트리 크기
변경 위치
리스트 재정렬 여부
Key 사용 여부
렌더 자체 비용
Diff 이후 실제 DOM 반영 비용

즉, 보통은 diff 알고리즘 자체를 휴리스틱으로 단순화해서 O(n)에 가깝다고 말하는게 맞다.

🐹 key 없으면 왜 문제지?

예를 들어
이전 : [A, B, C]
다음 : [X, A, B, C]

이런 경우, key가 없으면 리액트는 인덱스 기준으로 보게 돼서

A → X로 바뀌었네
B → A로 바뀌었네
C → B로 바뀌었네
C 하나 새로 생겼네

이런 식으로 뒤쪽이 전부 바뀐 것처럼 볼 수 있다. 그러면 불필요한 업데이트가 많아진다.
반면 key가 있으면, X를 추가하고 A/B/C는 기존 것을 재사용하기 때문에 훨씬 깔끔하게 처리가 가능하다.
그래서 key가 리스트에서 중요한 것!

🐹 diff complexity가 낮으면 무조건 빠른 앱?

그건 아님.
실제 성능에서는 아래와 같은게 다 들어간다.

컴포넌트 함수 다시 실행 비용
객체 생성 비용
Reconciliation 비용
Commit 단계에서 실제 DOM 수정 비용
Layout / paint 비용

즉, virtual DOM diff가 빠르다 -> 전체 렌더링이 무조건 빠르다. 이건 아니고, 정확히는 ‘브라우저 DOM을 직접 마구 건드리는 것보다, 변경점을 계산하는 과정을 예측 가능하고 효율적으로 만들었다’ 정도로 이해하는게 좋다.

🐹 reconciliation과 diffing은 다른걸까

react reconciliation 과정에서 diffing을 수행한다. 즉, reconciliation이 더 큰 개념.

Diffing : reconciliation 안에 들어있는 비교 작업 (뭐가 달라졌는지 찾는 것)
- 타입이 같은 지, props가 바뀌었는지, 자식이 달라졌는지, key가 같은지
Reconciliation : 화면을 어떻게 업데이트할지 전체적으로 결정하는 과정
- 이 컴포넌트는 유지, 이 DOM 노드는 업데이트, 이 subtree는 버리고 새로 mount, 이 child는 이동/추가/삭제 처리