정규 표현식(Regex) 매칭, O(n²)에서 O(n)으로 성능 혁신!
by DD
4개월 전
조회수 8
기존 정규 표현식(Regex) 엔진은 모든 매치(All Matches)를 찾는 과정에서 O(n²) 시간 복잡도(Time Complexity) 문제를 겪음
RE# 엔진은 두 번의 패스(Two Passes)를 통해 선형 시간 내에 모든 매치를 찾는 새로운 알고리즘(New Algorithm)을 제시
성능 향상을 위해 CPU 인트린직(CPU Intrinsics)을 활용, 기존 벤치마크(Benchmark)에서 경쟁력을 확보
스트리밍(Streaming) 환경에서의 제약과 캡처 그룹(Capture Groups) 미지원 등 몇 가지 한계점(Limitations) 존재
선형 시간 내 모든 매치(All Matches)의 구현
기존 정규 표현식(Regex) 엔진은 모든 매치를 찾는 과정에서 O(n²) 시간 복잡도(Time Complexity) 문제를 겪는다는 점을 지적한다. 특히, `.*a|b` 패턴과 같이 최악의 경우, 각 위치에서 매치를 시도하며 삼각 합(Triangular Sum) 형태로 시간이 증가한다. RE# 엔진은 이러한 문제를 해결하기 위해 입력 문자열을 두 번 순회하는 알고리즘을 사용하며, 이를 통해 패턴과 입력에 관계없이 선형 시간 내에 모든 매치를 찾을 수 있도록 설계되었다.
RE# 엔진의 아키텍처 및 성능 분석
RE# 엔진은 두 번의 패스(Two Passes)를 통해 모든 매치 경계를 표시하는 방식으로 작동한다. 이러한 아키텍처는 병목 현상(Bottleneck)을 줄여 성능을 향상시키며, 특히 많은 매치를 생성하는 패턴(예: 로그 파싱)에서 기존 엔진 대비 획기적인 속도 향상을 보인다. 벤치마크 결과에 따르면, RE#은 기존 Rust regex 엔진과 비교하여 리터럴 매칭(Literal Matching) 및 대체(Alternation) 패턴에서 유사하거나 더 나은 성능을 보여준다.
성능 최적화를 위한 CPU 인트린직(CPU Intrinsics) 활용
RE# 엔진은 성능 향상을 위해 CPU 인트린직(CPU Intrinsics)을 적극적으로 활용한다. 특히, AVX2 및 NEON 구현을 통해 리터럴 검색, 다중 위치 매칭, 범위 기반 문자 클래스 스캐닝 등에서 최적화를 이루었다. 이러한 최적화는 기존 regex 엔진과의 성능 격차를 줄이는 데 기여했으며, 특히 CPU 레벨에서의 최적화(CPU-Level Optimization)를 통해 전반적인 성능을 향상시켰다.
스트리밍(Streaming) 환경에서의 제약 및 캡처 그룹(Capture Groups) 미지원
RE# 엔진은 스트리밍(Streaming) 환경에서 몇 가지 제약 사항을 가진다. 특히, `^.*$`와 같이 명확한 경계가 있는 패턴을 제외하고는, 모든 매치를 찾는 과정에서 무한 루프에 빠질 수 있다. 또한, RE#은 현재 캡처 그룹(Capture Groups)을 지원하지 않으며, 이는 캡처 그룹이 매칭 후 별도의 연산이 필요하기 때문이다. 이러한 한계점에도 불구하고, RE#은 POSIX 의미론(POSIX Semantics)을 준수하며, 부울 연산자(Boolean Operators) 및 룩어라운드(Lookarounds)를 지원한다.
REmatch와의 차이점
RE# 엔진은 REmatch와는 다른 문제를 해결한다. REmatch는 모든 중첩된 매치를 반환하는 반면, RE#은 겹치지 않는 최장 일치(Leftmost-Longest) 매치를 찾는다. REmatch는 O(n²)의 중첩된 매치를 반환하므로, RE#은 grep, ctrl+f, find_iter와 같은 도구에서 사용되는 정확한 매칭 의미론(Matching Semantics)을 제공하는 데 초점을 맞춘다.
