본문으로 건너뛰기
黯羽轻扬매일 조금씩

React 리스트 Diff

무료2017-05-28#Front-End#JS#list diff algorithm#tree diff algorithm#dom diff#react virtual dom diff

신기해 보이지만 알고 보면 대단하지 않은 React Diff

1. Tree Diff

트리의 diff는 상대적으로 복잡한 문제입니다. 먼저 간단한 시나리오를 생각해보죠:

    A           A'
   / \   ?    / | \
  B   C  ->  G  B   C
 / \  |         |   |
D   E F         D   E

diff(treeA, treeA')의 결과는 다음과 같아야 합니다:

1. B 앞에 G 삽입(insert)
2. E를 F 자리로 이동(move)
3. F 삭제(remove)

treeA에 위의 3단계를 적용하면 treeA'를 얻을 수 있습니다. 트리의 규모가 작을 때는 눈으로도 금방 알 수 있죠. 어떻게 했는지 되짚어봅시다:

1. 위에서 아래로 관찰하며, 완전히 다르면 더 찾지 않습니다.
2. 현재 레이어의 노드를 비교하여 추가(새로 생김), 삭제(없어짐)를 찾습니다.
3. 아래쪽의 서브 트리 구조가 유사한지 살펴보고 이동(기존 노드의 위치 변경)인지 판단합니다.

컴퓨터가 이를 수행하게 하려면 추가와 삭제는 찾기 쉽지만, 이동의 판정은 꽤 복잡해집니다. 우선 트리의 유사도를 수치화(예: 가중 편집 거리)해야 하고, 유사도가 어느 정도일 때 이동이 삭제+추가보다 효율적인지(작업 단계가 더 적은지) 결정해야 합니다.

P.S. Tree Diff 알고리즘에 관심이 있다면 Matching, diffing and merging XML을 참고하세요. 2008년 글이라 꽤 오래되었지만 흥미롭습니다.

2. React의 가정

React 내부에서 관리하는 가상 DOM 트리 역시 diff 문제에 직면합니다. DOM 트리가 빈번하게 업데이트될 때(상호작용이 잦을 경우), 너무 복잡한 tree diff 방안은 성능 문제를 야기할 수 있습니다. DOM 조작 시나리오의 특징을 고려해보면 다음과 같습니다:

  • 국소적인 작은 변화가 많고, 대규모 변화는 적습니다. (성능을 위해 표시/숨김으로 회피함)

  • 레이어를 넘나드는 이동은 적고, 같은 레이어 내에서의 이동은 많습니다. (예: 테이블 정렬)

대규모 변화가 많다면 diff는 사실상 의미가 없으며 순수한 성능 낭비일 뿐입니다. 레이어를 넘나드는 이동이 많다면 정교한 이동(move) 판정이 필수적이며 알고리즘 요구 사항이 매우 높아집니다. DOM 조작 시나리오는 다행히 높은 요구 사항을 필요로 하지 않으므로, 이에 근거하여 몇 가지 가정을 세웠습니다:

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

즉:

  • 서로 다른 타입의 엘리먼트는 서로 다른 서브 트리에 대응한다고 가정합니다. ("서브 트리 구조가 유사한지 아래로 훑어보기"를 고려하지 않으므로, 이동 판정이 쉬워집니다.)

  • 전후 구조 모두 고유한 key를 가지며 이를 diff의 근거로 삼습니다. 동일한 key는 동일한 엘리먼트임을 나타낸다고 가정합니다. (비교 비용 절감)

또한, 만약의 경우를 대비해 React는 shouldComponentUpdate 훅을 제공하여 사용자가 직접 diff 과정에 개입하고 오판을 방지할 수 있도록 합니다.

3. 가상 DOM 트리 Diff와 리스트 Diff

트리 구조를 직접 비교하려고 하면 막막합니다. (사람 눈에는 형태 구조의 차이가 쉽게 보이지만 컴퓨터는 서툴기 때문이죠.) 예를 들어:

Page
  Header
    div
      img
      p
  List
    Item1
      img
      p
      button
    Item2...

diff(Page, newPage)를 통해 직접 결과를 얻기는 힘들어 보입니다. 이때 문제의 규모를 줄이는 좋은 방법은 바로 재귀입니다:

1. 각 노드가 스스로 업데이트가 필요한지 확인합니다.
2. 필요하다면 직계 자식들을 diff 하여 추가, 삭제, 이동, 수정을 찾아냅니다.
3. 수정이 필요한 노드에 대해 리프(leaf) 노드까지 재귀적으로 아래로 내려가며 확인합니다.

이렇게 트리의 diff는 리스트(list) diff로 분해되었고, 실제로 구현해야 할 부분은 오직 리스트 diff 부분이 되었습니다. 문제가 매우 명확해졌죠.

4. 리스트 Diff

두 개의 1차원 정수 배열을 생각해봅시다:

var oldList = [1, 2, 3, 7, 4];
var newList = [1, 4, 5, 3, 7, 6];

어떻게 diff를 통해 추가/삭제/이동을 찾아낼까요?

1. 이전 리스트를 순회하며 삭제를 찾습니다.
2. 새 리스트를 순회하며 추가와 이동을 찾습니다.

간단한 방안

성능과 복잡도를 고려하지 않고, 가장 단순하고 무식한 리스트 diff를 구현해 봅시다:

var diff = function(oldList, newList) {
    var changes = [];
    // 위치를 시뮬레이션하기 위한 미러링
    var _oldList = oldList.slice();
    // 이전 리스트 순회, 삭제 찾기
    oldList.forEach(function(item, i) {
        if (newList.indexOf(item) === -1) {
            changes.push({
                type: 'remove',
                index: i
            });
            _oldList.splice(i, 1);
        }
    });

    // 새 리스트 순회, 추가/이동 찾기
    newList.forEach(function(item, i) {
        var index = _oldList.indexOf(item);
        if (index === -1) {
            // 추가
            changes.push({
                type: 'insert',
                index: i,
                item: item
            });
            _oldList.splice(i, 0, item);
        }
        else {
            // 이동
            if (index !== i) {
                var step = {
                    type: 'move',
                    from: index,
                    to: i
                };
                changes.push(step);
                move(_oldList, step.from, step.to);
            }
        }
    });

    return changes;
};
var move = function(list, from, to) {
    var item = list.splice(from, 1);
    if (from > to)
        list.splice(to, 0, item[0]);
    else
        list.splice(to - 1, 0, item[0]);
};

patch 시뮬레이션:

var showSteps = function(changes) {
    changes.forEach(function(change) {
        switch (change.type) {
            case 'insert':
                console.log('insert ' + change.item + ' before ' + oldList[change.index]);
                oldList.splice(change.index, 0, change.item);
                break;
            case 'remove':
                console.log('remove ' + oldList[change.index]);
                oldList.splice(change.index, 1);
                break;
            case 'check':
                console.log('check ' + oldList[change.index] + ' for update');
                break;
            case 'move':
                console.log('move ' + oldList[change.from] + ' to ' + oldList[change.to]);
                move(oldList, change.from, change.to);
                break;
            default:
                cosole.error('not here');
                break;
        }
        console.log(oldList);
    });
};

실행 결과 작업 단계:

source  1 2 3 7 4
target  1 4 5 3 7 6

remove 2
  1 3 7 4
move 4 to 3
  1 4 3 7
insert 5 before 3
  1 4 5 3 7
insert 6 before undefined
  1 4 5 3 7 6

위치를 시뮬레이션하기 위해 _oldList 미러를 사용하는 요령을 부렸는데, 이는 추가/삭제/이동이 index에 미치는 영향을 계산하기 위함입니다. 다만 별도의 공간 비용이 발생하므로 이 부분을 제거할 방법을 찾아봅시다.

공간 비용 최적화

위치 시뮬레이션 작업을 제거하고, 직접 index changes를 계산합니다:

// 1. 위치 시뮬레이션을 index change 기록으로 대체함. 먼저 새 리스트 순회 후 이전 리스트 순회
var diff = function(oldList, newList) {
    var changes = [];
    // 변화가 oldList의 비교되지 않은 요소의 index에 미치는 영향을 계산함. 구간 값임.
    // 내 앞의 요소를 더 앞으로 보내는 것은 내 index에 영향을 주지 않기 때문.
    // 이동 시 <=lastIndex인 index에만 영향을 줌.
    // <=index: delta 형식으로 표현함.
    var maxLength = Math.max(oldList.length, newList.length);
    var oldIndexChanges = new Array(maxLength).fill(0);
    // 수정 전의 index
    var _index;

    // 새 리스트 순회, 추가/이동 찾기
    newList.forEach(function(item, i) {
        var index = oldList.indexOf(item);
        if (index === -1) {
            // 추가
            changes.push({
                type: 'insert',
                index: i,
                item: item
            });
            // insert는 oldList 뒤쪽 모든 요소의 index에 영향을 줌
            oldIndexChanges[maxLength - 1]++;
        }
        else {
            _index = index;
            // old index 수정
            // index 위치까지 sum delta를 구함
            index += oldIndexChanges.reduce(function(acc, delta, idx) {
                if (idx >= index)
                    return acc + delta;
                else
                    return acc;
            });
            // 이동
            if (index !== i) {
                var step = {
                    type: 'move',
                    from: index,
                    to: i
                };
                changes.push(step);
                if (index > i) {
                    // move는 oldList에서 <=from 인 요소에 영향을 줌
                    oldIndexChanges[_index]++;
                }
                else {
                    // from이 to보다 작을 수 없음
                    // 앞에서부터 훑어오기 때문에 [0, to-1] 위치는 확정되어 앞의 요소를 가져오지 않기 때문
                    console.error('impossible');
                }
            }
        }
    });

    // 이전 리스트 순회, 삭제 찾기
    // 총 delta 계산
    // 추가와 이동을 거친 후, 삭제될 요소는 반드시 맨 뒤에 있으며 모든 index change의 영향을 받음
    var indexDelta = oldIndexChanges.reduce(function(acc, delta) {
        return acc + delta;
    });
    oldList.forEach(function(item, i) {
        if (newList.indexOf(item) === -1) {
            // old index 수정
            i += indexDelta;
            changes.push({
                type: 'remove',
                index: i
            });
        }
    });

    return changes;
};

// 2. patch 시뮬레이션
var showSteps = function(changes) {
    changes.forEach(function(change) {
        switch (change.type) {
            case 'insert':
                console.log('insert ' + change.item + ' before ' + oldList[change.index]);
                oldList.splice(change.index, 0, change.item);
                break;
            case 'remove':
                console.log('remove ' + oldList[change.index]);
                oldList.splice(change.index, 1);
                break;
            case 'check':
                console.log('check ' + oldList[change.index] + ' for update');
                break;
            case 'move':
                console.log('move ' + oldList[change.from] + ' to ' + oldList[change.to]);
                move(oldList, change.from, change.to);
                break;
            default:
                cosole.error('not here');
                break;
        }
        console.log(oldList);
    });
};

실행 결과 작업 단계:

source  1 2 3 7 4
target  1 4 5 3 7 6

move 4 to 2
  1 4 2 3 7
insert 5 before 2
  1 4 5 2 3 7
move 3 to 2
  1 4 5 3 2 7
move 7 to 2
  1 4 5 3 7 2
insert 6 before 2
  1 4 5 3 7 6 2
remove 2
  1 4 5 3 7 6

작업 단계가 2단계 늘어났습니다. 이동을 먼저 하고 삭제를 나중에 했기 때문인데(삭제를 나중에 하면 추가/이동 시 삭제로 인한 index 변동을 고려하지 않아도 됨), 삭제될 예정인 2를 대상으로 한 두 단계의 move는 무의미합니다. 이를 회피할 방법을 찾아야 하는데 여기서는 생략하고 바로 React의 원본 구현을 살펴보겠습니다.

5. React 리스트 Diff

우리의 생각과 비슷하게, 새 리스트를 먼저 순회하고 이전 리스트를 나중에 순회합니다:

var diff = function(oldList, newList) {
    var changes = [];
    // 이전에 방문한 children 리스트 중 가장 큰 index
    var lastIndex = 0;
    // 마지막으로 배치된 노드, 추가/이동 시 사용함
    var lastPlacedNode = null;

    // 새 리스트 순회, 추가/이동 찾기
    newList.forEach(function(item, i) {
        var index = oldList.indexOf(item);
        if (index === -1) {
            // 추가
            changes.push({
                type: 'insert',
                item: item,
                afterNode: lastPlacedNode
            });
        }
        else {
            // lastIndex로 상대 위치가 변하지 않은 이동을 걸러냄
            if (index < lastIndex) {
                // 이동
                var step = {
                    type: 'move',
                    item: item,
                    afterNode: lastPlacedNode
                };
                changes.push(step);
            }
            lastIndex = Math.max(index, lastIndex);
        }
        lastPlacedNode = item;
    });

    // 이전 리스트 순회, 삭제 찾기
    oldList.forEach(function(item, i) {
        if (newList.indexOf(item) === -1) {
            changes.push({
                type: 'remove',
                index: i
            });
        }
    });

    return changes;
};

여기서 매우 기발한 최적화는 lastIndex입니다. 훑어본 원본 list 중 가장 오른쪽 요소의 index를 기록하다가, 원래의 상대 위치가 더 이상 요구 사항을 충족하지 못할 때(이동하지 않으면 안 될 때) 비로소 이동을 수행합니다. 이렇게 함으로써 원래의 상대 위치를 최대한 활용하고 불필요한 이동을 방지합니다.

patch 시뮬레이션:

var showSteps = function(changes) {
    // 이동 시 이전 위치를 조회하기 위해 하나 남겨둠
    var _oldList = oldList.slice();
    // 추가/이동/삭제 시 DOM 조작을 시뮬레이션하려면 패칭 중인 이전 요소의 현재 index를 알아야 함
    // 실제 DOM 패치 시에는 요소 탐색 후 DOM API가 index 없이도 조작 가능하므로 필요 없음
    var patchingIndex = -1;
    changes.forEach(function(change) {
        switch (change.type) {
            case 'insert':
                console.log('insert ' + change.item + ' after ' + change.afterNode);
                patchingIndex = oldList.indexOf(change.afterNode);
                insertAfter(oldList, change.item, patchingIndex);
                break;
            case 'remove':
                console.log('remove ' + _oldList[change.index]);
                patchingIndex = oldList.indexOf(_oldList[change.index]);
                oldList.splice(patchingIndex, 1);
                break;
            case 'move':
                console.log('move ' + change.item + ' to pos after ' + change.afterNode);
                patchingIndex = oldList.indexOf(change.afterNode);
                move(oldList, oldList.indexOf(change.item), patchingIndex);
                break;
            default:
                cosole.error('not here');
                break;
        }
        console.log(oldList);
    });
};
var move = function(list, from, to) {
    var item = list.splice(from, 1);
    if (from > to)
        list.splice(to + 1, 0, item[0]);
    else
        list.splice(to, 0, item[0]);
};
var insertAfter = function(list, item, index) {
    list.splice(index + 1, 0, item);
};

실행 결과 작업 단계:

source  1 2 3 7 4
target  1 4 5 3 7 6

insert 5 after 4
  1 2 3 7 4 5
move 3 to pos after 5
  1 2 7 4 5 3
move 7 to pos after 3
  1 2 4 5 3 7
insert 6 after 7
  1 2 4 5 3 7 6
remove 2
  1 4 5 3 7 6

1과 4를 만났을 때는 원래의 상대 순서가 올바르므로 움직이지 않습니다. 3을 만났을 때 비로소 더 이상 원래 위치를 유지할 수 없게 되어 이동을 수행합니다.

이 예제만 본다면 React의 구현이 가장 효율적인 것은 아닙니다. 우리가 처음 작성했던 간단한 버전(삭제 먼저 하고 추가/이동 나중에 하기)은 단 4단계만으로 끝낼 수 있었으니까요.

6. 온라인 데모

예제 시나리오에서의 React 구현 및 글 본문의 각 diff 메서드 예시: http://www.ayqy.net/temp/react/demo/list-diff.html

브라우저 콘솔을 열고 "리스트 업데이트"를 클릭하여 diff 결과를 확인해 보세요.

P.S. React 버전은 15.5.4입니다.

참고 자료

댓글

아직 댓글이 없습니다

댓글 작성