React 리스트 Diff 알고리즘

TL;DR

React가 [<li key>, <li key>, ...] 같은 자식 배열을 diff하는 알고리즘은 단일 파일의 reconcileChildrenArray 함수 하나에 있다. 핵심은 4가지다:

1. 단방향(forward-only) 스캔. Fiber에는 back-pointer가 없어서 (양끝에서 좁혀오는 two-ended diff 불가) 왼쪽→오른쪽 한 방향으로만 훑는다.
2. 2단계 전략. 먼저 빠른 경로(앞에서부터 슬롯이 어긋나지 않는 동안 1:1 비교) → 어긋나는 순간 느린 경로(남은 old child를 key→Fiber Map에 넣고 조회).
3. key가 일치(identity)의 기준. 같은 위치라도 key가 다르면 재사용 안 함. key가 같고 type이 같으면 Fiber를 재사용(props만 교체).
4. lastPlacedIndex로 "이동"을 판정. 노드를 옮길지 그대로 둘지를 증가하는 인덱스 커서 하나로 결정한다 — 이게 알고리즘의 가장 영리한 부분.

복잡도: 최선 O(n) (순서 안 바뀜), 최악 O(n) + Map 구축 (이동/삽입 많음). 흔히 말하는 O(n³) 트리 diff를 **휴리스틱으로 O(n)**으로 누른 것이 React diff의 본질이고, 그 휴리스틱의 핵심이 바로 key다.

---

1. 전제 — 왜 단방향인가

함수 맨 위 주석이 설계 의도를 그대로 설명한다:

    // This algorithm can't optimize by searching from both ends since we
    // don't have backpointers on fibers. I'm trying to see how far we can get
    // with that model. If it ends up not being worth the tradeoffs, we can
    // add it later.

    // Even with a two ended optimization, we'd want to optimize for the case
    // where there are few changes and brute force the comparison instead of
    // going for the Map. It'd like to explore hitting that path first in
    // forward-only mode and only go for the Map once we notice that we need
    // lots of look ahead. This doesn't handle reversal as well as two ended
    // search but that's unusual. Besides, for the two ended optimization to
    // work on Iterables, we'd need to copy the whole set.

    // In this first iteration, we'll just live with hitting the bad case
    // (adding everything to a Map) in for every insert/move.

요점:

• Vue 2 / Preact는 two-ended diff (양끝에서 좁혀옴 → 역순 정렬에 강함). React는 Fiber에 prev 포인터가 없어서 안 한다.
• Fiber 자식은 단일 연결 리스트 (child → sibling → sibling → null). 앞으로만 갈 수 있다.
• 대신 React는 "변경이 적은 흔한 경우"를 brute-force로 빠르게 처리하고, 진짜 어려울 때만 Map을 쓴다.

---

2. 알고리즘 구조 — 3개의 단계

reconcileChildrenArray는 크게 세 블록으로 나뉜다.

[Phase 1] 빠른 경로: old/new를 앞에서부터 1:1로 짝맞춤
            (slot의 key가 맞는 동안 계속)
   │
   ├─ new를 다 소진? → 남은 old 전부 삭제하고 끝  [Phase 2a]
   ├─ old를 다 소진? → 남은 new 전부 삽입하고 끝   [Phase 2b]
   │
   ▼
[Phase 3] 느린 경로: 남은 old를 key→Fiber Map에 넣고
            남은 new를 Map에서 조회하며 매칭 (이동/삽입/삭제)

2.1 상태 변수

    let knownKeys: Set<string> | null = null;

    let resultingFirstChild: Fiber | null = null;
    let previousNewFiber: Fiber | null = null;

    let oldFiber = currentFirstChild;
    let lastPlacedIndex = 0;
    let newIdx = 0;
    let nextOldFiber = null;

• oldFiber — 현재 보고 있는 기존 Fiber (current 트리).
• newIdx — 현재 보고 있는 새 children 배열 인덱스.
• resultingFirstChild / previousNewFiber — 결과로 만들어지는 새 sibling 리스트를 엮는 포인터.
• lastPlacedIndex — 이동 판정의 핵심 커서 (§4에서 상세).

---

3. Phase 1 — 빠른 경로 (앞에서부터 1:1)

    for (; oldFiber !== null && newIdx < newChildren.length; newIdx++) {
      if (oldFiber.index > newIdx) {
        nextOldFiber = oldFiber;
        oldFiber = null;
      } else {
        nextOldFiber = oldFiber.sibling;
      }
      const newFiber = updateSlot(
        returnFiber,
        oldFiber,
        newChildren[newIdx],
        lanes,
      );
      if (newFiber === null) {
        // ... 슬롯이 안 맞으면 루프 탈출 → 느린 경로로
        if (oldFiber === null) {
          oldFiber = nextOldFiber;
        }
        break;
      }
      if (shouldTrackSideEffects) {
        if (oldFiber && newFiber.alternate === null) {
          // 슬롯은 맞췄지만 기존 fiber를 재사용 못 했으면 기존 것 삭제
          deleteChild(returnFiber, oldFiber);
        }
      }
      lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
      // 결과 sibling 리스트에 이어붙임
      if (previousNewFiber === null) {
        resultingFirstChild = newFiber;
      } else {
        previousNewFiber.sibling = newFiber;
      }
      previousNewFiber = newFiber;
      oldFiber = nextOldFiber;
    }

