[Open WebUI] 재귀적 메시지 리스트 생성을 반복문으로 전환하여 O(d²) → O(d) 개선

PR 링크: open-webui/open-webui#22194 상태: Merged | 변경: +11 / -11

들어가며

Open WebUI의 프론트엔드에서 대화 메시지 목록을 생성하는 createMessagesList 함수가 재귀 + 스프레드 연산자로 구현되어 있었습니다. 이 패턴은 대화 깊이(d)에 대해 O(d²)의 배열 복사를 발생시킵니다. 이 PR은 반복문 + push + reverse로 변환하여 O(d)로 개선합니다.

핵심 코드 분석

Before: 재귀 + 스프레드 — O(d²) 배열 복사

export const createMessagesList = (history, messageId) => {
    if (messageId === null) {
        return [];
    }
    const message = history.messages[messageId];
    if (message === undefined) {
        return [];
    }
    if (message?.parentId) {
        return [...createMessagesList(history, message.parentId), message];
    } else {
        return [message];
    }
};

[...createMessagesList(history, message.parentId), message]는 매 재귀 단계마다 이전 결과 배열 전체를 새 배열로 복사합니다. 깊이 d일 때 총 복사 원소 수는 1 + 2 + ... + d = O(d²)입니다.

After: 반복문 + push + reverse — O(d)

export const createMessagesList = (history, messageId) => {
    const list = [];
    let currentId = messageId;

    while (currentId !== null && currentId !== undefined) {
        const message = history.messages[currentId];
        if (message === undefined) {
            break;
        }
        list.push(message);
        currentId = message.parentId;
    }

    return list.reverse();
};

push는 amortized O(1)이고, 마지막 reverse는 O(d)입니다. 재귀 호출 스택도 제거되어 깊은 대화에서 스택 오버플로우 위험도 사라집니다.

왜 이게 좋은가

1. 스프레드 연산자의 숨겨진 비용

JavaScript의 [...arr, element]는 직관적이지만, 매번 새 배열을 할당하고 기존 원소를 모두 복사합니다. 루프나 재귀에서 이 패턴을 사용하면 의도치 않게 O(n²) 비용이 발생합니다.

깊이 1: [m1]                    → 1개 복사
깊이 2: [...[m1], m2]           → 1 + 2 = 3개 복사  
깊이 3: [...[m1, m2], m3]       → 1 + 2 + 3 = 6개 복사
깊이 d:                         → d(d+1)/2 개 복사

2. 메모리 압력 감소

재귀 버전은 매 단계마다 새 배열을 할당하고, 이전 배열은 GC 대상이 됩니다. 깊이 100인 대화에서 100개의 중간 배열이 생성되었다가 즉시 버려집니다. 반복문 버전은 배열 1개만 사용합니다.

3. 콜 스택 안전성

JavaScript 엔진의 기본 콜 스택 깊이는 보통 10,000~15,000 수준입니다. 매우 긴 대화에서는 재귀 깊이가 이 한계에 도달할 수 있습니다. 반복문은 이 제한에서 자유롭습니다.

4. 동일한 동작 보장

입력과 출력이 완전히 동일합니다. 분기 대화(branched chats)에서도 광범위하게 테스트되어 부작용이 없음이 확인되었습니다.

참고 자료

• V8 Blog: Spread Elements — V8 엔진의 스프레드 연산자 최적화
• MDN: Array.prototype.reverse() — in-place 배열 반전