[React] Reconciliation - (feat, Diffing 알고리즘)

 

Intro.

지난 글에서 Reconcilation에 대해 잠깐 이야기를 했습니다만, 이번 글에서 Reconcilation에 대해 좀더 깊게 다뤄보려합니다.

현재 최신 reconciler는 fiber structure를 기반으로한 reconciler지만, 글에서 중점적으로 다루려고 하는 내용이 diffing algorithm이기에, stack reconciler 피쳐를 사용해 설명하겠습니다.

 

Main.

 

Reconcilation에 대한 지난 글을 정리하자면 다음과 같습니다.

 

• React Element Tree를 생성하는 것. (VDOM)
• React Element란 결국 plain Obejct이기에, tree 생성은 굉장히 빠르다.
• 이 과정은 setState와 render호출 시, 일어난다.
• VDOM 생성 후, 마지막에 변화들을 실제 DOM 트리에 반영한다.

 

 

 

 

첫 렌더링 때는 어쩔 수 없이 VDOM 모두 DOM에 동기화 시키나, 이후에 상태 변화 혹은 element 변화에 의해 reconcilation이 발생할 시, VDOM 전체를 DOM에 동기화 시키는 작업은 비효율적입니다. 이 때 최적의 방법은, 바뀐 부분만 찾아 동기화 시키는 것이지요.

 

먼저 상태 변화, 혹은 element가 변할 때, reconcilation 과정이 일어나면서, 즉시, 새로운 VDOM을 생성합니다.

그리고 이전 VDOM 과 새로 생성된 VDOM을 비교하면서, 최소한의 연산을 통해 이전 VDOM을 최신 VDOM으로 바꿀 수 있는 방법을 찾습니다. diffing algorithm을 통해서 말이죠.

 

하지만 여기서 문제가 생깁니다!

일반적인 트리-매칭 알고리즘의 경우 O(n^3)의 시간 복잡도를 갖기 때문입니다.

즉, element의 개수가 1000개라고 할 때, 10억번의 연산이 필요하단 뜻이고, 당연하지만 이는 바람직하지 않습니다.

 

그렇기에 react는 두가지를 가정하고 휴리스틱 알고리즘을 사용합니다. 이는 다행히 O(n)의 복잡도를 가집니다.

1. 서로 다른 type을 가지는 React Element는, 서로 다른 트리를 생성 할 것이다.
2. 개발자는 'key'프로퍼티를 통해 리액트에게 해당 요소가 바뀌었는지 안바뀌었는지 힌트를 줄 수 있다.

 

먼저 1번, 당연하지만 이전 VDOM과 최신 VDOM을 비교하면서, 동일한 노드에 대해 다음과 같을 때,

 

<div>
	<img/>
</div>


/// to...


<div>
	<a/>
</div>

 

더 볼 것도 없이, 각 컴포넌트 하위 컴포넌트들이 같은지는 확인 할 필요도 없습니다. 그래서, reconcilation시, 해당 노드 기점(img)으로 아랫단은 모두 제거해버리죠. 이를 친숙한 용어로 'unmount'라고 합니다. 예제에선, img가 unmount되겠군요.

 

만약 속성이 바뀌는 경우는 어떨까요?

 

const Component = ({style}) => {
	return <div style={style} />
}



//from

<Component style={{backgroundColor : 'red'}} />


//to

<Component style={{backgroundColor : 'blue'}} />

 

 

이 경우, 동일한 컴포넌트 인스턴스에 대해 속성만 업데이트 시켜줍니다. unmount는 일어나지 않습니다. 상태는 유지됩니다.

 

 

 

자식컴포넌트가 바뀌는 경우는 어떨까요?

 

//from..


<div>
    <span>hello</span>
    <span>bye</span>
</div>


// case 1

<div>
    <span>hello</span>
    <span>bye</span>
    <span>hoho</span>
</div>


// case 2

<div>
    <span>bye</span>
    <span>hello</span>
    <span>hoho</span>
</div>

 

일단 case 1에 대해선, 첫번째, 두번째 span까진 동일함으로 유지시키고 새로 추가된 3번째 span에 대해 업데이트 시켜줍니다.

 

하지만 case 2에 대해선, 첫번째 span, 두번째 span모두 다르므로 둘다 unmount시킵니다.

 

이 부분에 대해 문제가 있어보이죠?

 

만약 span 요소가 5000개일 경우,  [1,2,3,4,5...5000] -> [2,3,4 , ...5000 , 1] 로 변했다고 할 때, 고작 순서 조금 달라졌다고 

4999개의 인스턴스들을 unmount시키는 것은 매우 비효율적입니다. 

 

이 경우를 위해 key프로퍼티가 존재합니다. 동일한 key 프로퍼티에 대해 리액트가 해당 프로퍼티가 이전 VDOM과 동일하다면, unmount 시키지 않습니다.

 

흔히들 배열 요소를 렌더링 하기 위해 다음과 같이들 하곤 합니다만,

const MyList = () => {

	return ['1','2','3'].map((item , idx) => return <span key={idx}>{item}</span)
}

 

굉장히 잘못된 습관이죠? key의 존재 의의를 전혀 살리지 못할겁니다.

 

 

 

 

끝으로 여담이지만, 

reconcilation 과정은, react 보단  React-native 혹은 react-dom과 같은 renderer에 의해 수행됩니다. 실제로, react github 가보면, react 메인 패키지와 react-reconciler가 분리되어 있음을 볼 수 있습니다. react 패키지 그 자체로는 react element , component 정의 기능 밖에 없습니다.

 

react-dom