Diffing Algorithm에 대해 알아보자!

선언형 프로그래밍 vs 명령형 프로그래밍

명령형 프로그래밍

어떻게(how)를 자세히 기술하는 접근 방식이다.
아래와 같이 DOM를 직접 조작하여 UI를 업데이트할 때, 우리는 각 단계마다 무엇을 해야 하는지를 명시적으로 작성해야 한다.

const button = document.createElement('button');
button.textContent = 'Click me';
document.body.appendChild(button);

button.addEventListener('click', function() {
  const message = document.createElement('p');
  message.textContent = 'Button clicked!';
  document.body.appendChild(message);
});

선언형 프로그래밍

무엇(what)을 하고 싶은지를 기술하는 방식이다.
상태와 그 상태에 따른 UI를 기술하며, 중간 단계나 구현 세부 사항은 신경 쓰지 않는다.
아래 React 예시를 보자

function App() {
  const [clicked, setClicked] = React.useState(false);

  return (
    <div>
      <button onClick={() => setClicked(true)}>Click me</button>
      {clicked && <p>Button clicked!</p>}
    </div>
  );
}

ReactDOM.render(<App />, document.getElementById('root'));

위와 같이 React는 declarative API(선언형 API)이기에 우리가 일일이 신경을 쓸 필요가 없다.
덕분에 우리는 코드를 쉽게 작성하지만, React 내부에서 어떤 일이 일어나는지 알 수 없다.

근데 어떤 일이 일어나는지 궁금하지 않는가????
그래서 찾아보았다!

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

Diffing Algorithm이라 불리는 reconciliation 알고리즘에 대해 알아보자!!

Diffing Algorithm의 등장 배경

render 함수는 React 엘리먼트 트리는 만드는 것이다.
state나 props가 갱신되면 render함수는 새로운 React 엘리먼트 트리를 반환할 것이고 이때 React는 방금 만들어진 트리에 맞게 가장 효과적으로 UI를 갱신하는 방법을 알아낼 필요가 있다.

이를 위해 React에서는 2가지를 가정하고 heuristic algorithm(휴리스틱 알고리즘)을 사용한다.

• 서로 다른 타입의 두 elements는 서로 다른 트리를 만들어낸다.
• 개발자가 key prop을 통해, 어떤 자식 elements가 변경되지 않아야 할지 표시해줄 수 있다.

여기서 잠깐!! heuristic algorithm이란???

문제 해결을 위해 완벽한 해답을 찾는 것보다는 근사치나 만족할 만한 해답을 빠르게 찾아내기 위한 방법론이다.
주로 복잡하고 시간이 많이 소요되는 문제에 대해 현실적인 시간 내에 해결책을 제공한다.

Diffing Algorithm

기본적으로 두 개의 가상 트리를 비교한다.
여기서 말하는 두 개의 가상 트리란 이전 가상 DOM 트리와 새로운 가상 DOM 트리다.

• 이전 가상 DOM 트리

  컴포넌트가 마지막으로 렌더링되었을 때의 상태를 반영한 가상 DOM이다.
  React는 이 트리를 메모리에 저장해 두고, 컴포넌트의 상태나 props가 변경될 때마다 이 트리와 새로운 가상 DOM 트리를 비교한다.
  이 트리는 이전 상태의 UI 구조를 나타낸다.

• 새로운 가상 DOM 트리

  새로운 가상 DOM 트리는 현재 상태나 props에 기반하여 새롭게 생성된 가상 DOM이다.
  컴포넌트가 새로운 데이터를 받아 렌더링될 때, React는 이 새로운 가상 DOM 트리를 생성한다. 이 트리는 현재 상태의 UI 구조를 나타낸다.

element의 타입이 다른 경우

위의 경우는 이전 트리를 버리고 완전히 새로운 트리를 구축한다.
트리를 버릴 때는 이전 DOM 노드들을 모두 파괴된다.
다시 말해 루트 element의 아래의 모든 컴포넌트는 언마운트되고 그 state도 사라진다.
아래와 같은 비교가 일어나면,

<div>
  <Counter />
</div>
  
<span>
  <Counter />
</span>

이전 Counter는 사라지고 새로 다시 마운트가 된다.

DOM element의 타입이 같은 경우

위의 경우는 두 elements의 속성을 확인하여 동일한 내역은 유지하고 변경된 속성만 갱신한다.

<div className="before" title="stuff" />

<div className="after" title="stuff" />

이 두 elements를 비교하면 React는 현대 DOM 노드 상에 className만을 수정한다.

style이 갱신될 때도 마찬가지이다.

<div style={{color: 'red', fontWeight: 'bold'}} />

<div style={{color: 'green', fontWeight: 'bold'}} />

위 두 엘리먼트 사이에서 변경될 때, React는 fontWeight는 수정하지 않고 color 속성만을 수정한다.

DOM 노드의 처리가 끝나면 React는 이어서 해당 노드의 자식들을 재귀적으로 처리한다.

같은 타입의 컴포넌트 엘리먼트

컴포넌트가 갱신되면 인스턴스는 동일하게 유지되어 렌더링 간 state가 유지된다.
컴포넌트의 바뀐 내용을 업데이트하기 위해서는 현재 컴포넌트 인스턴스의 props를 업데이트한다.

자식에 대한 재귀적 처리

DOM 노드의 자식들을 재귀적으로 처리할 때, React는 기본적으로 동시에 두 리스트를 순회하고 차이점이 있으면 변경을 생성한다.

<ul>
  <li>first</li>
  <li>second</li>
</ul>

<ul>
  <li>first</li>
  <li>second</li>
  <li>third</li>
</ul>

위의 예시를 보면 React는 두 트리에서 first, second가 일치하는 것을 확인하고 마지막으로 third를 추가한다.

하지만 위와 같은 단순 구현은 아래의 예시에서는 효율적이지 않다.

<ul>
  <li>Duke</li>
  <li>Villanova</li>
</ul>

<ul>
  <li>Connecticut</li>
  <li>Duke</li>
  <li>Villanova</li>
</ul>

첫번째부터 일치하지 않으니 변경을 한다. 두번째도 일치하지 않고 세번째는 추가를 해야 한다.
같은 내용이 있음에도 불구하고 다시 만들어야 한다는 것이다.

keys

이러한 문제 해결을 위해 React는 key 속성을 지원한다.
자식들이 key를 가지고 있다면, React는 key를 통해 기존 트리와 이후 트리의 자식들이 일치하는지 확인한다.

위의 예시는 아래와 같이 효율적으로 바꿀 수 있다.

<ul>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
</ul>

<ul>
  <li key="2014">Connecticut</li>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
</ul>

React는 2014 key를 가진 element가 추가되었고 나머지 2015와 2016 key를 가진 elements는 이동만 하면 된다는 것을 알 수 있다.

key값은 전역적으로 유일할 필요없이 형제 사이에서만 유일하면 된다.

이렇게 key 값의 의미를 알게 되었는데 그럼 반복문에서 key 값을 이용하는 이유도 알 수 있다.

function ItemList({ items }) {
  return (
    <ul>
      {items.map(item => (
        <li key={item.id}>{item.name}</li>
      ))}
    </ul>
  );
}

위와 같이 반복을 할 때 반복을 통해 많은 양의 자식을 만들다보면 key값이 없을 때는 효율성이 낮아진다. 다만 key값이 있게 된다면 item.id 값의 비교를 통해 이동을 할지 아니면 다른 수행을 할지 효율적으로 정할 수 있다. 이러한 이점을 위해 의무적으로 key를 사용하게 한다.

이상 Diffing Algorithm에 대해 알아 보았다!