libstdc++: Templatize regex executor traversal mode
Templatized regex executor traversal modes to eliminate runtime branches and improve performance.
This commit addresses significant regex performance regressions introduced previously by making the executor’s traversal mode (DFS vs. BFS) a template parameter instead of a runtime member. This allows the compiler to eliminate dead code paths for the unused mode at compile time, reducing dynamic instructions and mispredicted branches. This optimization restores and surpasses the performance of GCC 15 for email, URI, and IPv4 regex matching.
In Details
The _Executor class previously used a _M_search_mode member to distinguish between DFS and BFS traversal algorithms. This led to runtime branches and dead code within hot functions, impacting performance. By moving _M_search_mode to a template parameter, the compiler can now perform full code specialization for each traversal mode, eliminating the conditional branches and compare instructions, and improving instruction cache locality.
- DFS
- Direct Finite State Machine, a method for implementing regular expression matching.
- BFS
- Breadth-First Search, another algorithm that can be used for regular expression matching, often contrasted with DFS.
- templatize
- To convert a piece of code (like a class or function) to use C++ templates, allowing it to operate on different types or configurations specified at compile time.
- IPA
- Interprocedural Analysis, a compiler optimization technique that analyzes code across function calls. Opaque parameters in runtime code can hinder IPA.