Optimizing regex compilers
Tevaearai, Zacharie · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · 2025
Modern regular expressions are powerful string-processing tools, available in most programming languages. However, their power comes at a cost. Most regex engines exhibit worst-case exponential time complexity with respect to the input size, because they rely on a backtracking matching algorithm. This can result in severe performance issues, and can be a vulnerability when the input string or the regex is controlled by the user, leading to so-called Regular Expression Denial of Service (ReDoS) attacks. Fortunately, a large subset of modern regex features can be matched in linear time using alternative algorithms. However they come with various tradeoffs; for instance matching using a deterministic automata is very fast, but suffer from exponential pre-processing time, while using a PikeVM gives use linear compilation and execution time complexity but often performs poorly in practice. We focus on that second algorithm, the PikeVM, and propose a native-compilation approach to accelerate its execution. We present two implementations: one as a standalone library and another integrated into V8, the JavaScript engine that powers Chromium. Our approach achieves a 3.6× speedup on average compared to other implementations based on an interpreter.