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.
RE#: how we built the fastest regex engine in F#
21–30 of 90 posts
Re: RE#: how we built the fastest regex engine in F#
#22This is very impressive. > how does RE# find the leftmost-longest match efficiently? remember the bidirectional scanning we mentioned earlier - run the DFA right to left to find all possible match starts, then run a reversed DFA left to right to find the ends. the leftmost start paired with the rightmost end gives you leftmost-longest. two linear DFA scans, no backtracking, no ambiguity. I'm pretty sure that should s…
> I'm pretty sure that should say "the leftmost start paired with the leftmost end".
I’m pretty sure it shouldn’t, that would give you the leftmost shortest match instead of leftmost longest.
Re: RE#: how we built the fastest regex engine in F#
#23@burnsushi is that true?
Tentative doubt until/if he confirms. (but specifically in F# though. Edit: No, comparisons to Rust etc. are made in TFA)
Re: RE#: how we built the fastest regex engine in F#
#24This 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 benchmarks it's faster than the exponential implementations of .NET Compiled so the 35 000x can be an arbitrary multiplier, you can keep adding alternatives and make it 1000000x.
for a small set of 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.
Re: RE#: how we built the fastest regex engine in F#
#25This is very impressive. > how does RE# find the leftmost-longest match efficiently? remember the bidirectional scanning we mentioned earlier - run the DFA right to left to find all possible match starts, then run a reversed DFA left to right to find the ends. the leftmost start paired with the rightmost end gives you leftmost-longest. two linear DFA scans, no backtracking, no ambiguity. I'm pretty sure that should s…
> I'm pretty sure that should say "the leftmost start paired with the leftmost end". I’m pretty sure it shouldn’t, that would give you the leftmost shortest match instead of leftmost longest.
As originally written, doesn't it go from the start of the first match to the end of the last match? I feel like I'm missing something.
Re: RE#: how we built the fastest regex engine in F#
#26You got me at TalTech. Great job and the paper is high quality. I'll have to learn F# but I believe it is worth it.
Re: RE#: how we built the fastest regex engine in F#
#27I've had nothing but great experience with F#. If it wasn't associated with Microsoft, it'd be more popular than haskell
I think if it weren't a 'first class' member of .NET ecosystem[0], no one would know F#. After all Haskell and Ocaml already exist. [0]: my very charitable take, as MS obviously cares C# much much more than F#.
[dead]
Re: RE#: how we built the fastest regex engine in F#
#28Worth mentioning (haven’t checked if the paper talks about this) that while the industry mostly forgot about derivatives and extended REs (i.e. REs with intersection and negation), academia did not. Unfortunately, there have been some pretty discouraging results: the DFA for an extended RE (including a lazy DFA implemented using derivatives, as here) is worst-case doubly exponential in the length of the expression[1], not just exponential as for normal REs. So there is a potential reason not to support intersections in one’s RE matcher, even if they are enticingly easy to implement in terms of derivatives (and even if I personally like to see experimentation in this direction).
[1] https://www.sciencedirect.com/science/article/pii/S030439751...
Re: RE#: how we built the fastest regex engine in F#
#29Earlier quoted context omitted.
> I'm pretty sure that should say "the leftmost start paired with the leftmost end". I’m pretty sure it shouldn’t, that would give you the leftmost shortest match instead of leftmost longest.
As originally written, doesn't it go from the start of the first match to the end of the last match? I feel like I'm missing something.
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
Re: RE#: how we built the fastest regex engine in F#
#30This 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…
Would SearchValues help there for a fallback to a SIMD optimized simple string literal search rather than the happy path?