핵심은 updateSlot — key가 맞으면 Fiber 반환, 안 맞으면 null 반환:

    if (typeof newChild === 'object' && newChild !== null) {
      switch (newChild.$$typeof) {
        case REACT_ELEMENT_TYPE: {
          if (
            newChild.key === key
          ) {
            const prevDebugInfo = pushDebugInfo(newChild._debugInfo);
            const updated = updateElement(
              returnFiber,
              oldFiber,
              newChild,
              lanes,
            );
            currentDebugInfo = prevDebugInfo;
            return updated;
          } else {
            return null;   // ← key 불일치 → 빠른 경로 종료 신호
          }
        }

→ 같은 슬롯(같은 인덱스)의 old.key와 new.key가 다르면 즉시 null → Phase 1 루프가 break되고 느린 경로로 넘어간다. 이것이 "맨 앞에 항목 하나만 추가해도 그 뒤가 전부 어긋나는" 상황에서 Map 경로로 가는 이유.

updateElement는 key가 맞은 뒤 type까지 같아야 재사용한다:

    if (current !== null) {
      if (
        current.elementType === elementType ||
        // ... hot reload / lazy 예외
      ) {
        // Move based on index
        const existing = useFiber(current, element.props);  // ← Fiber 재사용 (props 교체)
        coerceRef(existing, element);
        existing.return = returnFiber;
        return existing;
      }
    }
    // Insert
    const created = createFiberFromElement(element, returnFiber.mode, lanes); // ← 새로 생성
    coerceRef(created, element);
    created.return = returnFiber;
    return created;

정리: key 일치 → type 일치 둘 다 만족해야 기존 Fiber(=DOM 노드, state)를 재사용. key는 맞는데 type이 다르면 새 Fiber 생성 (기존 것은 삭제).

Phase 2a / 2b — 한쪽이 먼저 소진

    if (newIdx === newChildren.length) {
      // 새 children을 다 썼다 → 남은 old는 전부 삭제
      deleteRemainingChildren(returnFiber, oldFiber);
      // ...
      return resultingFirstChild;
    }

    if (oldFiber === null) {
      // 기존 children을 다 썼다 → 남은 new는 전부 삽입 (fast path)
      for (; newIdx < newChildren.length; newIdx++) {
        const newFiber = createChild(returnFiber, newChildren[newIdx], lanes);
        if (newFiber === null) {
          continue;
        }
        lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx);
        // ... sibling 리스트에 이어붙임
      }
      return resultingFirstChild;
    }

• new 먼저 소진 (newIdx === length): 뒤에 남은 old는 더 이상 필요 없음 → deleteRemainingChildren. (예: 리스트 끝에서 항목 제거.)
• old 먼저 소진 (oldFiber === null): 남은 new는 전부 신규 → createChild로 삽입. (예: 리스트 끝에 항목 추가 — 가장 흔하고 빠른 케이스.)

→ 끝에 추가/제거는 Phase 1+2만으로 끝난다. Map을 안 만든다. 그래서 append가 제일 싸다.

---

4. placeChild — 이동 판정의 핵심 ★

이 알고리즘에서 가장 영리하고 가장 오해받는 부분. "노드를 이동시킬지(Placement flag) 그냥 둘지"를 lastPlacedIndex 하나로 결정한다.

  function placeChild(
    newFiber: Fiber,
    lastPlacedIndex: number,
    newIndex: number,
  ): number {
    newFiber.index = newIndex;
    if (!shouldTrackSideEffects) {
      // hydration 중 useId 알고리즘용
      newFiber.flags |= Forked;
      return lastPlacedIndex;
    }
    const current = newFiber.alternate;
    if (current !== null) {
      const oldIndex = current.index;
      if (oldIndex < lastPlacedIndex) {
        // This is a move.
        newFiber.flags |= Placement | PlacementDEV;
        return lastPlacedIndex;
      } else {
        // This item can stay in place.
        return oldIndex;
      }
    } else {
      // This is an insertion.
      newFiber.flags |= Placement | PlacementDEV;
      return lastPlacedIndex;
    }
  }

4.1 규칙

• current === null (재사용된 Fiber 없음) → 삽입 → Placement flag.
• current !== null (Fiber 재사용함) → 기존 위치 oldIndex와 lastPlacedIndex 비교:
  • oldIndex < lastPlacedIndex → 이동(move) → Placement flag. (lastPlacedIndex는 그대로.)
  • oldIndex >= lastPlacedIndex → 그대로 둠 → lastPlacedIndex = oldIndex로 갱신.

4.2 직관 — "가장 긴 증가 수열을 안 건드린다"

lastPlacedIndex는 "지금까지 제자리에 둔 노드들의 최대 old-index" 다. 새 노드의 oldIndex가 이 값보다 크거나 같으면 → "오른쪽으로 잘 가고 있다" → 안 움직여도 됨. 작으면 → "뒤로 역행했다" → 그 노드를 앞으로 끌어와야 함 → 이동 표시.

즉 React는 상대 순서가 유지되는(증가하는 old-index) 노드들은 가만히 두고, 역행하는 노드만 옮긴다. 이것이 최소 이동에 가까운 결과를 O(n)으로 얻는 트릭.

4.3 예시로 보는 이동 판정

예시 A — [A,B,C,D] → [A,C,B,D] (B와 C 교환)

new	재사용 old.index	lastPlacedIndex (직전)	판정	lastPlacedIndex (이후)
A	0	0	0 >= 0 유지	0
C	2	0	2 >= 0 유지	2
B	1	2	1 < 2 이동	2
D	3	2	3 >= 2 유지	3

→ B 하나만 이동. A·C·D는 DOM을 안 건드린다.

예시 B — [A,B,C] → [C,A,B] (C를 맨 앞으로)

new	재사용 old.index	lastPlacedIndex	판정
C	2	0	2 >= 0 유지 → lastPlaced=2
A	0	2	0 < 2 이동
B	1	2	1 < 2 이동

→ A, B가 이동으로 표시됨 (C는 제자리). 결과는 맞지만 이동 횟수는 최적이 아닐 수 있다 — "C를 한 번 옮기는" 게 사람 눈엔 최소지만, 단방향 그리디라 A·B를 옮긴다. 앞쪽 삽입/이동이 비싼 이유.

---

5. Phase 3 — 느린 경로 (key→Fiber Map)

Phase 1이 중간에 깨지면(슬롯 불일치) 남은 old child들을 Map에 넣는다.

    // Add all children to a key map for quick lookups.
    const existingChildren = mapRemainingChildren(oldFiber);

  function mapRemainingChildren(
    currentFirstChild: Fiber,
  ): Map<string | number | ReactOptimisticKey, Fiber> {
    const existingChildren: Map</* ... */> = new Map();

    let existingChild: null | Fiber = currentFirstChild;
    while (existingChild !== null) {
      if (existingChild.key === null) {
        existingChildren.set(existingChild.index, existingChild);   // key 없으면 index를 키로
      } else if (/* optimistic key */) {
        existingChildren.set(-existingChild.index - 1, existingChild);
      } else {
        existingChildren.set(existingChild.key, existingChild);     // key 있으면 key를 키로
      }
      existingChild = existingChild.sibling;
    }
    return existingChildren;
  }

핵심: key가 있으면 Map<key, Fiber>, key가 없으면 Map<index, Fiber>. 그래서 key 없는 리스트는 "index가 곧 key" 처럼 동작 → 순서가 바뀌면 전부 어긋난다 (key의 중요성).

그 다음 남은 new를 Map에서 조회:

    for (; newIdx < newChildren.length; newIdx++) {
      const newFiber = updateFromMap(
        existingChildren,
        returnFiber,
        newIdx,
        newChildren[newIdx],
        lanes,
      );
      if (newFiber !== null) {
        if (shouldTrackSideEffects) {
          const currentFiber = newFiber.alternate;
          if (currentFiber !== null) {
            // Map에서 재사용했으면, 삭제 목록에 안 들어가게 Map에서 제거
            existingChildren.delete(
              currentFiber.key === null ? newIdx : currentFiber.key,
            );
          }
        }
        lastPlacedIndex = placeChild(newFiber, lastPlacedIndex, newIdx); // 같은 이동 판정
        // ... sibling 리스트 연결
      }
    }

    if (shouldTrackSideEffects) {
      // Map에 남은(= new에서 안 쓰인) old는 전부 삭제
      existingChildren.forEach(child => deleteChild(returnFiber, child));
    }

updateFromMap의 조회 로직 — key가 있으면 key로, 없으면 newIdx로:

        case REACT_ELEMENT_TYPE: {
          const matchedFiber =
            existingChildren.get(
              newChild.key === null ? newIdx : newChild.key,
            ) ||
            (enableOptimisticKey &&
              existingChildren.get(-newIdx - 1)) ||
            null;
          const prevDebugInfo = pushDebugInfo(newChild._debugInfo);
          const updated = updateElement(
            returnFiber,
            matchedFiber,
            newChild,
            lanes,
          );
          currentDebugInfo = prevDebugInfo;
          return updated;
        }

흐름:

1. 남은 new 각각을 Map에서 key로 조회.
2. 찾으면 → Fiber 재사용 + Map에서 제거 + placeChild로 이동 판정.
3. 못 찾으면 → 새 Fiber 삽입.
4. 루프 끝나고 Map에 남은 것(= 새 리스트에 없는 old) → 전부 삭제.

→ 이동/삽입/삭제가 전부 이 한 패스에서 처리된다. Map 덕분에 "리스트 중간에서 사라졌다 다시 나타나는" 항목도 O(1) 조회로 복원(=이동)된다.

---

6. 결과물 — flag로 commit에 전달

diff의 산출물은 DOM 조작이 아니라 Fiber에 찍힌 flag다. (commit 단계가 이 flag를 보고 실제 DOM을 만진다 — analysis/react-fiber-architecture/REPORT.md의 commit 단계 참조.)

상황	표시
새 항목	`newFiber.flags
이동 항목	`newFiber.flags
제자리 + props 변경	useFiber로 재사용, props diff는 completeWork에서 Update
삭제 항목	deleteChild → returnFiber의 deletions 리스트 + ChildDeletion flag

흥미로운 점: React에서 "삽입"과 "이동"은 같은 Placement flag다. commit 때 둘 다 insertBefore/appendChild로 처리되기 때문 (이동 = 기존 DOM 노드를 새 위치로 insertBefore).

---

7. key의 역할 — 코드로 증명되는 것들

지금까지 본 코드가 "왜 key를 잘 줘야 하는가"를 그대로 설명한다:

1. key 없으면 index가 key가 된다 (mapRemainingChildren:485, updateFromMap:1010). → 순서가 바뀌면 모든 슬롯이 어긋나 state/DOM이 엉뚱하게 재사용됨.
2. 맨 앞 삽입이 비싸다 (placeChild의 그리디 이동 판정). → key가 있어도 단방향 그리디라 앞쪽 변경은 뒤 노드들을 이동으로 만든다. 단, key가 있으면 최소한 Fiber/state는 보존된다 (DOM 재생성 X).
3. key+type이 둘 다 같아야 재사용 (updateElement:599-625). → 같은 자리에 <div key="a"> → <span key="a">면 Fiber를 새로 만든다.
4. 랜덤/인덱스 key는 최악 — 매 렌더 key가 바뀌면 Map 조회가 전부 miss → 전부 삭제 후 전부 삽입 → state 전손실 + DOM 재생성.

안티패턴

{items.map((item, i) => <Row key={i} {...item} />)}      // ❌ index key — 순서 변경에 취약
{items.map((item) => <Row key={Math.random()} />)}        // ❌ 매번 새 key — 전부 재생성
{items.map((item) => <Row key={item.id} {...item} />)}    // ✅ 안정적 고유 key

---

8. 복잡도 / 성능 요약

시나리오	경로	비용
끝에 추가	Phase 1 → 2b	O(n), Map 없음
끝에서 제거	Phase 1 → 2a	O(n), Map 없음
props만 변경 (순서 동일)	Phase 1 전체	O(n), Map 없음
중간 삽입/삭제/이동	Phase 1 → 3	O(n) + Map 구축
맨 앞 삽입	Phase 3	O(n) + Map, 뒤 노드 다수 이동 표시
전체 순서 뒤집기	Phase 3	O(n) + Map, 이동 다수 (two-ended였다면 더 쌌을 케이스)

핵심: 거의 모든 경우 O(n). 다만 "이동 표시 개수"는 단방향 그리디라 최적이 아닐 수 있다 (역순/앞쪽 변경에 약함). 그래도 정확성은 보장되고, 실무 변경 패턴(끝 추가/제거, 정렬)에는 충분히 빠르다.

---

9. 다른 라이브러리와 비교

	React	Vue 2	Preact
방향	단방향 forward	two-ended (양끝)	two-ended 유사
역순/앞쪽 변경	상대적으로 약함	강함	강함
자료구조	Fiber 단일 연결 리스트 (back-pointer 없음)	vnode 배열 (양방향 인덱스)	vnode 배열
이동 판정	lastPlacedIndex 그리디	양끝 포인터 4개	유사
미매칭 처리	key→Fiber Map	key→index Map	유사

React가 단방향을 고른 이유는 §1 주석대로 Fiber에 back-pointer가 없고, Iterable(무한 스트림 가능)도 지원해야 하기 때문. 배열 전체를 복사해야 two-ended가 가능한데 그 비용을 피했다.