RE#: how we built the fastest regex engine in F#

Re:RE#: how we built the fastest regex engine in F# by ieviev on Monday March 09, 2026 @02:06PM (#47312901)

I have experienced this as well, the performance degradation of DFA to NFA is enormous and while not as bad as exponential backtracking, it's close to ReDoS territory.

The rust version of the engine (https://github.com/ieviev/resharp) just returns an Error instead of falling back to NFA, I think that should be a reasonable approach, but the library is still new so i'm still waiting to see how it turns out and whether i had any oversights on this.

[ Parent | on HN ]

Re:RE#: how we built the fastest regex engine in F# by ot on Monday March 09, 2026 @05:20PM (#47315703)

Here RE2 does not fall back to the NFA, it just resets the Lazy DFA cache and starts growing it again. The latency spikes I was mentioning are due to the cost of destroying the cache (involving deallocations, pointer chasing, ...)

[ Parent | on HN ]

Re:RE#: how we built the fastest regex engine in F# by ieviev on Tuesday March 10, 2026 @12:33PM (#47325533)

Ah, sorry then i misunderstood the comment

I'm not sure if it's with both RE2 or Rust, but some internal engines of Rust appear to allocate a fixed buffer that it constantly re-creates states into.

I'm not really familiar with the eviction technique of RE2 but I've done a lot of benchmark comparisons. A good way to really stress test RE2 is large Unicode classes, \w and \d in RE2 are ascii-only, i've noticed Unicode (\p{class}) classes very drastically change the throughput of the engine.

[ Parent | on HN ]