RE# 정규식 엔진, Rust로 재구현! 성능과 유연성을 잡다.
RE# 정규식 엔진이 Rust로 재구현되어 크레이트(crate) 형태로 공개됨
기존 F# 버전과 달리 기호 미분(Symbolic Derivatives) 방식을 사용하여 성능 향상 도모
UTF-8 지원 및 lookahead 제한 해제 등 기능 개선 및 확장
SIMD 최적화 부재로 인해 리터럴 패턴(Literal Pattern) 성능은 낮지만, 다른 패턴에서는 경쟁력 확보
커뮤니티에서는 정규식 엔진의 성능과 유연성에 대한 관심이 높음
기호 미분(Symbolic Derivatives) 기반 엔진 설계
RE#의 Rust 버전은 기존 Brzozowski 미분 대신 기호 미분(Symbolic Derivatives)을 핵심 알고리즘으로 채택했다. 기호 미분은 각 문자에 대한 미분을 계산하는 대신, 모든 가능한 문자에 대한 결정 트리를 생성하여 상태 전이를 처리한다. 이러한 방식은 미분 계산 횟수를 줄여 성능을 향상시키고, minterm 계산을 자연스럽게 수행할 수 있게 한다. 특히, ITE(If-Then-Else) 트리를 활용하여 문자 집합을 효율적으로 분할하고 처리한다.
UTF-8 지원 및 lookahead 확장
Rust 버전은 UTF-16 기반의 F# 버전과 달리, UTF-8을 직접 지원하여 바이트 단위의 문자열 처리를 수행한다. 또한, lookahead 연산자 사용에 대한 제한을 해제하여, 복잡한 lookahead 패턴을 지원한다. 예를 들어, `(?=.*a)(?=.*b)(?=.*c)def`와 같은 패턴을 지원하며, lookahead 내부의 중첩된 lookahead도 처리할 수 있다. 이러한 기능은 정규식 표현의 유연성을 높이고, 다양한 사용 사례를 지원한다.
성능 벤치마크 및 SIMD 최적화 부재
벤치마크 결과에 따르면, Rust 버전은 리터럴 패턴(Literal Pattern)에서 .NET의 SIMD 최적화를 활용하는 기존 F# 버전에 비해 성능이 낮다. 하지만, case-insensitive 매칭과 같은 다른 패턴에서는 16,833배의 성능 향상을 보였다. 저자는 SIMD prefilters 및 right-to-left scanning을 위한 SIMD 루틴(SIMD Routines)의 부재를 언급하며, 향후 성능 개선의 여지를 남겼다.
256-bit 벡터 기반 문자 집합 표현
Rust 버전은 바이트 단위 처리를 활용하여, 문자 집합을 256-bit 비트 벡터로 표현한다. 각 비트는 가능한 바이트 값을 나타내며, AND, OR, NOT과 같은 비트 연산을 통해 문자 집합 연산을 수행한다. 이러한 방식은 BDD(Binary Decision Diagrams)를 사용하는 .NET 버전에 비해 간단하고 빠르며, CPU 캐시 효율성을 높인다. 특히, AVX2를 통해 단일 명령어로 256비트 연산을 수행할 수 있다.
