[Web] React, Virtual DOM, Diffing algorithm, react fiber, 반복 element에 key가 필요한 이유

지난번에 React는 Virtual DOM을 이용해서 실제 DOM을 사용하는것보다 좀 효율적으로 렌더링 할 수 있다고 했습니다.

​

Browser DOM은 browser의 object 입니다.

​

Virtual DOM은 뭘까요?

 

Virtual DOM

특징 :

​

1. RVM은 Real DOM의 가벼운 표현이라고 보시면 됩니다(lightweight)

​

2. js object로 메모리 내에 트리구조의 자료구조로 저장되어 있습니다.

react app 메모리 내에서 계속 유지되고 있으므로, 필요할 때 언제든 쉽게 수정이 가능합니다.

Browser DOM은 새로고침을 해야해서 속도 차이가 굉장히 심하게 납니다.

​

모~든 React의 수정사항은 가상 DOM에 먼저 반영 됩니다.

그 이후에 Virtual DOM은 Real DOM과 차이점을 비교해서, 차이가 나는 부분만 re-render을 합니다.

​

트리구조를 가지고 있기때문에, 트리 내의 자식노드들도 다같이 re-render 하게 됩니다.

​

그러면 이 트리구조는 언제 만들어지나요?

-> setState가 불릴때 트리구조가 완성이 됩니다. 노드들이 각자 만들어 져서 트리가 됩니다.

​

re-render을 하면 계속 트리를 만드는 과정이 발생합니다. 좀 비효율적이긴 하죠? (heap에다가 memory alloc, free과정이 계속 필요하잖아요?)

​

그래서 구글은 re-render하더라도 트리를 다시 만들지 않는 알고리즘을 채택했답니다. (in-place)

​

무조건 구글이 좋냐고요? 그건 아니라고 하더라구요.^^

구글의 incremental dom에 대한 설명입니다.

https://github.com/google/incremental-dom

google/incremental-dom

음 .. 근데

Virtual DOM과 Real DOM의 차이를 비교하는것도 다 시간 낭비 아닌가요?

그 시간에 직접 고치면 될 것 같은데... 어떻게 비교하는지 알아봅시다.

​

Diffing algorithm (reconciliation)
어디 부분만 바꿀지 결정하는 알고리즘

RealDOM과 VIrtualDOM의 차이를 빠르게 비교해주는 알고리즘 입니다.

​

React DOCS를 보시면, 원래 두개의 차이를 발견해서 새 트리를 구성하는것은 O(N^3)이라는 엄청난 시간복잡도를 가진다고 합니다.

그리고 그에 대한 논문도 참고로 나와있구요.

​

근데 페이스북팀은 휴리스틱하게 해서(몇가지 가정과 함께) O(N)수준으로 줄였다고 합니다.

저는 이걸 보면서 굉장히 감명받았습니다. 왜 사람이 알고리즘을 공부해야 하는지.. O(N^3) -> O(N) .. 아주 명장면입니다

​

그리고 이걸 읽으면서 왜 반복문이나 map함수에서 <div key={id}>를 하라고 하는지 이해가 됐습니다..

​

어떻게 할까요?

​

1. root element를 비교합니다.

root가 다르면 그냥 before은 버리고, 새로운 tree를 만듭니다.

​

2. 만약 같다면 자식 노드들의 component를 비교합니다.

두개의 Component or element명이 다르다면, 이전의 DOM은 unmount 시켜서 버립니다.

이때 componentWillUnmount()가 실행된다고 합니다.

​

3. 두개의 이름도 같다면, 내부의 속성을 또 비교합니다. 여기서 다른 부분이 발견되면 그 부분만 re-render하면 되는것이죠.

https://reactjs.org/docs/reconciliation.html#the-diffing-algorithm

Reconciliation – React

왜 반복 element에는 key가 필요할까?

react의 diffing알고리즘 때문에 그렇답니다.

react는 자식노드들을 재귀적으로 탐색합니다.

 

----before
<ul>
  <li>first</li>
  <li>second</li>
</ul>
---after
<ul>
  <li>first</li>
  <li>second</li>
  <li>third</li>
</ul>

react는 ul을 서로 비교합니다.

음.. 같구만 하면서 li element로 넘어갑니다.

1번. li first 똑같군.. 합격!

2번. li second 똑같군... 합격!

3번. li third? 새로 생겼잖아? 불합격!! 이녀석만 추가로 등록합니다

​

음.. 좋습니다 한방에 찾아냈습니다 !!

​

그러면..

----before
<ul>
  <li>first</li>
  <li>second</li>
</ul>
---after
<ul>
  <li>third</li>
  <li>first</li>
  <li>second</li>
</ul>

이건 어떨까요?

음.. 비교 시작하겠습니다

1번. first와 third? 불합격!! -> 바꿉니다

2번. second와 first? 불합격!! -> 바꿉니다

3번. second가 추가되었네? 불합격!! -> 바꿉니다

​

3번의 불필요한 수정이 일어났습니다.​

즉, 맨 앞의 원소를 넣을때 굉장히 퍼포먼스 저하가 있습니다.

이건 어쩔수 없겠죠? 바로 이런것을 해결하기 위해서 key를 사용한답니다.

 

----before (original)
<ul>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
</ul>
----after
<ul>
  <li key="2014">Connecticut</li>
  <li key="2015">Duke</li>
  <li key="2016">Villanova</li>
</ul>

react의 예시입니다.

이 경우에는 after(modified)에서 key를 가지고 original에서 번호를 찾는다고 합니다.

ul의 child에 대해서 탐색을 합니다.

​

무슨 말이냐 ?

li after의 key 2014가 있습니다. original에 2014가 없습니다. --> 얘 추가

li key가 2015입니다. original에 있습니다. 그대로 놔둡니다

li after의 key가 2014입니다. original에 있습니다. 그대로 놔둡니다.

즉 한번의 변경만 일어납니다.

-> 여기까지는 official입니다.

​

지금부터는 제 생각입니다.

​

만약 자식 노드의 숫자가 많아지면, li가 2만개 이렇게 된다면, 오히려 검색하는데 걸리는 시간이 더 많지 않나? 그냥 하나씩 비교하는게 낫지않나? 생각했습니다.

​

상황 : 1개의 숫자만 새로 맨앞에 추가가 됨

key가 없는경우 -> 2만개 수정 -> 비교 : 2만번, 수정 : 2만번

key가 있는경우(인덱싱 잘 되어있다는 가정) -> 비교 : 2만 * (log2만) = 약 30만번 이하.., 수정 : 1번

​

​

key를 정할때의 주의사항에 대해서도 나와있습니다. Keys should be stable, predictable, and unique

라고 되어있는데, 아마 자식 노드를 전부 순회하면서 diff를 찾는게 O(N)이 아닐것 같다는 생각입니다.

Math.random()같은것을 하면 오히려 성능이 저하된다고 하는것을 보니, 인덱싱 기법을 통해서 O(lgN) 수준으로 낮추지 않았을까 생각됩니다.

​

검색하는데 걸리는 시간 < real dom을 수정하는데 걸리는 시간이라서 이러한 방법을 채택하지 않았나 싶습니다.

보통 1초에 수억번 비교가 가능하니까요..

​

React Fiber

새로운 reconciliation algorithm입니다. React16부터 나왔다고는 하는데..

react 의 core code를 변경했다고 합니다, 여기를 읽어보세요... 저는 이만

https://github.com/acdlite/react-fiber-architecture

acdlite/react-fiber-architecture