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

31–40 of 90 posts

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

#31

Post by sgc »

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…

I second this request. It would be wonderful to be able to test the rust implementation since it easier to call from other languages in my typical setup. I have a couple uses cases I have never fully resolved, just implemented partial work arounds and accepted a restricted feature set. This would probably allow me to deal with them correctly.

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

#32

Post by ieviev »

feldrim wrote: post #30
ieviev wrote: post #24

Earlier quoted context omitted.

There's currently only a string solver with the same core library, but not a full regex engine https://github.com/ieviev/cav25-resharp-smt I will open source the rust engine soon as well, some time this month. As for the benchmarks, it's the fastest for large patterns and lookarounds, where leftmost-longest lets you get away with less memory usage so we don't need to transition from DFA to NFA. In the github readme b…

Would SearchValues help there for a fallback to a SIMD optimized simple string literal search rather than the happy path?

Yes, that's exactly what we did to be competitive in the benchmarks.

There's a lot of simple cases where you don't really need a regex engine at all.

integrating SearchValues as a multi-string prefix search is a bit harder since it doesn't expose which branch matched so we would be taking unnecessary steps.

Also .NET implementation of Hyperscan's Teddy algorithm only goes left to right.. if it went right to left it would make RE# much faster for these cases.

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

#33

Post by u_sama »

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…

in what is it different ?

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

#36

Post by burntsushi »

ieviev wrote: post #24
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…

There's currently only a string solver with the same core library, but not a full regex engine https://github.com/ieviev/cav25-resharp-smt I will open source the rust engine soon as well, some time this month. As for the benchmarks, it's the fastest for large patterns and lookarounds, where leftmost-longest lets you get away with less memory usage so we don't need to transition from DFA to NFA. In the github readme b…

> for simple string literals it will definitely lose to Hyperscan and Rust regex since they have a high effort left-to-right SIMD algorithm that we cannot easily use

I think "simple string literals" undersells it. I think that description works for engines like RE2 or Go's regex engine, but not Hyperscan or Rust regex. (And I would put Hyperscan in another category than even Rust regex.) Granted, it is arguably difficult to be succinct here since it's a heuristic with difficult-to-predict failure points. But something like: "patterns from which a small number of string literals can be extracted."

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

#38

Post by ieviev »

burntsushi wrote: post #36
ieviev wrote: post #24

Earlier quoted context omitted.

There's currently only a string solver with the same core library, but not a full regex engine https://github.com/ieviev/cav25-resharp-smt I will open source the rust engine soon as well, some time this month. As for the benchmarks, it's the fastest for large patterns and lookarounds, where leftmost-longest lets you get away with less memory usage so we don't need to transition from DFA to NFA. In the github readme b…

> for simple string literals it will definitely lose to Hyperscan and Rust regex since they have a high effort left-to-right SIMD algorithm that we cannot easily use I think "simple string literals" undersells it. I think that description works for engines like RE2 or Go's regex engine, but not Hyperscan or Rust regex. (And I would put Hyperscan in another category than even Rust regex.) Granted, it is arguably diffi…

yes, that is correct. also Rust's engine matches the full unicode spec as individual characters, whereas .NET's will chop emojis into two sometimes, so Rust at a disadvantage here.

something i've been also wondering is how does Harry (https://ieeexplore.ieee.org/document/10229022) compare to the Teddy algorithm, it's written by some of the same authors - i wonder if it's used in any engines outside of Hyperscan today.

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

#39

Post by nodra »

nbevans wrote: post #34
FrustratedMonky wrote: post #21

F# is one of the biggest 'What could have beens'. Great language, that just didn't hit the right time, or reach critical mass of the gestalt of the community.

It uses far less tokens than C#, so watch this space...

Care to explain? Pattern matching, type inference, etc.?

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

#40

Post by murkt »

u_sama wrote: post #33
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…

in what is it different ?

Starts of sentences are not capitalized, which makes it a bit harder to read. English language prescribes capitalization after a period.
Post reply on HN