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

Re:RE#: how we built the fastest regex engine in F# by ieviev on Wednesday March 04, 2026 @08:28AM (#47247121)

It goes from start of the first match to the longest "alive" end, in practice it will go to a dead state and return after finding the match end.

there's an implicit `.*` in front of the first pass but i felt it would've been a long tangent so i didn't want to get into it.

so given input 'aabbcc' and pattern `b+`,

first reverse pass (using `.*b+`) marks 'aa|b|bcc'<-

the forward pass starts from the first match:

'aa->b|b|cc' marking 2 ends

then enters a dead state after the first 'c' and returns the longest end: aa|bb|cc

i hope this explains it better

[ Parent | on HN ]

Re:RE#: how we built the fastest regex engine in F# by masfuerte on Wednesday March 04, 2026 @09:48AM (#47248228)

Cheers. I was more confused by how you were doing multiple matches. So I read the paper, which describes the AllEnds algorithm. If I understand correctly, the reverse pass captures all of the match starts and these need to be remembered for the forward pass. Which is what you were showing above, but I didn't follow it.

So, once it gets going, a traditional engine can produce matches iteratively with no further allocation, but RE# requires allocation proportional to the total number of matches. And in return, it's very much faster and much easier to use (with intersection and complement).

[ Parent | on HN ]

Re:RE#: how we built the fastest regex engine in F# by ieviev on Wednesday March 04, 2026 @10:08AM (#47248612)

Yes, exactly correct

It's also beneficial to merge some of the matching locations into ranges where possible, so when `a*` matches a long sequence of '|a|a|a|a|a|', it can be represented as a range of (0,5), we do this to keep the lookaround internal states smaller in the engine.

[ Parent | on HN ]