React Diffing algorithm1 - Heuristics algorithm

Smart diffing algorithm 

 랜더링 되어 사용되고 있는 Real DOM Tree와 React에서 쓰는 in-memory에 있는 Virtual DOM Tree를 비교하는 알고리즘이다. 최소한의 연산으로 수정작업이 요구되는 실제 DOM object를 찾아서 수정 및 변경작업을 한다.

이 알고리즘의 Time Complexity는 O(n)으로써 상당히 빠른편이다.

옛날에 포스팅한 virtual dom에 대한 내용

https://kmj24.tistory.com/124

브라우저, DOM과 Virtual DOM

 

 

rendering되는 순간 재연산의 영향을 최소화하여 성능향상을 할 수 있도록 한다.

최소한의 연산으로 변경된 DOM객체를 찾아서 reflow, layout / repaint를 하도록 한다.

 

Batching

 

React App에서 예를 들어 위와 같은 형태의 컴포넌트트리가 있다고 하자.

여기서 몇개의 컴포넌트에서 변경이 일어난다고 했을때(상태 변경 등), React는 변경된 컴포넌트에 Dirty표시를 해두고, batch에 추가한다.

(redux와 같은 전역상태관리 라이브러리를 사용할 경우에는 root에 dirty를 표시.

그리고 Virtual DOM Element와 Real DOM Element를 비교하고 순회하며 dirty체크된 Element를 처리한다. 여기서 속성값만 변한 경우 속성값만 업데이트, Element Tag또는 Component가 변경된 경우 해당 Node 및 하위 Node제거(unmount) 후 새로운 Virtual DOM으로 대체 하여 batch에 쌓인 모든 변화를 처리한 후 Real DOM에 결과를 업데이트 한다.

 

하위트리 렌더링

이를 O(n)의 시간복잡도를 만들수 있었던 알고리즘은 Heuristics algorithm이다.

Heuristics 알고리즘은 문제를 빠르고 효율적으로 해결하기 위해 디자인된 방법이다. 중요하지 않은 정보는 고려하지 않는 형태의 알고리즘으로, 정확한 연산이 필요할 경우 사용을 지양한다.

2개의 임의의 트리 사이에서 변경내용을 비교하는것은 O(n³)쯤 된다고 한다. 이는 매우 복잡한 시간복잡도이고, React는 heristics algorithm을 사용하여 O(n)으로 시간복잡도를 줄였다고 자랑한다.

React는 같은 레벨의 트리만 비교하도록 한다. Web Application에서 구성요소가 트리의 다른 수준으로 이동되는 경우가 매우 드물기 때문에 복잡성을 크게 줄일 수 있으며, 보통 큰 손실이 나지 않는다고 한다.

 

 Real DOM과 Virtual DOM을 level by level로 비교하며 바뀐부분을 찾아나간다.

위의 사진과 같이 같은 level의 노드를 비교하며 노드들의 수 일치 또는 불일치에 따라 다른 비교를 한다.

 1. 수가 일치하다는 것은 추가되거나 삭제된 노드가 없다는 것을 의미한다. 

 - 해당 노드의 상태가 변경되어 내부의 값이 변경된 노드라면 dirty가 체크되어 있을것이고, 하위 컴포넌트의 속성값을 업데이트하는것으로 처리할 수 있다.

 - 이럴 경우 Real DOM을 Virtual DOM으로 대체하여 자식 노드들을 탐색하는 비용을 걷어낸다.

<span>{...contents}</span>

<label>{...contents}</label>

위의 코드에서 element span이 label로 변경되었다고 생각해보자.

위의 경우 <span>에서 마운트해제(componentWillUnmount)한 뒤, <label>로 마운트한다.(componentWillMount)

또한 element가 제거될 경우 해당 element와 하위 element 및 state가 모두 사라진다.

style의 갱신또한 변경된 내용만 갱신한다.

 

2. 수가 불일치할 경우 어떤 노드 또는 어느 위치의 노드가 추가되거나 삭제되었는지, 확인하는데 cost가 발생할것이다.

 - list나 queue와 같은 선형 구조를 생각하면 쉬울것이다. 어떤 노드가 추가/삭제되었는지 확인하기 위해서는 cost가 많이 생길 수 있다.

<ul>
  <li>a</li>
  <li>b</li>
</ul>


<ul>
  <li>d</li>
  <li>a</li>
  <li>c</li>
  <li>f</li>
  <li>e</li>
  <li>b</li>
</ul>

- 위와 같이 a와 b만 있을 경우에서 d a c f e b가 되는 경우로 바뀌는데 기존 a와 변경된 d를 비교하여 하위 트리를 유지할 수 없다고 판단, 모든 자식노드들을 변경해버리게 된다. 이럴 경우 성능상 문제가 발생할 수 있다.

- React는 이러한 경우에 대하여 list 형태의 컴포넌트를 rendering할 때 key 값 입력을 강제한다.

<ul>
  <li key='1'>a</li>
  <li key='2'>b</li>
</ul>


<ul>
  <li key='4'>d</li>
  <li key='1'>a</li>
  <li key='3'>c</li>
  <li key='6'>f</li>
  <li key='5'>e</li>
  <li key='2'>b</li>
</ul>

- 배열과 같이 index 등의 key값으로 어떤 노드가 추가/삭제되었는지 쉽게 확인하여 그저 새로운 노드에 대하여 각 노드들의 rendering할 위치만 바꿔주면 된다. (물론 배열은 요소의 추가 삭제 시 비용이 많이 발생하지만 여기서는 예를 들어보았다.) 

 

이러한 Heuristics algorithm을 기반으로 Diffing알고리즘은 DOM tree를 빠르게 변화를 확인하고 브라우저에 렌더링 시켜준다.

 

 

 

참고

http://blog.drakejin.me/React-VirtualDOM-And-Repaint-Reflow/

ReactJS의 Virtual DOM과 Repaint, Reflow | DrakeJin

https://ko.reactjs.org/docs/reconciliation.html

재조정 (Reconciliation) – React

 

https://medium.com/@gethylgeorge/how-virtual-dom-and-diffing-works-in-react-6fc805f9f84e

How Virtual-DOM and diffing works in React