Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

iev.ee

Post reply on HN
Print view View original

81–90 of 90 posts

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

#81

Post by UltraSane »

ieviev wrote: post #62
noelwelsh wrote: post #16

I love regular expression derivatives. One neat thing about regular expression derivatives is they are continuation-passing style for regular expressions. The derivative is "what to do next" after seeing a character, which is the continuation of the re. It's a nice conceptual connection if you're into programming language theory. Low-key hate the lack of capitalization on the blog, which made me stumble over every se…

While i completely understand it, the lack of capitalization is just an indication that a human wrote this, it has to be imperfect i see enough slop and Look At Me on a daily basis. i don't want it to look like an ad or a LinkedIn post in 2026.

Refusing to use standard capitalization just looks unprofessional.

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

#82

Post by voxl »

ieviev wrote: post #62
noelwelsh wrote: post #16

I love regular expression derivatives. One neat thing about regular expression derivatives is they are continuation-passing style for regular expressions. The derivative is "what to do next" after seeing a character, which is the continuation of the re. It's a nice conceptual connection if you're into programming language theory. Low-key hate the lack of capitalization on the blog, which made me stumble over every se…

While i completely understand it, the lack of capitalization is just an indication that a human wrote this, it has to be imperfect i see enough slop and Look At Me on a daily basis. i don't want it to look like an ad or a LinkedIn post in 2026.

It's your personal style. Researchers have their quirks, don't listen to the industry suits saying dumb shit like "it's unprofessional" you can mask if you're looking for a job at Google in the future, but for now enjoy being yourself and say fuck you to the lazy socially imposed dogma of this particular community

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

#83

Post by gfody »

voxl wrote: post #82
ieviev wrote: post #62

Earlier quoted context omitted.

While i completely understand it, the lack of capitalization is just an indication that a human wrote this, it has to be imperfect i see enough slop and Look At Me on a daily basis. i don't want it to look like an ad or a LinkedIn post in 2026.

It's your personal style. Researchers have their quirks, don't listen to the industry suits saying dumb shit like "it's unprofessional" you can mask if you're looking for a job at Google in the future, but for now enjoy being yourself and say fuck you to the lazy socially imposed dogma of this particular community

<3

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

#84

Post by gbacon »

ngruhn wrote: post #70
gbacon wrote: post #11

That’s beautiful work. Check out other examples in the interactive web app: https://ieviev.github.io/resharp-webapp/ Back in the Usenet days, questions came up all the time about matching substrings that do not contain whatever. It’s technically possible without an explicit NOT operator because regular languages are closed under complement — along with union, intersection, Kleene star, etc. — but a bear to get right…

I built a similar library in TypeScript (also based on regex derivatives). You can really built cool tools with complement / intersection. E.g. 1) regex equivalence checker (check if intersection of complements is empty): https://gruhn.github.io/regex-utils/equiv-checker.html 2) password generator from regex constraints (16+ chars, at least on upper case char, etc). Just take the intersection of all constraints and g…

That’s really slick! I’m glad someone paid attention in automata theory.

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

#85

Post by ieviev »

andriamanitra wrote: post #15

This is very interesting. I'm a bit skeptical about the benchmarks / performance claims because they seem almost too good to be true but even just the extended operators alone are a nice improvement over existing regex engines. The post mentions they also have a native library implemented in Rust without dependencies but I couldn't find a link to it. Is that available somewhere? I would love to try it out in some of…

If you're interested, the rust version is open source now as well: https://github.com/ieviev/resharp

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

#86

Post by phillipcarter »

systems wrote: post #57

I am a bit worried about the state of F# thought, Don Syme seem to no longer be acting as the project lead, and I didn't hear of any successor Compared to most actively developed languages F# look very stale currently

Don has always been the language design BDFL, but has ensured it was community driven since at least 2012.

In all practicality the team at Microsoft has always been the main drivers of the F# project. It comes with the territory when you’re the primary group maintaining the compiler, core library, SDK, FSI, and Editor integrations.

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

#87

Post by ot »

btown wrote: post #56
ieviev wrote: post #52

Earlier quoted context omitted.

We refer to this in the paper as well, The standard way to do intersection / complementation of regexes with NFAs requires determinization, which causes a huge blowup, whereas for us this is the cost of a derivative. It is true that we cannot avoid enormous DFA sizes, a simple case would be (.*a.*)&(.*b.*)&(.*c.*)&(.*d.*)... which has 2^4 states and every intersection adds +1 to the exponent. How we get around this i…

> The second time the same (or similar) input is used these states are already created and it is linear. Does this imply that the DFA for a regex, as an internal cache, is mutable and persisted between inputs? Could this lead to subtle denial-of-service attacks, where inputs are chosen by an attacker to steadily increase the cached complexity - are there eviction techniques to guard against this? And how might this w…

> are there eviction techniques to guard against this?

RE2 resets the cache when it reaches a (configurable) size limit. Which I found out the hard way when I had to debug almost-periodic latency spikes in a service I managed, where a very inefficient regex caused linear growth in the Lazy DFA, until it hit the limit, then all threads had to wait for its reset for a few hundred milliseconds, and then it all started again.

I'm not sure if dropping the whole cache is the only feasible mitigation, or some gradual pruning would also be possible.

Either way, if you cannot assume that your cache grows monotonically, synchronization becomes more complicated: the trick mentioned in the other comment about only locking the slow path may not be applicable anymore. RE2 uses RW-locking for this.

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

#88

Post by ieviev »

ot wrote: post #87
btown wrote: post #56

Earlier quoted context omitted.

> The second time the same (or similar) input is used these states are already created and it is linear. Does this imply that the DFA for a regex, as an internal cache, is mutable and persisted between inputs? Could this lead to subtle denial-of-service attacks, where inputs are chosen by an attacker to steadily increase the cached complexity - are there eviction techniques to guard against this? And how might this w…

> are there eviction techniques to guard against this? RE2 resets the cache when it reaches a (configurable) size limit. Which I found out the hard way when I had to debug almost-periodic latency spikes in a service I managed, where a very inefficient regex caused linear growth in the Lazy DFA, until it hit the limit, then all threads had to wait for its reset for a few hundred milliseconds, and then it all started a…

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.

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

#89

Post by ot »

ieviev wrote: post #88
ot wrote: post #87

Earlier quoted context omitted.

> are there eviction techniques to guard against this? RE2 resets the cache when it reaches a (configurable) size limit. Which I found out the hard way when I had to debug almost-periodic latency spikes in a service I managed, where a very inefficient regex caused linear growth in the Lazy DFA, until it hit the limit, then all threads had to wait for its reset for a few hundred milliseconds, and then it all started a…

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 wheth…

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, ...)

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

#90

Post by ieviev »

ot wrote: post #89
ieviev wrote: post #88

Earlier quoted context omitted.

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 wheth…

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, ...)

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.

Post reply on HN