| Diffing 알고리즘이란

Diff는 두 대상 간의 "차이점"을 의미합니다. 말 그대로 이전 트리와의 차이점을 구하는 알고리즘 입니다.

리액트는 우리가 작성한 UI를 브라우저에 효율적으로 그리기 위해 Virtual DOM이라는 중간 단계를 거치면서 Diffing 알고리즘을 활용해 차이를 비교 합니다.

효율적으로 그린다?

리액트는 UI 상태가 바뀔 때마다 새로운 Virtual DOM을 만들고,

이전 Virtual DOM과 비교하여 실제로 바뀐 부분만 실제 DOM에 반영합니다.

이 비교하는 과정을 바로 Diffing 알고리즘이라고 부릅니다.

| Virtual DOM

Virtual DOM은 실제 DOM을 추상화한 자바스크립트 객체입니다.

리액트에서는 Virtual DOM을 활용해 최소한의 변경사항만을 실제 DOM에 한 번에 반영하여 성능을 최적화합니다.

이 때 최소한의 변경 사항을 확인하기 위한 과정이 Diffing입니다.

한번에 반영하는 이유가 있나요?

변경 사항을 개별적으로 DOM에 적용하면, 브라우저가 매번 렌더링 과정을 반복하므로 성능에 큰 비용이 발생합니다.

따라서 한 번에 변경 사항을 반영해 렌더링 비용을 최소화합니다.

자바스크립트의 DocumentFragment가 이와 유사한 개념입니다.

잘못된 예:

const list = document.querySelector("#list");

const fruits = ["Apple", "Orange", "Banana", "Melon"];

fruits.forEach((fruit) => {

const li = document.createElement("li");

li.textContent = fruit;

list.appendChild(li); // 개별적으로 DOM에 추가

});

좋은 예:

const list = document.querySelector("#list");

const fruits = ["Apple", "Orange", "Banana", "Melon"];

const fragment = new DocumentFragment();

fruits.forEach((fruit) => {

const li = document.createElement("li");

li.textContent = fruit;

fragment.appendChild(li); // 한 번에 추가할 fragment에 모음

});

list.appendChild(fragment); // DOM에 한 번만 적용

그럼 Virtual DOM을 사용하면 빠른 건가요?

빠를수도 있지만 아닐수도 있습니다.

리액트 개발 팀원이자, Redux의 개발자인 Dan Abramov의 트윗을 보면 다음과 같이 말합니다.

Myth: React is “faster than DOM”. Reality: it helps create maintainable applications, and is “fast enough” for most use cases.

결국 Virtual DOM을 생성하고, 비교(Diffing)한 뒤,

이를 실제 DOM에 반영하는 과정이 있기 때문에 때에 따라서는 더 느릴 수도 있습니다.

다만 대부분은 충분히 빠르면서 유지 보수하기 좋은 코드를 작성할 수 있게 도와줍니다.

Reconciliation(재조정) 과 Diffing 알고리즘

리액트에서 DOM이 업데이트되는 과정을 보면 다음과 같습니다.

상태 변경 → 새로운 Virtual DOM 생성 → Reconciliation(Diffing) → 업데이트 예약 → 실제 DOM 적용

이 과정에서 Reconciliation은 이전 Virtual DOM 트리와 새로운 Virtual DOM 트리를 비교하여 변경된 부분을 찾는 과정입니다.

이 비교하는 과정에 사용하는 알고리즘이 Diffing 알고리즘 입니다.

Diffing 알고리즘이 중요한가요?

Reconciliation 과정에서 변경된 부분을 빠르게 찾을수록 성능이 향상됩니다.

기본적으로 하나의 트리를 다른 트리로 변환하기 위해서는 O(n³)의 시간 복잡도를 갖고 있습니다.

만약 리액트에서 해당 시간 복잡도의 알고리즘을 그대로 사용하게 되면 1000개의 엘리먼트를 그리기 위해 10억 번의 비교 연산을 수행해야 합니다.

그래서 리액트는 어떻게 하는데요?

리액트는 이를 효율적으로 수행하기 위해 두 가지 휴리스틱을 적용한 O(n) 복잡도의 알고리즘을 사용합니다.

서로 다른 타입의 두 엘리먼트는 서로 다른 트리를 만들어낸다.
개발자가 key prop을 통해, 여러 렌더링 사이에서 어떤 자식 엘리먼트가 변경되지 않아야 할지 표시해 줄 수 있다.

리액트에서 비교가 어떤식으로 일어나나요?

리액트는 두 개의 트리를 비교할 때 두 엘리먼트의 루트 엘리먼트부터 비교하게 되고,

이후의 동작은 루트 엘리먼트의 타입에 따라 아래와 같이 동작합니다.

다른 타입의 요소는 삭제 후 재생성합니다.

// 이전

<div>

</div>

// 이후

<span>

</span>

위 예시에서 div가 span으로 변경되었기 때문에 리액트는 하위 컴포넌트(Counter)를 포함해 전체를 삭제하고 새로 생성합니다.

같은 타입의 요소는 속성만 갱신합니다.

// 이전

<div className="old" title="hello">Hello</div>

// 이후

<div className="new" title="hello">Hello</div>

이 경우 리액트는 변경된 className 속성만 업데이트하고, 다른 속성(title 등)은 변경하지 않습니다.

리스트에서는 key로 요소의 변화를 확인합니다.

// 이전

<ul>

<li key="2016">Villanova</li>

</ul>

// 이후

<ul>

<li key="2014">UConn</li>

<li key="2016">Villanova</li>

</ul>

리액트는 자식들이 key 속성을 가지고 있으면, 이를 통해 기존 트리와 이후 트리의 자식들이 일치하는지 확인하고, 트리 변환 작업이 효율적으로 수행되도록 돕습니다.

만약 휴리스틱이 기반하고 있는 가정에 부합하지 않으면?

그런 경우 성능이 나빠질 수 있습니다.

따라서 리스트의 key 값을 설정할 때 반드시 변하지 않고, 유일한 값을 설정해야 합니다.

만약 변하는 값(리스트의 index, Math.random() 등)을 key로 사용하면 불필요한 DOM 노드를 재생성할 수 있습니다.

| 끝

만약 나중에 UI 라이브러리나 프레임워크를 만들게 된다면,

우리가 가장 많이 사용하는 React의 기본 동작 방식을 이해하는 것이 큰 도움이 될 겁니다.

실제 코드는 훨씬 복잡하고 어렵지만, 전체적인 흐름만 파악해도 충분히 유익하다고 생각합니다.

특히, React의 Reconciliation 과정이 코드로 어떻게 구현되어 있는지 궁금하다면 아래 링크에서 직접 확인해볼 수 있습니다.

https://github.com/facebook/react/tree/v19.0.0/packages/react-reconciler/src

[React] 리액트에서 Virtual DOM과 diffing 알고리즘