React) Diffing 알고리즘 (비교 알고리즘)

Diffing 알고리즘을 알려면 먼저 이 글을 읽고 VDOM에 대해 알고 와보자

React) Virtual DOM 가상 돔

 

1. Diffing 알고리즘이란?

리액트 공식문서(레거시)의 한 부분을 가져와 봤다.

하나의 트리를 가지고 다른 트리로 변환하기 위한 최소한의 연산 수를 구하는 알고리즘 문제를 풀기 위한 일반적인 해결책들이 있습니다.
하지만 이러한 최첨단의 알고리즘도 n개의 엘리먼트가 있는 트리에 대해 O(n^3)의 복잡도를 가집니다.

React에 이 알고리즘을 적용한다면, 1000개의 엘리먼트를 그리기 위해 10억 번의 비교 연산을 수행해야 합니다.
너무나도 비싼 연산이죠.
React는 대신, 두 가지 가정을 기반하여 O(n) 복잡도의 휴리스틱 알고리즘을 구현했습니다.

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

 

트리의 비교 연산의 비용이 너무 비싸진다....

그래서 리액트에서는 두개의 VDOM을 Diffing 알고리즘을 휴리스틱 알고리즘을 구현해 비교하는 것과 개발자가 key props를 통해 바뀐것을 명시하는 것 이 2가지 방법으로 문제를 해결하려 한다.

 

 

 

2. Diffing의 동작

휴리스틱 알고리즘을 이용해 O(n^3)이 걸리는 트리 구조 비교를 O(n)의 시간으로 해결했다.

이 방식의 핵심은 "전부 비교하지 않고 상식적으로 바뀔만한 곳만 비교하자" 라는 것이며, 이는 트리 구조에서 다음과 같이 적용된다.

 

2.1 State가 제거되는 경우

2.1.1 루트 엘리먼트의 타입이 변하는 경우

 

같은 계층(부모 노드)이 변하는 경우는 완전히 다르기 때문에 아예 새로운 트리를 구축하게 된다.
div에 감싸진 <Counter />가 있었는데, span으로 <Counter /> 를 감싸게 된다면 루트 엘리먼트의 모든 자식 컴포넌트가 언마운트되며 자식 컴포넌트들의 state도 없어진다.

 

 

2.1.2 렌더링된 컴포넌트가 렌더링 중지됬을 때

 

 

위의 사진처럼 state를 갖던 컴포넌트가 렌더링이 중단되면 해당 컴포넌트가 갖고있던 state 또한 사라진다.

 

2.1.3 key props를 이용해 state 재설정

 

key는 단지 목록을 구분하기 위해 존재하는 것은 아니다.

key를 이용해 React가 모든 구성요소를 구별하도록 한다.

 

key를 사용하게 된다면 같은 부모 내에 렌더링 한다 하더라도 다른 컴포넌트로 간주하기 때문에 상태를 공유하지 않는다.따라서 서로 다른 컴포넌트가 생성, 제거될 때마다 해당 컴포넌트의 상태는 파괴된다.

 

주의해야 할 점은 key는 전역적으로 고유하지 않고 부모 내의 위치만 지정한다.

 

 

2.2 State가 유지되는 경우

2.2.1 엘리먼트 타입은 같으나 속성이 변하는 경우

import { useState } from 'react';

export default function App() {
  const [isFancy, setIsFancy] = useState(false);
  return (
    <div>
      {isFancy ? (
        <Counter isFancy={true} /> 
      ) : (
        <Counter isFancy={false} /> 
      )}
      <label>
        <input
          type="checkbox"
          checked={isFancy}
          onChange={e => {
            setIsFancy(e.target.checked)
          }}
        />
        Use fancy styling
      </label>
    </div>
  );
}

function Counter({ isFancy }) {
  const [score, setScore] = useState(0);
  const [hover, setHover] = useState(false);

  let className = 'counter';
  if (hover) {
    className += ' hover';
  }
  if (isFancy) {
    className += ' fancy';
  }

  return (
    <div
      className={className}
      onPointerEnter={() => setHover(true)}
      onPointerLeave={() => setHover(false)}
    >
      <h1>{score}</h1>
      <button onClick={() => setScore(score + 1)}>
        Add one
      </button>
    </div>
  );
}

 

위의 코드의 상황을 사진으로 표현하자면 아래와 같다.

<Counter /> 컴포넌트는 isFansy 상태에 상관없이 같은 위치에 유지되기 때문에 재설정은 일어나지 않는다.그로인해 State도 없어지지 않는다.

 

 

2.3 Diffing 동작을 정리하자면....

Diffing 동작은 트리 구조에서 변화된 엘리먼트를 찾아 비교한다.하지만 여기서 State가 제거되는지, 같은 위치에 렌더링되는지, 엘리먼트의 유일값인 key props를 보면 Diffing이 동작하는 모습을 알 수 있다.

 

 

 

 

3. 정리

Diffing 알고리즘은 이전 VDOM과 바뀐 VDOM을 비교해 변한 엘리먼트를 찾아내는 역활을한다.

 

Diffing 동작은 State의 제거 여부, 같은 위치에 렌더링되는지, 엘리먼트의 유일값인 key props에 영향을 받는다.

 

추가적으로 React는 JSX 마크업이 아닌 UI 트리의 위치에 따라 어떤 상태가 어떤 구성요소에 속하는지 추적한다.

 

 

 

4. 참고 링크

• https://ko.legacy.reactjs.org/docs/reconciliation.html#gatsby-focus-wrapper
• https://react.dev/learn/preserving-and-resetting-state#same-component-at-the-same-position-preserves-state
• https://yeoulcoding.me/147
• https://velog.io/@joy37/React-diffing-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
• https://velog.io/@naamoonoo/%EB%A6%AC%EC%95%A1%ED%8A%B8%EB%8A%94-%EC%96%B4%EB%96%BB%EA%B2%8C-%EC%9E%91%EB%8F%99%ED%95%A0%EA%B9%8C-Diffing-3%EC%A3%BC%EC%B0%A8-%ED%9A%8C%EA%B3%A0
• https://velog.io/@youa7878/React-Diffing-Algorithm
• https://joong-sunny.github.io/react/react2/#%EF%B8%8F%EC%A7%88%EB%AC%B81-%EB%A6%AC%EC%95%A1%ED%8A%B8-%EA%B0%80%EC%83%81%EB%8F%94-%EC%99%9C%EC%8D%A8%EC%9A%94