Diffing Algorithm

1. Diffing Algorithm의 필요성

• React가 기존 가상 DOM과 변경된 새로운 가상 DOM을 비교 시

• 변경된 새로운 가상 DOM 트리에 부합하도록 기존의 UI를 효율적으로 갱신하는 방법을 알아낼 필요

• 즉 하나의 트리를 다른 트리로 변형을 시키는 가장 작은 조작 방식을 알아내야만 했음

• 기존에 알아낸 조작 방식 알고리즘은 O(n^3)의 복잡도를 가지고 있었음.

• 이는 너무 비싼 연산으로 두 가지 가정으로 새로운 휴리스틱 알고리즘을 구현함.

• 이 두 가정은 거의 모든 실제 사용 사례에 들어맞고, React는 비교 알고리즘(Diffing Algorithm)을 사용

  • 각기 서로 다른 두 요소는 다른 트리를 구축할 것이다.

  • 개발자가 제공하는 key 프로퍼티를 가지고, 여러 번 렌더링을 거쳐도 변경되지 말아야 하는 자식 요소가 무엇인지 알아낼 수 있을 것이다.

2. React가 DOM 트리를 탐색하는 방법

• 트리의 레벨 순서대로 순회하는 방식으로 탐색

• 즉 같은 레벨(위치)끼리 비교

• 이는 너비 우선 탐색(BFS)의 일종

1) 다른 타입의 DOM 엘리먼트인 경우

• DOM 트리는 각 HTML 태그마다 각각의 규칙이 있어 그 아래 들어가는 자식 태그가 한정적이라는 특징이 있음

• 자식 태그의 부모 태그 또한 정해져 있다는 특징이 있기 때문에, 부모 태그가 달라진다면 React는 이전 트리를 버리고 새로운 트리를 구축하고, 이전의 DOM 노드들은 전부 파괴됨

  <div>
  <Counter />
  </div>
  
  // 부모 태그가 div에서 span으로 바뀌면 자식 노드 <Counter/>는 완전히 해제
  <span>
  <Counter />
  </span>

2) 같은 타입의 DOM 엘리먼트인 경우

• 타입이 바뀌지 않는다면 React는 최대한 렌더링을 하지 않는 방향으로 최소한의 변경 사항만 업데이트

• 업데이트할 내용이 생기면 virtual DOM 내부의 프로퍼티만 수정한 뒤, 모든 노드에 걸친 업데이트가 끝나면 그때 단 한번 실제 DOM으로의 렌더링을 시도

  <div className="before" title="stuff" />
  
  // 기존의 엘리먼트가 태그는 바뀌지 않은 채 className만 변경됨
  // React는 두 요소 비교 시 className만 수정되고 있다는 것을 알게 됨
  <div className="after" title="stuff" />

  // className이 before인 컴포넌트
  <div style={{color: 'red', fontWeight: 'bold"}} title="stuff" />
  
  // className이 after인 컴포넌트
  <div style={{color: 'green', fontWeight: 'bold"}} title="stuff" />

• 두 엘리먼트 비교 시, React는 정확히 color 스타일만 바뀌고 있음을 눈치챔

• 따라서 React는 color 스타일만 수정, 다른 요소는 수정하지 않음

• 이렇듯 하나의 DOM 노드를 처리한 뒤 React는 뒤이어 해당 노드들 밑의 자식들을 순차적으로 동시에 순회하면서 차이가 발견될 때마다 변경함

• 이를 재귀적으로 처리한다고 표현

3) 자식 엘리먼트의 재귀적 처리

• 아래와 같이 자식 엘리먼트 변경 시

  <ul>
  <li>first</li>
  <li>second</li>
  </ul>
  
  // 자식 엘리먼트의 끝에 새로운 자식 엘리먼트를 추가
  <ul>
  <li>first</li>
  <li>second</li>
  <li>third</li>
  </ul>

• React는 기존 <ul>과 새로운 <ul>을 비교 시 자식 노드를 순차적으로 위에서부터 아래로 비교하면서 바뀐 점을 찾음

• 때문에 첫 번째 자식 노드들과 두 번째 자식 노드들이 일치하는 점 확인 후 세 번째 자식 노드를 추가

• 이렇듯 React는 위에서 아래로 순차적으로 비교하기에 리스트의 처음에 엘리먼트를 삽입하시 이전 코드에 비해 훨씬 나쁜 성능을 낼 수 있음.

• 따라서 아래와 같이 자식 엘리먼트 변경 시

  <ul>
  <li>Duke</li>
  <li>Villanova</li>
  </ul>
  
  // 자식 엘리먼트를 처음에 추가
  <ul>
  <li>Connecticut</li>
  <li>Duke</li>
  <li>Villanova</li>
  </ul>

• React는 우리의 기대대로 최소한으로 동작하지 못하게 됨. 기존처럼 처음의 노드들을 비교하기 때문

• <li>Duke</li>와 <li>Connecticut</li>으로 자식 노드가 서로 다르다고 인지한 React는 리스트 전체가 바뀌었다고 받아들임

• 즉 그대로인 자식 노드는 유지시켜도 된다는 것을 깨닫지 못하고 전부 버리고 새롭게 렌더링 해버립니다. 이는 굉장히 비효율적인 동작 방식

• 따라서 React는 이 문제를 해결하기 위해 key라는 속성을 지원

4) 키(Key)

• 만약 자식 노드들이 key를 갖고 있다면, React는 key로 기존 트리의 자식과 새로운 트리의 자식의 일치 여부 확인 가능

  <ul>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
  </ul>
  
  // key가 2014인 자식 엘리먼트를 처음에 추가
  <ul>
  <li key="2014">Connecticut</li>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
  </ul>

• React는 key 속성으로 ‘2014’라는 자식 엘리먼트가 새롭게 생겼고, ‘2015’, ‘2016’ 키를 가진 엘리먼트는 그저 위치만 이동했다는 걸 알게 됨.

• 따라서 React는 기존의 동작 방식대로 다른 자식 엘리먼트는 변경하지 않고 추가된 엘리먼트만 변경

• 이 key 속성에는 보통 데이터 베이스 상의 유니크한 값(ex. Id)을 부여해 주면 됨

• 키는 전역적으로 유일할 필요는 없고, 형제 엘리먼트 사이에서만 유일하면 됨

• 만약 유니크한 값이 없다면 배열의 인덱스를 key로도 사용 가능

• 다만 배열이 다르게 정렬될 경우가 생긴다면 배열의 인덱스를 key로 선택했을 경우는 비효율적으로 동작할 수 있다는 점 참고

• 인덱스는 그대로지만 그 요소가 바뀐다면 React는 배열의 전체가 바뀌었다고 받아들일 것이고, 기존의 DOM 트리를 버리고 새로운 DOM 트리를 구축해 버리기 때문에 비효율적으로 동작하게 될 것임.