RE# 정규식 엔진, Rust로 재구현하여 성능과 유연성 모두 잡다!
기존 F# 기반 RE# 엔진을 Rust로 재구현하여 다양한 플랫폼 지원 및 성능 향상을 도모함
심볼릭 미분(Symbolic Derivatives) 방식을 도입하여 정규식 처리 효율을 높이고, lookahead 제약 조건을 완화함
UTF-8 지원 및 256비트 벡터 기반 문자 집합(Character Sets)을 통해 메모리 사용량 감소 및 속도 개선을 이룸
벤치마크 결과, 리터럴 패턴(Literal Patterns)에서는 기존 엔진에 미치지 못하나, 케이스 인센서티브(Case-insensitive) 매칭 등에서 괄목할 만한 성능 향상을 보임
심볼릭 미분(Symbolic Derivatives) 기반 엔진 아키텍처
Rust로 재구현된 RE# 엔진은 기존의 Brzozowski 미분 대신 심볼릭 미분(Symbolic Derivatives) 방식을 채택했다. 이는 문자 집합을 기반으로 하는 ITE(If-Then-Else) 트리를 사용하여 각 상태에 대한 미분을 계산한다. 기술적으로 보면, 이 방식은 개별 문자가 아닌, 모든 가능한 문자에 대한 결정 트리를 생성하여 미분 연산의 효율성을 높인다. 이러한 아키텍처는 특히 문자 집합 연산에서 성능 향상을 가져온다.
UTF-8 지원 및 바이트 기반 처리
Rust 버전의 RE# 엔진은 UTF-16 대신 UTF-8을 지원하며, 바이트 단위로 문자열을 처리한다. 이는 256비트 비트 벡터를 사용하여 문자 집합을 표현함으로써 메모리 사용량 감소 및 연산 속도 향상을 가능하게 한다. 특히, 문자 집합 연산은 AVX2 명령어를 통해 단일 명령어로 처리되어 CPU 캐시 효율성을 높인다. 이러한 바이트 기반 처리는 성능 최적화에 기여한다.
Lookahead 제약 조건 완화 및 단일 패스 매칭
Rust 버전은 lookahead 연산에 대한 제약 조건을 완화하여, 복잡한 정규식 패턴을 지원한다. 특히, (?=.*a)(?=.*b)(?=.*c)def와 같은 중첩된 lookahead를 단일 패스로 처리할 수 있다. 기술적으로 보면, lookahead(body, tail) 형태로 묶어 body와 tail을 함께 미분함으로써 매칭 과정의 효율성을 높인다. 이러한 접근 방식은 정규식 표현의 유연성을 향상시킨다.
성능 벤치마크 및 트레이드오프 분석
벤치마크 결과에 따르면, Rust 버전은 리터럴 패턴(Literal Patterns)에서 기존 엔진에 비해 성능이 낮지만, 케이스 인센서티브(Case-insensitive) 매칭에서는 16,833배의 성능 향상을 보였다. 이는 Rust 버전이 SIMD 최적화를 아직 구현하지 않았기 때문이다. 하지만, 심볼릭 미분 방식과 UTF-8 지원을 통해 다양한 정규식 패턴에 대한 성능 개선 가능성을 보여준다. 향후 SIMD 최적화가 이루어지면 성능 격차를 줄일 수 있을 것으로 예상된다.
