AI 요약
정규표현식의 성능 보장은 지난 수십 년간 IT 업계의 주요 과제였으나, 대다수 엔진이 '전체 매칭 검색' 시 발생하는 성능 저하 문제를 해결하지 못했습니다. RE2, Go, Rust, .NET의 NonBacktracking 모드 등 소위 '선형 시간'을 보장한다는 엔진들도 실제로는 단일 매칭에만 해당할 뿐, find_iter나 FindAll 호출 시 최악의 경우 O(m * n²) 복잡도를 가집니다. 이는 매칭을 찾을 때마다 다음 위치에서 다시 전체 검색을 시도하는 구조적 한계 때문입니다. Russ Cox는 이미 2009년에 Alfred Aho의 awk조차 이러한 비효율적인 루프 방식을 사용한다고 지적한 바 있습니다. 학술적인 정규표현식 연구가 실제 매칭의 위치나 개수보다는 단순한 '일치 여부' 판단에만 집중해 온 것이 이 문제의 근본 원인으로 꼽힙니다.
핵심 인사이트
- 성능의 허상: 선형 시간을 광고하는 대부분의 엔진(RE2, Go, Rust regex)이 전체 검색 시에는 $O(m \times n^2)$ 복잡도로 회귀함.
- 구체적 지표: BurntSushi의
rebar벤치마크 결과, 입력 데이터가 2배로 늘어날 때 처리량(Throughput)이 1/2로 줄어드는 명확한 이차적 성능 저하가 확인됨. - 학계의 한계: 정규표현식 이론이 '문자열이 패턴에 맞는가'라는 Yes/No 문제에만 매몰되어, 실무에서 중요한 '매칭의 위치와 개수'를 찾는 문제를 경시함.
- 백트래킹과의 차이: 지수적(Exponential) 시간이 걸리는 백트래킹 방식보다는 낫지만, 대규모 문서 검색 시 100배 큰 문서가 100배가 아닌 10,000배(약 3시간)의 시간을 소요하게 만듦.
주요 디테일
- 발생 메커니즘:
.*a|b패턴으로 'b'만 가득한 문자열을 검색할 때, 엔진은 각 위치에서.*a를 찾기 위해 남은 문자열을 매번 스캔하며 실패한 뒤b를 매칭하는 '삼각형 합(Triangular sum)' 연산을 수행함. - 역사적 배경: 1970년대 Thompson의 NFA 구성 이후 거의 모든 엔진이 이 문제를 방치했으며, 2009년 Russ Cox의 지적 이후에도 근본적인 수정이 이루어지지 않음.
- 문서화 실태: Rust의
regex crate문서만이 이 최악의 복잡도를 $O(m \times n^2)$라고 솔직하게 명시하고 있음. - 임시 방편: 매칭을 찾는 즉시 중단하는 모드를 활성화하면 $O(m \times n)$으로 복구되지만, 이는 전체 매칭 결과를 얻어야 하는 실제 요구사항과는 배치됨.
- 참조 프로젝트: 작성자는 F# 기반의 RE# 및 Rust로의 재작성 과정을 통해 세계에서 가장 빠른 엔진을 개발하며 이 문제를 심도 있게 분석함.
향후 전망
- 엔진 설계의 변화: 단순 DFA/NFA 루프를 넘어, 매칭 위치를 효율적으로 추적하는 새로운 알고리즘이 현대 엔진에 도입될 가능성이 높음.
- 보안 위협 인식: 신뢰할 수 없는 입력값(Haystack)에 대해 전체 검색을 수행할 경우 발생할 수 있는 서비스 거부(DoS) 공격 위험에 대한 개발자들의 주의가 요구됨.
출처:hackernews