[Open WebUI] O(n²) 시간 복잡도 메시지 리스트 생성 버그 수정

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

들어가며

Open WebUI에서 사용자가 메시지를 보낼 때, LLM에 전달할 대화 기록을 구성하는 get_message_list 함수가 O(n²) 시간 복잡도로 동작하고 있었습니다. 이 함수는 메시지 전송, 채팅 검색, RAG 컨텍스트 구축 등 핵심 경로에서 호출되므로, 대화가 길어질수록 응답 시작까지의 지연이 크게 증가하는 문제가 있었습니다. 단 2줄의 변경으로 O(n)으로 개선한 PR입니다.

핵심 코드 분석

Before: list.insert(0) — O(n²)

def get_message_list(messages_map, message_id):
    message_list = []
    while current_message:
        message_list.insert(
            0, current_message
        )  # Insert the message at the beginning of the list
        parent_id = current_message.get("parentId")
        current_message = messages_map.get(parent_id) if parent_id else None
    return message_list

Python의 list.insert(0, x)는 리스트의 모든 기존 원소를 한 칸씩 뒤로 밀어야 합니다. 대화 깊이가 d일 때 총 이동 횟수는 1 + 2 + ... + (d-1) = O(d²)입니다.

After: append + reverse — O(n)

def get_message_list(messages_map, message_id):
    message_list = []
    while current_message:
        message_list.append(current_message)
        parent_id = current_message.get("parentId")
        current_message = messages_map.get(parent_id) if parent_id else None
    message_list.reverse()
    return message_list

list.append()는 amortized O(1)이고, 마지막에 list.reverse()는 O(d)입니다. 총 시간 복잡도는 O(d)로 줄어듭니다.

왜 이게 좋은가

1. 실사용 시나리오에서의 영향

이 함수는 다음 경로에서 호출됩니다:

• middleware.py: 메시지 전송 시 대화 기록 구성 → 사용자가 느끼는 "첫 토큰 지연"에 직접 영향
• routers/chats.py: 채팅 검색 시 모든 대화의 메시지 리스트 구성
• retrieval/utils.py: RAG 컨텍스트 구축 시 대화 기록 접근

대화가 100턴을 넘기면 insert(0)은 약 5,000번의 원소 이동을 발생시키지만, append+reverse는 200번의 연산으로 충분합니다.

2. Python 리스트의 내부 구조

Python의 list는 내부적으로 동적 배열(C 배열의 포인터 배열)로 구현됩니다. insert(0)은 memmove로 전체 포인터를 이동시키므로 캐시 라인을 무효화하고, 대용량 리스트에서 메모리 대역폭 병목까지 발생할 수 있습니다.

3. 보편적인 안티패턴

list.insert(0) 반복은 Python에서 가장 흔한 O(n²) 실수 중 하나입니다. collections.deque의 appendleft()나 이번 PR처럼 append+reverse 패턴이 올바른 대안입니다.

참고 자료

• Python TimeComplexity - wiki.python.org — Python 내장 자료구조의 시간 복잡도 참조
• CPython listobject.c ins1 함수 — list.insert의 memmove 구현