[Open WebUI] O(n²) unshift를 O(n) push+reverse로 교체하여 메시지 빌드 최적화

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

들어가며

Open WebUI의 buildMessages 함수는 채팅 히스토리에서 부모-자식 관계를 따라 메시지 목록을 역순으로 구성합니다. 기존 코드는 루프 안에서 Array.unshift()를 반복 호출하여 O(n²) 시간 복잡도를 가지고 있었습니다. 이 PR은 단 2줄의 변경으로 O(n)으로 개선합니다.

핵심 코드 분석

Before: unshift() — O(n²)

// Messages.svelte
_messages.unshift(message);
message = message.parentId !== null ? history.messages[message.parentId] : null;
// ...
messages = _messages;

Array.unshift()는 매 호출마다 기존 모든 원소를 한 칸씩 뒤로 밀어야 합니다. 대화 깊이가 n일 때 총 이동 횟수는 1 + 2 + ... + (n-1) = O(n²)입니다.

After: push() + reverse() — O(n)

// Messages.svelte
_messages.push(message);
message = message.parentId !== null ? history.messages[message.parentId] : null;
// ...
messages = _messages.reverse();

Array.push()는 amortized O(1)이고, 마지막에 reverse()는 O(n)입니다. 총 시간 복잡도가 O(n)으로 줄어들며, 동일한 메시지 순서를 보장합니다.

왜 이게 좋은가

1. 스트리밍 중 반복 호출 경로

buildMessages는 스트리밍 응답 중에도 호출될 수 있는 함수입니다. 긴 대화에서 토큰이 도착할 때마다 O(n²) 연산이 발생하면 UI 프레임 드랍으로 이어집니다. O(n)으로 개선하면 수백 턴의 대화에서도 일정한 성능을 유지합니다.

2. JavaScript 엔진의 배열 최적화

V8 엔진에서 unshift()는 내부적으로 배열 백업 스토어 전체를 재배치해야 합니다. 반면 push()는 사전 할당된 공간에 단순 포인터 쓰기로 끝나는 경우가 대부분입니다. reverse()도 in-place 스왑으로 캐시 친화적입니다.

3. Python에서의 동일 패턴

흥미롭게도 Open WebUI의 Python 백엔드에서도 동일한 list.insert(0) 안티패턴이 발견되어 별도 PR로 수정된 바 있습니다. 프론트엔드와 백엔드 모두에서 같은 알고리즘 실수가 반복된 사례입니다.

참고 자료

• MDN Web Docs: Array.prototype.unshift() — unshift의 동작 방식
• V8 Blog: Elements Kinds — V8의 배열 내부 최적화 전략